[BOJ 9078] 이웃하는 두 수만 정렬하는 문제

문제 출처: 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

설명

이미 정렬 가능한 배열 = A (예를 들어 12)가 있다고 가정했을 때, 이후에 원소를 2개 추가한다고 했을 때, 그 추가되는 두 개의 숫자도 이미 정렬되어 있어야만 새로운 배열의 정답이 YES가 됩니다.
(예를 들어 12 배열에 3,4를 추가한다면->1234, 3412, 3124, 즉 3과 4는 어떤 곳에 위치하든 정렬된 상태여야만 합니다)

 

여기서 count 변수를 각 배열의 원소 뒤에 오는 다른 원소의 크기 비교를 한 값을 전부 합한 sum값이라고 합시다.
1. 1234의 경우
34가 뒤에 추가되었으나 count가 변하지 않음.
2. 3412의 경우
34가 앞에 추가되었으므로 count가 +4 (3이 12보다 크므로 +2, 4가 12보다 크므로 +2해서 총 +4)
3. 3124의 경우
3이 앞에 추가되었으므로 count가 +2 (3이 12보다 크므로 +2, 4는 뒤에 왔으므로 count 변화 없음)

즉, 기존에 이미 정렬 가능한 배열에서 새로운 원소를 추가시킬 때마다 count의 변화는 짝수로 변하게 됨.

참고로 위 사례에서는 12와 같이 짝수개의 원소 배열부터 시작했지만, 123과 같이 홀수개의 원소 배열에서 출발하더라도 같은 논리를 도출하게 됨. 또한, 태초에 12나 123같은 정렬된 배열에 대해서 count값은 0을 가지므로 어떠한 길이의 배열도 count가 짝수여야 YES가 됨.

 

블로그 백업중... https://jeongmincha.github.io/posts/00007/ 로 이동