[C++] 백준 1138번 한 줄로 서기

첫번째줄에는 사람 수를 받고 두번째줄은 왼쪽에 자신보다 큰 사람이 몇명이 있는지를 나타냅니다.

두번째줄에 차례대로 키가 1부터 2, 3 .... 으로 증가합니다.

예제에는 4명이 입력되었으며 키가 1, 2, 3, 4 인 사람이 있다고 볼 수 있습니다.

키가 1인 사람은 왼쪽에 자신보다 큰 사람이 2명

키가 2인 사람은 왼쪽에 자신보다 큰 사람이 1명

키가 3인 사람은 왼쪽에 자신보다 큰 사람이 1명

키가 4인 사람은 왼쪽에 자신보다 큰 사람이 0명 있으므로

4 2 1 3 순으로 서있습니다.

 

3가지 절차를 통해 문제를 풀었습니다.

1. 왼쪽큰인원 +1명을 하게 되면 큰 인원을 제외한 자리를 찾을 수 있습니다.

2. 왼쪽에 작은 인원이 몇명 있는지 체크를 하면서 그 만큼 더 오른쪽으로 이동합니다.

3. 이미 자리에 인원이 있으면 그 오른쪽으로 이동해서 있는지 확인하고 없으면 위치에 자리합니다.

 

#include <iostream>
using namespace std;

int height[10000];
int leftPeople[10000];
int people[10000];

void init(){
   for(int i=0; i<10000; ++i){
      height[i] = i+1;
      leftPeople[i] = -1;
      people[i] = -1;
   }
}

int main(int argc, char *argv[])
{
   init();
   int cycle, index, count, check;
   cin >> cycle;
   for(int i=0; i<cycle; ++i){
      count = 0;
      cin >> leftPeople[i];
      check = leftPeople[i];
      for(int j=0; j<check; ++j){
         if(people[j]!=-1 && people[j] < height[i]){
            check++;
            count++;
         }
      }
      index = leftPeople[i]+count;
      
      while(people[index]!=-1){
         index++;
      }
      people[index]=height[i];
      index = 0;
   }
   for(int i=0; i<cycle; ++i){
      cout << people[i] << " ";
   }
   return 0;
}