알고리즘 :: 줄 세우기, 병합정렬 응용

알고리즘 공부하며 배운내용

 

 

줄 세우기

가게에서 경품권을 줄 선 순서대로 나눠줬다.

경품권이 잘못돼서 다시 나눠줘야 되는데, 본인들이 몇 번째였는지 기억을 못한다.

 

근데, 모든 사람이 본인 앞에 키가 큰 사람이 몇 명 있었는지 기억한다.

이를 이용해서 어떤 순서로 서 있었는지 알아보자

 

 

들어오는 값

키가 작은 사람부터 자신보다 키가 큰 사람이 몇 명 있었는지 입력

예)

3 1 1 0

제일 키가 작은 첫 번째 사람 앞에는 3명의 키 큰 사람이 있었다.

그다음 키가 작은 사람 앞에는 1명의 키 큰 사람이 있었다.

. . .

 

 

구하고 싶은 값

키가 작은 사람 순서대로 1, 2 ... n 번호가 있다면,

처음 어떻게 서 있었는지 출력

예)

4 2 3 1

제일 작은 사람 앞에 4, 2, 3 번째 사람들이 있었다.

그 다음 작은 사람 앞에 4번이 있었다.

 

 

핵심 포인트

앞에서 배운 병합정렬을 여기에 쓰일 줄이야!!

뒤에서부터 키가 큰 순으로, 자기보다 키가 큰 사람만 체크하면 된다.

 

 

코드

병합정렬 비스므리한 코드를 사용했다.

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 line.txt로 저장했다
let fs = require('fs')
let input = fs.readFileSync('line.txt').toString().split(' ')

let order = []

// 뒤에서 부터 실행하고, 자기보다 키 큰 사람만큼 인덱스를 옮겨서 끼어 넣는 방식
for(let i = input.length - 1; i >= 0; i--) {
  order = [...order.slice(0, +input[i]), i+1, ...order.slice(+input[i])]
}

// 출력 결과 처럼 보이기 위한 join
order = order.join(' ')
console.log(order);