- 4 -
백준 온라인 저지 사이트 문제를 풀어보았다. 간단하게 리뷰남겨놓으려고 한다.
https://www.acmicpc.net/problem/1015
처음 문제 설명부터 무슨 소리인지 전혀 이해가 되지 않았다. P[0], P[1], ... P[N-1] 을 각각 하나의 배열이라고 생각해서였다. 하지만 그게 아니라 길이가 N인 수열 P는 0부터 N-1까지(포함)의 자연수를 원소로 갖고 있는 배열(순서는 미정)이라는 뜻이었다!
다음으로, 문제의 뜻을 살펴보니 배열 A가 주어졌을 때, 배열 B를 A를 비내림차순으로 정리한 배열이라고 한다면,
B[P[i]] = A[i] 를 만족하는 배열 P를 구하라는 문제였다(?)
그런데 설명에는 '적용' 같은 말이 써 있어서 헷갈리기만 했다.
에를 들어 A = [ 2, 1, 4, 3 ] 이라면, B = [ 1, 2, 3, 4] 이고
B[P[i]] = A[i] 를 만족시키는 배열 P를 찾아야 하므로, i = 0, 1, 2, 3 을 대입해보면. ( P[i] 란 배열 P의 i번째 원소라는 뜻 )
B[P[0]] = A[0] = 2
=> B[P[0]] = 2
=> P[0] = 1
B[P[1]] = A[1] = 1
=> B[P[1]] = 1
=> P[1] = 0
B[P[2]] = A[2] = 4
=> B[P[2]] = 4
=> P[2] = 3
B[P[3]] = A[3] = 3
=> B[P[3]] = 3
=> P[3] = 2
즉, P = [ 1, 0, 3, 2 ] 이다.
다시 한 번 살펴보면
A = [ 2, 1, 4, 3 ]
B = [ 1, 2, 3, 4 ]
P = [ 1, 0, 3, 2 ]
위에서 배열 P의 각 원소는 A의 각 원소가 몇 번째로 큰 지를 말해주고 있다!
eg) A의 첫 번째 원소인 2가 배열 내에서 2번째로 작으므로 P의 첫 번째 원소는 (가장 작으면 0) 1을 가리키고 있다.
이를 실제 코드로 구현하는 일은 그렇게 어렵지 않게 해 냈지만, 한 가지 아주 큰 조건이 있었다.
배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오.
비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다.
'만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. (?????)
예를 들어, A = [ 1, 1, 1, 1] 이라면 당연히 B = [1, 1, 1, 1] 이고. P 는 위에서 말했듯이 A의 각 원소가 배열 A 내에서 몇번째로 작은 원소인지에 대한 정보라고 했으므로
P = [ 0, 1, 2, 3 ]
P = [ 0, 2, 1, 3 ] ... 등등 0 부터 3의 정수로 이루어진 아무런 배열이면 상관 없다는 것이다.
이는 A = [1, 1, 5, 2] 같은 배열로 주어지면 코딩하기가 더욱 까다롭다. 생각이 여기까지 미치고 나서 너무 어렵다고 느껴져서 포기하기 직전, 내가 짠 코드가 이 문제를 자동으로 해결한다는 것을 깨달았다.(?)
(ArrayList의 indexOf(int a) 함수가 배열의 원소들을 조회할 때 앞에 있는 원소들부터 조회하기 때문인 것 같다.)
역시나 제출해보니 맞았습니다!가 이쁘게 출력되었다.
다음에는 문제 풀이 법도 같이 포스팅 해봐야겠다.