[BOJ][Python] 백준 9011번 - 순서

문제 링크: https://www.acmicpc.net/problem/9011

9011번: 순서

---

문제 풀이

구현

 

R 수열의 뒷부분부터 처리하면 어렵지 않다.

처리는 R[i]+1을 중심으로 하면 된다. 가령 R수열의 마지막은 오른쪽 부분이 없고 왼쪽에는 자신보다 작은 수의 개수이므로 R[i]+1로 자명하다. 그렇다면 중복 혹은 자신보다 작은 수가 오른쪽에 있는 경우는 어떻게 해야할까?

 

예제 1을 살펴보자

먼저 가장 뒷 부분을 채워준다. 여기는 아무것도 예외 처리 할 부분이 없다.

여기서 문제가 생기는데, 오른쪽에는 본인보다 작은 수가 포함되어 있기 때문이다. 그래서 이런 경우는 +1을 해준다.

 

여기도 마찬가지로 7이 중복되어 있으므로 8로 만들어주자.

 

이 부분은 1, 2가 3보다 작으므로 5가 된다.

 

이 부분의 처리가 제일 까다롭다고 생각하는데, 1은 이미 있으므로 2로 만들었지만 또 2가 중복되어 있으므로 3을 만들어줘야 한다. 따라서 정렬을 이용해서 매순간 확인을 해줘야 한다. 이후 뒤도 마찬가지로 계산해주면 된다.

 

따라서 최종 결과는 다음과 같다.

 

마지막으로 IMPOSSIBLE이 나오는 경우는 중복 혹은 자신보다 작은 수가 있어서 +1을 하는 과정을 거치면서 n보다 큰 숫자가 생기는 경우가 있다. 이때는 불가능한 수열이므로 반복문을 종료해주고 IMPOSSIBLE을 출력해주면 된다.

코드