[BOJ] 8120 : Coding of Permutations - travelbeeee

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

---

[ 알고리즘풀이 ]

 입력으로 들어온 값들을 역으로 순회하며 답을 채워나갈 것이다.

input[x] : x번 째 입력값

check[x] : 1 ~ N 중에서 x 값을 사용했는지 안 했는지 

 현재 input[x] 가 k 라면 아직 사용 안 한 값 중에서 (k + 1) 번째로 큰 값을 선택합니다. 그러면, 역순으로 채우고 있기 때문에 input[x] 보다 값이 크면서 index는 작은 값들이 k 개가 됩니다. 이때, 아직 사용 안 한 값 중에서 (k + 1)번 째로 큰 값이 없다면 불가능한 경우이므로 "NIE"를 출력합니다.

 

ex) input = [ 0 0 1 0 2 0 4 ] 

input 배열을 역으로 순회하며 정답 배열을 채워보자.

1) input[7] = 4 / check = [ 0 0 0 0 0 0 0 ]

check 배열을 순회하며 아직 사용 안 한 값 중에서 5번 째로 큰 값을 선택한다.

→ ans[7] = 3

2) input[6] = 0 / check = [ 0 0 1 0 0 0 0 ]

→ ans[6] = 7

3) input[5] = 2 / check = [ 0 0 1 0 0 0 1 ]

→ ans[5] = 4

4) input[4] = 0 / check = [ 0 0 1 1 0 0 1 ]

→ ans[4] = 6

5) input[3] = 1 / check = [ 0 0 1 1 0 1 1 ]

→ ans[3] = 2

6) input[2] = 0 / check = [ 0 1 1 1 0 1 1 ]

→ ans[2] = 5

7) input[1] = 0 / check = [ 0 1 1 1 1 1 1 ]

→ ans[1] = 1

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, input[30001] = {}, ans[30001] = {};
	bool check[30001] = {};

	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> input[i];

	bool flag = false;
	for (int i = N; i >= 1; i--) {
		int c = 0, j = N;
		while (!(c == input[i] && !check[j])) {
			if (!check[j])
				c++;
			j--;
		}
		if (j < 1) {
			flag = true;
			break;
		}
		ans[i] = j;
		check[j] = 1;
	}

	if (flag)
		cout << "NIE\n";
	else{
		for (int i = 1; i <= N; i++)
			cout << ans[i] << '\n';
	}
}

---

세그트리를 이용해서 푸신 분들이 많은데, 코드를 뜯어보고 추후에 다시 포스팅하도록 하겠습니다.