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

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

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

줄 세우기

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

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

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

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

들어오는 값

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

예)

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);

from http://forgottenknowledge.tistory.com/132 by ccl(A) rewrite - 2021-09-26 15:27:47