[ 백준 / G5 / 파이썬 Python ] 9011번 순서

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

9011번: 순서

 

코드

---

import sys
input = sys.stdin.readline # 시간을 4ms 줄여줌ㅋㅋ

def solution(n, arr):
    answer = [0] * n
    v = list(range(1,n+1))
    for i in range(n-1,-1,-1):
        to = arr[i]
        if to >= len(v): return False
        answer[i] = v[to]
        v.pop(to)
    return answer

for _ in range(int(input())):
    if answer := solution(int(input()), list(map(int, input().split()))): print(*answer)
    else: print("IMPOSSIBLE")

 

풀이

---

이 문제가 골드5에 어울리지 않는 것인지, 내가 골드5도 못 풀 정도로 약한 녀석인지 몰라도 정말 푸는데 오래 걸렸다.

한 탐색안에서 모두 다 해결할 수 있을 것 같은데 자꾸 한계에 부딪히고 실패하고 그래서 못하다가 어느 한 아이디어를 생각해내서 성공했다.

1등도 찍었다..후후

 

아이디어는 다음과 같다.

• n까지의 숫자를 담은 배열 v를 생성한다.
• 입력받은 배열 arr을 역순으로 탐색하면서 뒤부터 정답을 채워 나간다.
• arr에 있는 값을 인덱스 삼아서 v의 값을 꺼낸다.
  
  • v배열의 값은 초기에는 1~n까지 있지만 탐색 중간 과정에서 v[i] == i 라는 보장은 없다.
  • 왜냐하면  정답 배열을 채울 때 v에서 pop해서 채우기 때문이다.
• arr의 값이 v의 인덱스를 넘어가면 정답을 도출할 수 없으므로 IMPPOSIBLE을 출력한다.

이런 방법이 가능한 이유는 다음과 같은 조건들이 있기 때문이다.

1. answer[i]는 내 앞의 나보다 작은 수의 개수(arr[i])+1보다 크거나 같다.
2. answer[i]가 arr[i]+1보다 큰 경우는 내 뒤에서 이미 나보다 작거나 같은 수가 pop된 경우이다.

첫 번째 테스트 케이스의 로그를 찍어보면 다음과 같다.