[백준 20309] 트리플 소트 [Python]

문제

알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 "트리플 소트"는 다음과 같이 동작한다.

• 배열에서 연속한 위치에 있는 세 원소를 임의로 고른다.
• 세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 a,b,c이면 뒤집은 뒤에는 c,b,a가 된다.
• 배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다.

하지만 윤이는 트리플 소트로 모든 배열을 정렬할 수 없다는 사실을 깨닫고 실망했다. 1부터 N까지의 정수가 한 번씩 등장하는 배열이 주어졌을 때, 트리플 소트로 정렬할 수 있는지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄에 배열의 크기를 나타내는 정수 N이 주어진다.

두 번째 줄에 배열의 원소가 공백을 사이에 두고 순서대로 주어진다.

출력

트리플 소트로 주어진 배열을 오름차순으로 정렬할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

---

풀이

최대 길이가 3e5인 배열을 "트리플 소트" 했을 때 정렬이 되는지 확인하는 문제다.

Bubble 정렬과 정렬 방식이 유사하지만, 실제 정렬을 하면 시간 초과가 발생한다.

정렬 과정을 살펴보자.

" a b c d e "

" c b a d e "

홀수(1, 3, 5)는 순서에 관계없이, 홀수 위치에 존재하면 정렬이 가능한다. 이는 짝수(2, 4)또한 성립한다.

문제를 단순화해 arr[i]와 (i + 1)가 동일한 홀수 또는 짝수인지 확인하면 된다.

---

소스코드

보기

---

출처

https://www.acmicpc.net/problem/20309