1138 한 줄로 서기

문제 설명

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다. 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

문제 풀이

나의 접근 방법

키에 대한 오름차순으로 섰을 때의 내 위치 + 나보다 큰 사람이 앞에 몇 명 있는지 위치에 선다. 그러나 내 뒤에 나보다 작은 사람이 섰다면 내 뒤에 있는 작은사람 수 만큼 앞으로 옮겨선다. 그리고 앞으로 옮겨서고 있는 과정에서 작은사람을 만난다면 그 수 만큼 앞으로 옮겨선다. 이 과정을 코드로 표현하면 다음과 같다.

코드 설명

for(let i = 0; i < n; i++) {
  let tempCnt = 0;
  for(let j = n-1; j >= i+list[i]-tempCnt; j--){
    tempCnt += result[j] ? 1:0;
  }
  result[i+list[i]-tempCnt] = i+1;
}

i for문을 돌면서 입력으로 들어온 배열의 원소를 하나씩 탐색한다. j for문에서는 배열의 뒤쪽부터 탐색하며 tempCnt라는 변수를 업데이트 해준다. tempCnt에는 내 뒤에 있는 나보다 작은 사람의 수를 구해서 저장한다. j for문의 범위를 j >= i+list[i]-tempCnt;한 이유는 나보다 작은사람이 내가 서야 할 위치 뒤에 있어서 앞으로 옮겨서는 도중에 나보다 작은 사람을 만날 수 있기 때문이다. 위에서 구한 tempCnt를 바탕으로 i+list[i]-tempCnt위치에 줄을 세운다.

문제 후기

조금만 곰곰히 생각하면 간단한 문제인데 성급하게 예제 끼워맞추기 식으로 푸니까 헷갈렸다. 블로그에 포스팅 하려고 코드 설명을 작성하면서 차분히 생각해보니 이전 내 코드의 개선점이 보여서 조금 수정했다. 구현 문제는 바로 코드를 작성하기보단 꼼꼼하게 생각한 후 구현하도록 해야겠다.