문제: https://www.acmicpc.net/problem/9078
문제
주어진 숫자 열을 정렬하는데, 사용할 수 있는 연산은 이웃하는 두 숫자를 다른 두 수 사이나 숫자열의 맨 앞 혹은 맨 뒤에 끼워 넣는 것 뿐이다. 즉, 한 번에 숫자를 하나씩 옮기는 것이 아니라, 이웃하는 숫자를 두 개씩 묶어서 옮긴다. 4 1 5 3 2 의 경우 다음과 같이 정렬할 수 있다.
4 1 5 3 2 → 3 2 4 1 5 → 3 4 1 2 5 → 1 2 3 4 5
그러나 2 1 3 의 경우에는 어떻게 하더라도 정렬할 수 없다.
이와 같이 입력으로 1에서 N까지의 서로 다른 N의 정수로 구성된 숫자 열이 주어졌을 때, 그것이 위의 연산만으로 정렬가능한지 여부를 결정하는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 정수 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄에는 N개의 정수가 공백을 사이에 두고 주어진다.
출력
각 테스트 케이스에 대해서 정렬 가능하면 YES를, 아니면 NO를 한 줄에 하나씩 출력한다.
나의 해답
https://github.com/jeongmincha/solving-algorithm/blob/master/BOJ/9078.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for test_case in range(int(input())):
n = int(input())
lst = input().split()
count = 0
for i in range(n):
for j in range(i+1, n):
if lst[i] > lst[j]:
count += 1
if count % 2 == 0:
print('YES')
else:
print('NO')
설명
이미 정렬이 가능한 배열에 대해서 2개의 원소가 추가로 들어올 때, 그 원소들도 이미 정렬된 상태여야만 전체 배열이 정렬 가능한 상태라고 말할 수 있다.
예를 들어서 1이라는 원소 하나만 있는 배열은 이미 정렬된 것이므로 23을 앞에 붙이나 뒤에 붙이나 결국 최종 배열은 정렬 가능한 상태가 된다.
(123 or 231)
그런데 이 때, 순서를 바꾸게 되면서 원소 간의 대소 변화도 짝수만큼 변화하게 된다. 이 값을 명확하게 하기 위해서, count 라는 변수를 사용했고, 이 변수는 각 원소와 그 뒤 원소들을 비교하여 해당 인덱스의 원소가 큰 경우의 수를 합한 값이다.
- 123의 경우, 이미 정렬이 완료되어 있으므로 count 는 0 이 된다.
- 312의 경우, count 는 2가 된다.
즉, 이미 정렬이 되어 있는 배열의 경우 count 값이 0이 되고, 그 상태에서 2개의 원소들을 움직일 때마다 count 는 짝수만큼 변화하게 되므로, count 가 짝수인 경우에만 정렬 가능한 상태라고 말할 수 있는 것이다.
이에 따라서 count 값을 구하고 그 경우가 짝수일 때 YES, 홀수일 때 NO 를 반환하도록 구현하면 해결이 된다.
※ 기존 블로그 글: https://thinkpro.tistory.com/162 (2020-07-14)