1015: 수열 정렬 - 문제 이해/해설

1015번: 수열 정렬

 

B[ P[ i ] ] = A[ i ]

비내림차순 : 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우

 

이 두가지가 핵심이다.

비내림차순을 다시 한번 강조하자면 (인덱스 순서로 정렬되어 있을 때) 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우이다.

= 오름차순

문제에서 배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하라고 되어 있다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과는 B[  ]이다.

B[  ]가 비내림차순이 되어야 한다.

배열 A가 주어지므로 B[ P[ i ] ] = A[ i ]에 인덱스를 대입하여 B[ P[ i ] ]의 값(원소)을 알 수 있다.

이 때 값을 비내림차순으로 정렬하면 배열 B의 인덱스인 P[ i ]의 값이 0 부터 1씩 증가하는 형태가 되므로 P[ i ] 값을 알 수 있다.

 

---

index 와 value 사이의 관계를 놓치지 않는 것이 정말 중요하다.

이해가 어렵다면 예제 입력2를 통해 알아보자. (표에서 i = index )

 

1. 수열 A의 값이 ' 2 1 3 1 ' 로 주어졌다.

A[index]	value
A[ 0 ]	2
A[ 1 ]	1
A[ 2 ]	3
A[ 3 ]	1

2. B[ P[ i ] ] = A[ i ]

B[ P[index] ]	A[ i ]	value
B[ P[ 0 ] ]	A[ 0 ]	2
B[ P[ 1 ] ]	A[ 1 ]	1
B[ P[ 2 ] ]	A[ 2 ]	3
B[ P[ 3 ] ]	A[ 3 ]	1

3.  수열 B가 비내림차순이므로 value를 비내림차순으로 정렬

B[ P[index] ]	A[ i ]	value
B[ P[ 1 ] ]	A[ 1 ]	1
B[ P[ 3 ] ]	A[ 3 ]	1
B[ P[ 0 ] ]	A[ 0 ]	2
B[ P[ 2 ] ]	A[ 2 ]	3

4. 이 때 수열 B가 비내림차순이라 함은 수열 B의 index가 오름차순 일 때를 말하는 것이므로 아래 표와 같다.

B[ index ]	B[ P[ i ] ]	A[ i ]	value
B[ 0 ]	B[ P[ 1 ] ]	A[ 1 ]	1
B[ 1 ]	B[ P[ 3 ] ]	A[ 3 ]	1
B[ 2 ]	B[ P[ 0 ] ]	A[ 0 ]	2
B[ 3 ]	B[ P[ 2 ] ]	A[ 2 ]	3

수열 B의 index 가 P[ i ]와 같으므로, 수열 P의 값이 정해진다.

P[index]	value ( B의 index)
P[ 1 ]	0
P[ 3 ]	1
P[ 0 ]	2
P[ 2]	3

5. index로 정렬하면

P[index]	value
P[ 0 ]	2
P[ 1 ]	0
P[ 2 ]	3
P[ 3 ]	1

수열 P: 2 0 3 1

을 도출해낼 수 있다.

 

---

 

Code

 

1015: 수열 정렬

 

# A_size = '4'
# A_list = [2, 1, 3, 1]

A_size = input()
A_list = list(map(int, input().split())) 

#1 d2는 [A_index, A_value]를 값으로 갖는 2차원 리스트: d2 = [[0, 2], [1, 1], [2, 3], [3, 1]]
d2 = list() 
for idx in range(int(A_size)):
    d2.append([idx, A_list[idx]])

#3 d2에서 A_value를 오름차순(비내림차순) 정렬: d2_sorted = [[1, 1], [3, 1], [0, 2], [2, 3]]
d2_sorted = sorted(d2, key= lambda d2: d2[1]) # https://dydwnsekd.tistory.com/73

#4 d2_P[P_index(=A_index), P_value(B_index)]: d2_P = [[1, 0], [3, 1], [0, 2], [2, 3]]
d2_P = list()
for idx in range(int(A_size)):
    d2_P.append([d2_sorted[idx][0], idx])

#5 수열 P를 index로 정렬 d2_P_sorted : [[0, 2], [1, 0], [2, 3], [3, 1]]
d2_P_sorted = sorted(d2_P, key= lambda d2_P: d2_P[0])

#수열 P의 값만 sequence_P에 (index) 순서대로 저장, sequence_P =[2, 0, 3, 1]
sequence_P = list()
for num in d2_P_sorted:
    sequence_P.append(num[1])

#출력 조건에 맞게 수열 P 출력
print(*sequence_P)

 

이해가 어려운 부분 혹은 조언은 댓글로 남겨주세요:)