BOJ 9011 - 순서
이런 문제 많이 안풀어봤으면 당황할 수 있는데, 부분 순서라는 키워드에 너무 집중하지 말고 입력 데이터를 들여다보면 쉽게 풀 수 있다.
접근 방법
다음 입력 데이터를 끝 부분부터 살펴보자.
10
0 0 0 2 0 1 6 7 6 9
숫자가 10개인데, 제일 끝에 입력 받은 애가 9다. 그럼 이 앞에 있는 숫자가 9개니까 전부 이 위치에 들어갈 숫자보다 작아야된다는 거고 10번째 숫자인 10이 들어가야 한다.
여기서, 현재 위치에 들어갈 수 있는 숫자 리스트를 ArrayList로 관리하는 아이디어를 떠올릴 수 있었다. ArrayList에는 1부터 n까지 순서대로 넣어놓고 입력 데이터를 뒤에서 앞으로 순회해서, 각 순서를 ArrayList에 대입하고 하나씩 remove 해주면 된다.
예시를 들어보겠다.
ArrayList 처음 상태 : [1,2,3,4,5,6,7,8,9,10]
입력 데이터의 10번째 값 : 9
Stack.push(ArrayList.remove(9)); // 9번 인덱스에 있는 10이 제거
ArrayList 상태 : [1,2,3,4,5,6,7,8,9]
입력 데이터의 9번째 값 : 6
Stack.push(ArrayList.remove(6)); // 6번 인덱스에 있는 7이 제거
ArrayList 상태 : [1,2,3,4,5,6,8,9]
입력 데이터의 8번째 값 : 7
Stack.push(ArrayList.remove(7)); // 7번 인덱스에 있는 9가 제거
...
불가능한 경우는 IMPOSSIBLE 출력해줘야 하는데, 입력 받은 순서값보다 그 시점에서의 ArrayList size가 작은 경우 불가능한 것으로 처리해주면 된다.