[좋은 문제]백준 1138: 한 줄로 서기 - javascript (구현)

개인적으로, 구현 알고리즘으로 되게 좋은 문제라고 생각든다 ! 

 

문제 출처 

https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

예제 입력 1 복사

4
2 1 1 0

예제 출력 1 복사

4 2 1 3

예제 입력 2 복사

5
0 0 0 0 0

예제 출력 2 복사

1 2 3 4 5

예제 입력 3 복사

6
5 4 3 2 1 0

예제 출력 3 복사

6 5 4 3 2 1

예제 입력 4 복사

7
6 1 1 1 2 0 0

예제 출력 4 복사

6 2 3 4 7 5 1

 

문제 풀이 힌트 

1) 큰 틀 먼저 잡고 가자 

for(let i=1; i<n+1; i++){

             for(let j=0; j<n; j++){

      }

}

- 큰 반복문 i는 사람 키 순대로 뽑는다! => i자체가 그 i키를 가진 사람을 뽑은 것! 

- 작은 반복문 j는 뽑은 너 자리를 한번 우리가 찾아보자 !  =>result 빈 배열 자리 j를 돌면서 마땅한 조건에 i사람을 넣어줄 것임 ! 

2) 마땅한 조건이 무엇인가?

- 문제에서 주어진 왼쪽 사람 수와 내가 지나쳐온 result 자리 수가 같아야 할 것 ! 

3) 내가 지나쳐온 result 수는 어떻게 구하는가?

- 이미 result 안에 다른 숫자가 들어가 있다면 나보다 작은 숫자이니, count 해주지 않는다. (result 배열 돌면서 count는 나보다 큰 사람 수 세는 것)

- result 를 돌 때 0으로 채워져있다면 아직 순서가 오지 않은 나보다 큰 사람이 들어갈 예정이니, count를 해준다. 

4) 결론 

- 내가 지나쳐온 cnt 값 === 문제에서 주어진 왼쪽 사람 수 값 

- result 그 자리가 비어있을 때 

=> 두 조건이 만족하면 그 때 result[j] 자리에 i를 배치시킨다. 

 

정답 풀이 코드 

function solution(n,list){
  let result = new Array(n).fill(0); 
    for(let i=1; i<n+1; i++){
        let temp = list[i-1]; 
        let cnt = 0; 
        for(let j=0; j<n; j++){
            if(temp === cnt && result[j] === 0){
                result[j] = i; 
                break; 
            }else if(result[j] === 0){
                cnt++; 
            }
        }
    }
    let r = result.join(" "); 
    console.log(r)
}

const readline = require("readline"); 
const rl = readline.createInterface({
    input: process.stdin, 
    output: process.stdout,
}); 
let input = []
rl.on("line", function (line){
    input.push(line)
}).on("close", function (){
    let n = parseInt(input[0]); 
    let list = input[1].split(' ').map((el)=> parseInt(el)); 
    solution(n, list); 
    process.exit(); 
});

의사 코드 추가 

function solution(n,list){
  let result = new Array(n).fill(0); //사람 키대로 줄 세운 배열 
    for(let i=1; i<n+1; i++){ //i는 사람 키다
        let temp = list[i-1]; //i 키를 가진 사람 왼쪽 사람 수 
        let cnt = 0; 
        for(let j=0; j<n; j++){ //사람마다 result 배열을 돌면서 알맞은 곳에 넣어줄 것이다.
            if(temp === cnt && result[j] === 0){ //내 왼쪽 사람 수 = 내가 지나쳐온 result 자리 & 내가 들어갈 자리가 비어있어야 함
                result[j] = i; //i 키를 가진 사람이 들어간다. 
                break; 
            }else if(result[j] === 0){ //키가 작은 순대로(i)돌기 때문에 0으로 적혀 있는 수가 나보다 큰 사람 수일 것.  
                cnt++; 
            }
        }
    }
    let r = result.join(" "); 
    console.log(r)
}

const readline = require("readline"); 
const rl = readline.createInterface({
    input: process.stdin, 
    output: process.stdout,
}); 
let input = []
rl.on("line", function (line){
    input.push(line)
}).on("close", function (){
    let n = parseInt(input[0]); 
    let list = input[1].split(' ').map((el)=> parseInt(el)); 
    solution(n, list); 
    process.exit(); 
});