[C++] 백준 1138번 풀이 ( 한 줄로 서기 )

- 문제 (1138번) : 한 줄로 서기

• 링크 : https://www.acmicpc.net/problem/1138

• N 명의 사람을 기준으로 왼쪽에 자신보다 큰 사람이 몇명 서있는지 주어졌을 때 키가 1부터 N 인 사람들을 한줄로 세우는 프로그램 구현.

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 사람의 수 N 입력
• 둘째 줄에 키가 1인사람부터 차례대로 왼쪽에 자신보다 큰 사람이 몇명 서있는지 입력

[ 출력 ]

• 줄을 선 순서대로 키를 출력

---

- 문제 풀이

• 이 문제는 간단하지만, 논리가 생각보다 생각하기 힘들었다.

  왼쪽에 자신보다 키가 큰 사람이 서있으면 되므로, 키가 작은 사람부터 세울 때 키가 큰 사람이 설 수 있는 공간만 마련해주면 된다.

  즉, 키가 작은 사람부터 줄을 세우되, 자신보다 키가 큰 사람이 설수있는 빈 공간을 남겨두고 줄을 서면 된다.

  ex) 4명의 사람이 있고, 각각 2 1 1 0 의 사람이 왼쪽에 서 있을 때

  • 0인 경우 비어있는 위치 즉, 사람이 설 수 있는 공간

  • 1의 경우 => 0 0 1 0 으로 서면 됨.
  • 2의 경우 => 0 2 1 0 으로 서면 됨.
  • 3의 경우 => 0 2 1 3 으로 서면 됨.
  • 4의 경우 => 4 2 1 3 으로 서면 됨.

• 위와 같이 코드를 구현하면 쉽게 문제가 해결된다.

  구현같은 경우는 아래와 같은 방법으로 구현했다.

  • N 까지 반복문을 돌며 한명씩 줄을 세움.
  • 어떠한 사람이 서야하는 위치를 구할때는 줄을 세울 배열을 돌며 0의 개수가 입력받은 자신보다 키가 큰 사람의 수와 같을 때까지 index 를 증가시키며 위치를 찾았다.
  • 위치를 찾아 전부 줄을 세웠다면 줄을 세운 순서대로 키를 출력하면 종료.

• 이 문제는 자신보다 키가 큰 사람의 자리만 남겨두고 그 후에 본인을 줄을 세운다는 논리만 바로 생각했다면 금방 해결되는 문제였다.

---

- 최종 코드

#include <iostream>
#define N_MAX 10
using namespace std;

int arr[N_MAX] = {0, };

int main() {
    /* the number of people */
    int N = 0; 
    cin >> N;

    /* input info about standing */
    for(int i = 0; i < N; i++) {
        int temp = 0;
        cin >> temp;

        int index = 0; /* temp 가 저장될 위치 (index) */
        int count = 0; /* 앞에 나보다 키가 더 큰 사람이 설 자리 수 */
        int idx = 0; /* 배열을 돌 때 값을 비교하는 index */

        /* temp(나) 앞에 더 큰 사람이 서고 난 후 나의 위치 구하기 */
        while(count != temp) {
            if(arr[idx] == 0) {
                index++;
                count++;
                idx++;
            } else {
                index++;
                idx++;
            }
        }

        while(arr[index] != 0){ // 이미 이 위치에 어떠한 값이 저장되어있으면 다른 위치에 저장
            index++;
        }
        arr[index] = i+1;
    }

    /* print result */
    for(int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    printf("\n");
    return 0;
}