9) 백준 1138 - 한 줄로 서기

<문제>

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

1138번: 한 줄로 서기

새벽에 풀어서 그런지 머리가 안돌아갔던 문제 ....ㅠ

 

<코드>

#include <iostream>

using namespace std;

int main(void) {
	int p_bef[11] = {0, };
	int p_aft[11] = {0, };
	int N;
	cin >> N;
	
	for(int i = 1; i <= N; i++) {
		cin >> p_bef[i];
	}
	
	for(int i = 1; i <= N; i++) {
		int cnt = 0;
		int j = 0;
		while(cnt != p_bef[i]) {
			if(p_aft[j] == 0) {
				cnt++;
			}
			j++;
		}
		while(p_aft[j] != 0) j++;
		p_aft[j] = i;
	}
	
	for(int i = 0; i < N; i++) {
		cout << p_aft[i] << " ";
	}

	return 0;
}

방법은 간단했다.

1번 (가장 작은것) 부터 시작해서 왼쪽에 그 수 보다 큰게 몇 개 있는지 체크해주면 된다.

문제 예제 같은 경우, 1번의 왼쪽에는 2개가 있으므로, p_aft[2]에 1을 넣어줬다.

2번의 왼쪽에는 1개가 있으므로, p_aft[1]에 2를 넣어줬다.

그런데 3번의 왼쪽에는 1개가 있는데 p_aft[1]에 3을 넣으려고 보니까 2가 이미 자리를 잡았다. 이럴때, while문을 돌려서 자리를 계속 찾는다 (j값을 키워가면서...)

 

그런데 여기서 또 생각해줘야 할 문제는 앞에 이미 들어간 숫자들이 문제가 되기도 한다. 예를 들면 입력값이

10

5 3 8 .....

이라면 p_aft[8]에 3을 넣으려고 보니까 왼쪽에 1과 2가 있다. 이건 3보다 작은 수들로, p_aft[8]에 3을 넣으면 왼쪽에 3보다 큰 수들이 6개 있게 되므로 조건에 맞지 않는다. 이를 처리하는 과정이 처음 나오는 while문이다. p_aft배열을 index=0부터 확인하여 이미 수가 담겨져 있을 경우 그냥 카운팅하지 않는다.

예시로 보면, 1, 2는 카운팅 되지만, 3에는 1이 이미 담겨 있으므로 패스, 4는 카운팅, 5는 2가 담여져 있으므로 패스.....

 

(... 이해 되겠지..ㅎ....)

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

자신감이 조금씩 붙는듯 하다..!!!!(쉬운것만 해서 그런가 ㅎㅎ)