[맛있는물회] <알고리즘> 1138번 "한 줄로 서기"

오랜만에 다시 시작하는 알고리즘 문제라 그런지 엄청 헤맸다....

전형적인 그리디 문제이다.

왜 처음에 접근한 방식이 안 풀린지 아직도 잘 모르겠다. 한번 더 점검해보고 다시 생각해봐야겠다.

 

이 문제는 먼저 Input 값이 정렬되어있다는 점에 초점을 맞추어야한다.

키가 가장 작은 "1" 부터 "N"까지 순서대로 각 자신의 왼쪽에 자신보다 키가 큰 사람의 수를 보여준다.

(키가 같은 사람은 없음)

 

1. 틀린 접근법

처음에 생각한 방식은 "1"이 주어짐으로써 1번의 위치를 알 수 있다.

#include <iostream>
 
using namespace std;
 
 
 
int main(void) {
 
    int n,i,pos1,pos2,front=0, rear=0;
 
    int arr[11] = { 0, };
 
    cin >> n;
 
    cin >> pos1;
 
    front = pos1; rear = pos1;
 
    arr[front] = 1;
 
    for (i = 2; i <= n; i++) {
 
        cin >> pos2;
 
        if (pos1 != pos2)
 
            arr[--front] = i;
 
        else
 
            arr[++rear] = i;
 
        pos1 = pos2;
 
    }
 
    for (i = 0; i < n; i++)
 
        cout << arr[i] << " ";
 
    return 0;
 
}

 

(N이 4라고 가정)

Input :

4

2 2 1 0

=>

□ □ □ □ 에서 처음에 1이 가장 작으므로 왼쪽에 2명의 사람이 있다는 것이므로 1번의 위치는 알 수 있다.

 

□ □ 1 □ 

이제 여기서 1번의 Index를 바탕으로 나는 front와 rear를 잡았다.

if) 2번째의 값이 주어졌을 때 만약 1번의 값과 같다면 (2번의 값도 2), 1의 rear 즉 1번의 뒤쪽으로 가야한다고 생각했다.

else if) 만약 2번째의 값이 1번의 값보다 작다면 1의 왼쪽 즉 front로 가야한다고 생각했다.

 

이런 방식으로 쭉 접근하면 값은 나오는 것 같았는데 접근 방식이 잘못된 것같다. 아직 반례를 못찾았는데

*혹시 왜 틀린지 아시는 분 말씀해주시면 감사하겠습니다!!!

 

 

2. 정답

#include <iostream>
 
using namespace std;
 
 
 
int main(void) {
 
    int n, i, j, pos;
 
    int arr[11] = { 0, };
 
    cin >> n;
 
    for (i = 1; i <= n; i++) {
 
        cin >> pos;
 
        for (j = 0; j < n; j++) {
 
            if (arr[j] == 0 && pos == 0) {
 
                arr[j] = i;
 
                break;
 
            }
 
            else if (arr[j] == 0)
 
                pos--;
 
        }
 
    }
 
    for (i = 0; i < n; i++)
 
        cout << arr[i] << ' ';
 
    return 0;
 
}

혼자 못풀었다는 부분에 정말 큰 충격을 받았지만,,,

조금 도움을 받아서 다시 생각한 뒤 풀었다.

처음에 줄 배열을 0으로 초기화를 한다.

 

처음에 말한 것 처럼 키가 제일 작은 1부터 순서대로 값이 주어진 다는 것에 초점을 맞추어야한다.

따라서 배열에 0이라는 값이 들어있는 부분은 분명히 자신보다 키가 크다는 것이고, 넘어갈 때마다 count를 해주어야한다.

 

따라서 for 문을 돌리면서 0인 부분은 분명히 자신보다 키가 크므로 count를 하면서 넘어간다.

count를 다 세었으면 이제 값을 넣어야한다. 값을 넣을 때 자신보다 키가 작은 친구가 있는 부분에 들어가면 안되기 때문에 배열 값이 0인 곳에 들어가면 끝!

 

다시생각하면 간단한 문제인데 처음 접근법이 왜 틀린지 다시 생각해봐야겠다.