알고리즘 종류: 분할정복
혼자서 풀었는가?: O...
문제 자체는 그렇게 복잡하지 않고 한번에 이해할 수 있는 문제였으나 왜인지 모르게 하루 종일 붙잡고 있었던 문제이다... (일단 merge sort 구현하는 것 자체가 헬이었다 아니 개념은 다 알면서 인간아) 덕분에 머리도 빠게질 것 같았고 많이 힘들었다 이 문제를 풀면서 앞으로 백준을 풀 때 어떤식으로 풀어야할 지 깨달았다
- 아무리 길어도 한 번에 3시간 이상은 한 문제를 붙잡고 있지 말자. 차라리 1시간씩 3번 보는게 한번에 3번 보는 것보다 낫다.
- 변수나 리스트를 만드는 것을 피하지 말자. 나중에 확인하기 위해 해당 값을 저장할 필요가 있는 데이터는 변수나 리스트에 저장해두자
문제 링크: https://www.acmicpc.net/problem/2
문제 풀이
분할정복을 통해 접근하면 되는 문제이다. 맨 처음 주어진 배열을 분할정복 중 merge sort를 사용하여 내림차순으로 정렬한다. 2, 8, 10, 7, 1, 9, 4, 15 가 주어졌으면 15 10 9 8 7 4 2 1 순으로 정렬하면 된다
분할정복은 크게 크기 n의 문제를 n/x로 나누는 divide 단계와 이를 다시 조합하는 combine 단계로 나뉜다. 여기서도 결국 정렬이 아닌 등수를 구하는 것이 목적이기 때문에, 이 등수는 combine 단계, 즉 merge sort에서는 merge의 단계에서 발생한다.
등수를 갱신하는 방법은 간단하다. 이전 단계에서의 자신의 인덱스와 현재 단계에서의 자신의 인덱스를 비교한 뒤에, 현재 단계에서의 인덱스가 이전 단계에서의 인덱스보다 더 크면 그 차이를 누적으로 합산한다. 현재 단계에서의 인덱스가 늘어났다는 것은 즉 내 앞에 다른 누군가가 들어왔기 때문에 나의 인덱스가 커졌다, 즉 뒤쳐졌다는 것이다(내림차순으로 정렬한다는 것을 다시 한번 상기하자). 인덱스는 0부터 시작하지만 등수는 1부터 시작하기 때문에 마지막에 출력할 때 전부 +1해주는 것도 잊지말자.
여기서 중요한 것 하나는 비교를 통해 차이를 누적해주는 과정을, j 인덱스 차례에서만 해주면 된다는 것이다. (분할정복은 n개의 배열에서 앞에 절반을 i 인덱스, 뒤의 절반을 j 인덱스로 가져가는데 여기서 j 인덱스를 말한다) i,j 모두 현재 단계의 인덱스는 몇이고 이전 단계의 인덱스는 몇이었는지를 저장해둬야 하긴 하지만, 이 둘을 비교해서 갱산하는 것은 j만 해주면 된다. 왜냐하면 i 인덱스 앞에는 아무도 없는 것과 마찬가지이기 때문이다. 2라는 작은 수라도 맨 앞에 오면 앞에 아무도 없기 때문에 1등인 것처럼 말이다. 이해 잘 안되면 직접 예시를 그려가면서 해보샘
예시
3 1 2 4
순으로 뛰어가고 있다. 답은 1 2 2 1 이겠쥬?
divide 과정
3 1 2 4
3 1 | 2 4
3 | 1 | 2 | 4
combine 과정
3 | 1 | 2 | 4 일 때
칸막이를 기준으로 달리기 팀이 나뉜다고 생각해보자. 지금은 다들 혼자 뛰는 상황이기 때문에 자신의 인덱스도 모두 0이고 전부 1등인 상황이다.
3 1 | 2 4 일 때 -> 3 1 | 4 2 로 내림차순 정렬됨
여기서 i 인덱스인 애들은 3, 2이고 j인덱스인 애들은 1, 4이다. 따라서 1, 4의 갱신만 생각해주면 된다(물론 i인 원소도 현재 인덱스를 기록해야된다. 다음 단계에서 j에 들어올 경우 인덱스 비교가 가능하기 때문에)
1을 생각해보자. 얘는 이전 단계에서는 1등으로 달리고 있었는데 이젠 2등이다. 인덱스가 0이었는데 1로 된 것이다. 그 차이를 저장해주자.
2 역시 1등에서 2등으로 뒤쳐졌지만, 얘는 i이기 때문에 차이를 갱신할 필요가 없다
3 1 2 4 일 때 -> 4 3 2 1 로 내림차순 정렬됨
j 인덱스인 2, 4만 고려해주면 된다. 2의 이전 단계 인덱스는 1이었는데 이젠 2가 되었다. 역시 차이 1을 누적해준다. 4는 이전 단계 인덱스가 0이었는데 지금도 여전히 0이다. 계속 1등이라는 소리다. 갱신할 필요가 없다.
정렬이 끝이 났다. 3, 1, 2, 4 순서대로 0, 1, 1, 0 이 누적되었다. 여기서 1만 더 더하면 우리가 구하고자 하는 등수와 일치한다.
코드
n = int(input())
arr = [[0, 0, 0] for _ in range(n)] # 값, 현재등수, 원래 값 인덱스
for i in range(n):
arr[i][0] = int(input())
arr[i][2] = i
temp = [[0, 0, 0] for _ in range(n)]
rank = [0 for i in range(n)] # 누적 등수
print(arr)
def div(l, r):
if(l < r):
m = (l + r) // 2
div(l, m)
div(m+1, r)
combine(l, m, m+1, r) # 0 3 4 7
def combine(l, m, s, r):
i = l
j = s
k = l # 여기 조심
cnt = 0
while (i <= m and j <= r):
if (arr[i][0] > arr[j][0]):
temp[k] = arr[i]
arr[i][1] = cnt
i = i + 1
else: # j 갱신하는 부분만 확인
temp[k] = arr[j]
if (arr[j][1] < cnt):
rank[arr[j][2]] += cnt - arr[j][1] # 최종 rank 갱신
arr[j][1] = cnt
j = j + 1
k = k+1
cnt = cnt + 1
if (i == m+1):
for rest in range(j, r+1): # j 갱신하는 부분만 확인
temp[k] = arr[rest]
if (arr[rest][1] < cnt):
rank[arr[rest][2]] += cnt - arr[rest][1]
arr[rest][1] = cnt
k = k + 1
cnt = cnt + 1
elif (j == r+1):
for rest in range(i, m+1):
temp[k] = arr[rest]
arr[rest][1] = cnt
k = k + 1
cnt = cnt + 1
for idx in range(l ,r+1):
arr[idx] = temp[idx]
div(0, n-1)
for i in range(n):
print(rank[i]+1)
arr이라는 배열에는 총 세 개의 값이 저장된다. [처음 입력받은 값, 현재 이 값의 인덱스, 값의 원래 인덱스] 순서대로 저장한다. 값의 원래 인덱스는 입력받은 순서대로 출력하기 위해 필요하다. 현재 이 값의 인덱스는 이 인덱스 정보가 들어간다. rank라는 배열에는 차이를 계산하여 누적한 값이 저장된다.
이 문제는 현재 이 값의 인덱스와 이 값이 이전 단계에서 가졌던 인덱스 값을 따로 저장할 생각을 하지 못해서 굉징히 어렵게 풀었던 문제이다. 다시 한번 계속 알고 있어야 하는 데이터가 있다면 이걸 저장할 변수나 배열을 만들 생각을 바로 하도록 하자.
