[ACM-ICPC][BOJ] 9011 - Order

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 문제인 'Order'를 다뤄보겠습니다.

문제를 읽었을 땐 되게 어렵다고 느꼈지만, 간단한 아이디어로 구현할 수 있어서 금방 해결한 문제입니다.

---

[문제해석]

N명의 사람이 일렬로 서있고, 모든 사람들은 1 ~ N까지 숫자 중에 겹치지 않게 숫자를 하나 부여받는다고 하자.

이때, N개의 값이 주어지고 이 값들은 왼편에 있는 사람 중 나보다 값이 적은 사람의 수라고 하자.

N개의 값이 유효한지 아닌지 판단해라.

 

위의 예제를 통해 문제를 조금 더 이해해보자.

10명의 사람이 있고 [0 0 0 2 0 1 6 7 6 9] 라는 배열이 주어졌을 때, [6 4 3 5 1 2 8 9 7 10] 배열에 대해 생각해보자.

'4'번 번호를 부여받은 사람은 왼쪽에 자기보다 큰 '6' 만 존재하고,

'3'번 번호를 부여받은 사람은 마찬가지로 왼쪽에 자기보다 큰 '6', '4' 만 존재하므로 [0 0 0 ~ ]이 되고,

'5'번 번호를 부여받은 사람은 왼쪽에 자기보다 작은 '4', '3' 존재하므로 [0 0 0 2 ~ ]이 성립한다.

 

[알고리즘설계]

1. N개의 배열이 주어졌을 때, 이 배열은 왼쪽에 나보다 작은 사람의 수를 의미하므로 앞에서부터 순회하며 내 오른쪽에는 사람이 없다고 가정하고 왼쪽 사람들에게만 초점을 맞춰서 번호를 갱신하자.

ex)

[0 0 0 2 0 1 6 7 6 9 ] 가 입력된다고 하자.

1번 사람은 왼쪽에 자기보다 작은 사람이 0명이므로 가장 큰 번호인 1을 부여한다. [ 1 ]

2번 사람은 왼쪽에 자기보다 작은 사람이 0명이므로 가장 큰 번호인 2를 부여한다. [ 1 2 ]

3번 사람도 마찬가지로 3을 부여하고 [ 1 2 3 ] 이 된다.

4번 사람은 작은 사람이 2명이므로 번호 3을 부여하고, 3보다 크거나 같은 번호를 하나씩 업시켜준다. [ 1 2 4 3 ]

5번 사람은 작은 사람이 0명이므로 가장 큰 번호인 5를 부여한다. [ 1 2 4 3 5 ]

6번 사람은 작은 사람이 1명이므로 2번 번호를 부여하고, 2번보다 크거나 같은 번호들은 하나씩 업시켜준다.

[1 3 5 4 6 2] 가 된다.

 

2. 왼쪽에 있는 사람의 수보다 나보다 작은 사람의 수가 더 큰 경우에는 "IMPOSSIBLE"을 출력하자.

ex)

[0 0 0 5  ~~ ]

4번 사람은 왼쪽에 3명밖에 없는데 작은 사람이 5명이므로 불가능한 경우다.

 

#include<cstdio>

int s[100] = {};
int r[100] = {};

int main(void) {
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int ninput, flag = 0;
		scanf("%d", &ninput);

		for (int j = 0; j < ninput; j++){
			scanf("%d", &r[j]);
		}

		for (int j = 0; j < ninput; j++) {\
			if (j < r[j]) {
				printf("IMPOSSIBLE\n");
				flag = 1;
				break;
			}

			s[j] = r[j];
			for (int k = 0; k < j; k++) {
				if (s[k] >= r[j])
					s[k]++;
			}
		}

		if (flag)
			continue;

		for (int j = 0; j < ninput; j++)
			printf("%d ", s[j] + 1);
		printf("\n");
		
	}
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.