[BOJ-JS] 8120번 - Coding of Permutations

8120번: Coding of Permutations (acmicpc.net)

8120번: Coding of Permutations

 

세그트리 태그로 검색해서 찾은 문제였는데, 정작 세그트리를 사용하지 않고 훨씬 쉽게 풀었다. 기본 아이디어는 시퀀스 B가 주어졌을때, B의 뒷 숫자부터 차례대로 읽으면서 A의 뒷 숫자를 확정해나가는 것.

 

예를 들어, B = (0, 0, 1, 0, 2, 0, 4)로 주어졌다고 하면

- B의 제일 뒷 숫자는 4다. 이 말은, 맨 뒷 숫자보다 큰 앞 숫자들이 4개 있다는 것. 1, 2, 3, 4, 5, 6, 7 중에서 빨간 색으로 표시한 숫자가 앞에 와야 하므로, A의 제일 뒷 숫자는 3으로 확정.

- B의 그 다음 뒷 숫자는 0이다. 3은 이미 썼으므로, 1, 2, 4, 5, 6, 7 중 0개의 숫자가 선택한 숫자보다 커야 한다. 즉, 7.

- B의 그 다음 뒷 숫자는 2이다. 3, 7은 이미 썼으므로, 1, 2, 4, 5, 6 중 2개의 숫자가 선택한 숫자보다 커야 한다. 즉, 4.

...

이와 같은 과정을 계속 반복하면, A = (1, 5, 2, 6, 4, 7, 3)가 된다.

이 과정을 반복하던 중 문제가 생기면, 예를 들어, 남은 숫자는 3개인데, 앞에 4개의 숫자가 있어야 한다거나 하면, 이런 A를 찾는 것은 불가능하므로 NIE 출력.

 

아래의 구현에서는 splice를 써서 남은 숫자 배열을 줄여나갔는데, 이는 성능상 그리 좋은 방법은 아니다. 하지만 이 문제에서 B의 크기가 최대 30000이어서 문제 없이 통과했다.

 

구현 난이도는 매우 낮아보였는데, 비슷한 다른 문제의 난이도가 골1로 되어있다는 다른 기여한 분들의 글을 보고 나도 문제 난이도를 골1로 평가했다. 글을 작성한 시점에서는 세그트리 풀이를 쓴 분들이 플5를 주었고, 다른 분들이 골1을 주어서 그 사이에 있는 골3으로 난이도가 책정되어 있었다.

[a,...b]=(0+require('fs').readFileSync(0)).split`
`.map(i=>+i)
x=Array(a).fill(0).map((e,i)=>i+1)
r=[]
for(i=a-1;i>=0;i--){
  if(b[i]>=x.length)break
  y=x.length-1-b[i]
  r.push(x[y])
  x.splice(y,1)
}
r.reverse()
console.log(i==-1?r.join('\n'):'NIE')