백준 문제풀이 : (1138) 한 줄로 서기 - C/C++

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

1138번: 한 줄로 서기

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Silver 2	구현

 

 

문제

 

 

풀이

4명의 사람이 줄을 선다면 각 사람들의 키는 1부터 4까지이고, 5명의 사람이 줄을 선다면 각 사람들의 키는 1부터 5까지이다. 이런 식으로 1부터 N까지의 키를 가진 N명의 사람이 문제에서 주어진 규칙에 따라 줄을 섰을 때 왼쪽부터 순서대로 출력하는 문제이다. 

 

문제에서는 키 1인 사람부터 키 N인 사람까지 순서대로 자신의 왼쪽에 자기보다 큰 사람이 몇 명있는 지 말해주며, 이 대답이 문제에서는 TC로 주어진다. 

 

따라서 아래의 세 단계로 풀이 규칙을 만들 수 있다.

 

1. 키가 1인 사람부터 키가 N인 사람까지 각자 왼쪽에 자신보다 더 큰 사람이 몇 명 서있는 지 순서대로 얘기한다.

2. 키 1인 사람보다 작은 사람은 없기 때문에, 키 1인 사람이 말하는 수는 곧 자신이 줄에 선 위치가 된다.

3. 키 2인 사람부터는, 그가 대답한 수를 tall이라고 할 경우 이미 배정된 위치를 제외하고 tall 번째 자리에 배정하면 된다.

 

문제에서 주어진 테스트케이스로 예를 들어보자. 줄을 선 사람의 수는 4명이므로 키가 1,2,3,4인 사람이 줄에 서있을 것이다. 키 1인 사람의 왼쪽에는 자신보다 큰 이가 2명 있으므로, 키 1인 사람의 위치는 2번째 위치이다. (0번째 자리부터 시작)

 

키 2인 사람은 자신의 왼쪽에 자신보다 큰 이가 1명 있다고 말했다. 0번째 자리, 1번째 자리 둘 다 비어있으므로 키 2인 사람의 위치는 1번째 위치이다. 

 

키 3인 사람도 자신의 왼쪽에 자신보다 큰 이가 1명 있다고 말했다. 따라서 1번째 자리에 배정해야하는데, 1번째 자리에는 이미 키가 2인 사람이 들어가있다. 따라서 2번째 자리로 이동해 배정하려고 보면, 또 2번째 자리에는 이미 키가 1인 사람이 들어가있다. 따라서 이미 사람이 서있는 1번째 자리, 2번째 자리를 제외하고 1번째인 자리에 키가 3인 사람을 배정해준다. 자리는 0번부터 세고 있으므로, 줄의 0번째 자리가 0번째, 3번째 자리가 2번째가 되어 키 3인 사람은 3번째 자리에 배정된다. 

 

마지막으로, 키 4인 사람은 왼쪽에 자신보다 큰 이가 0명 있다고 말했따. 따라서 0번째 자리에 4를 배정하려고 보면, 0번째 자리에는 아직 아무도 없다. 따라서 키 4인 사람의 위치는 0번째이다. 

 

이렇게 키 1인 사람부터 이미 배정된 자리를 제외해가며 순서를 찾아주면 정답을 최대 연산 횟수 100회 이내로 찾을 수 있다. (N의 최댓값이 10이므로.) 

 

위 규칙을 실제 코드에서는 줄에서의 실제 순서를 pos라는 변수로, 이미 임자가 있는 자리를 제외한 가상 순서를 count라는 변수에 담아 구현했다.

 

 

코드 작성

#include <iostream>

using namespace std;
int peo[10]; //static 존에 배열을 만들었으므로 모든 값은 0으로 초기화.

int main() {
    int N;
    scanf("%d", &N);
    
    for (int n=1 ; n<=N ; n++) { 
    // 키 1인 사람부터 N인 사람까지 순서대로 자리 배정
        int tall; // 키 n인 사람 왼쪽에 그보다 큰 이가 몇 명 있는지.
        scanf("%d", &tall); 
        
        for (int pos=0, count=-1 ; pos<N ; pos++) { // 자리 배정해주는 부분
            if (peo[pos]<=0) count++; 
            //현재 위치가 빈 자리가 아닐 경우에만 세어준다.
            if (count==tall) { peo[pos] = n; break; }
            //빈 자리가 아닌 위치만 센 순서가 tall과 일치하면 그 위치에 배정
            //하고, 반복문 탈출.
        }
    }
    
    for (int n=0 ; n<N ; n++) {
        printf("%d ", peo[n]);
    }
}

 

 

END.