https://www.acmicpc.net/problem/34030
문제요약
- 20만개 수가 주어짐(1~10^9)
- 연산1 : 연속한 두 수 합이 홀수면 교환 가능
- 연산2 : 연속한 두 수 합이 짝수면 교환 가능
- 연산1만 써서 오름차순 정렬이 될까?
- 연산2만 써서 오름차순 정렬이 될까?
접근법
- 뭐가 되었든 순서가 바뀐 애들은 서로 교환이 되어야함
- 예를들어 10 ....... 2 라면 언젠가 (10,2)가 교환이 되어야함
- 같은숫자가 있으면 굳이 교환하지 않아도 됨
- 예를들어 ....7 .. 7 ... 2 .... 이면 (7,7)은 교환하지 않아도 됨
- 어떤 숫자의 오른쪽 부분에서 어떤 숫자보다 작은 숫자들을 대상으로 판단
- 그 숫자들은 결국 왼쪽으로 옮겨져야하고, 결국 교환을 하기때문에
- 그 숫자들의 값보다 홀/짝인지가 중요
- 구간트리로 접근하는 것처럼 보일 수도 있으나 정렬로 해결 가능
- 숫자가 작고, 좌표가 왼쪽인 숫자부터 판단 시작
- 그 숫자의 오른쪽에 그 숫자보다 작고 홀/짝이 있는지 판단하면 : 연산1, 연산2 실패 여부를 판단할 수 있음
- 홀/짝 판단은 어떻게?
- A[t] : t 위치의 오른쪽에 홀수/짝수가 있다? 없다를 알려주는 배열
- A 배열을 만드는 방법?
- 아까 정렬한 결과의 순서대로 숫자를 처리
- 숫자가 홀/짝이면 숫자의 위치부터 왼쪽을 모두 있음으로 처리
- 그런데 어짜피 항상 왼쪽 끝까지는 가지 않음
- 다른 숫자가 홀/짝을 채웠으면 더 채울 필요가 없음
- 즉 A 배열은 O(N) 시간으로 생성이 됨
newbieski