[백준 알고리즘] - 좌표 압축 (18870번) with Python

📎 간략한 문제 정리

• N개의 좌표 X1~XN이 있을 때 X1'는 X1보다 작은 서로다른 요소의 개수를 의미합니다.

📈 문제 분석

• 주어진 배열을 정렬한 후 문제를 처리하면 쉽게 접근할 수 있습니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 가장 단순하게 생각해보면 전체를 순회하며 기준을 세우고, 자신을 제외한 다른 요소들을 검색해보며 더 작은 값이면 count += 1의 로직을 구현할 수 있습니다. 하지만 이것은 O(N^2)이며 주어진 조건 1 <= N <= 1,000,000에서 속도 이슈가 발생합니다. 그래서 정렬한 후 문제를 해결하는 방법을 생각했습니다.

💻 처음 풀이한 코드

from sys import stdin

input = stdin.readline
N = int(input())
x_list = list(map(int, input().split()))
sorted_list = sorted(x_list)
result = [0 for _ in range(N)]
for i in range(N):
    result[i] = sorted_list.index(x_list[i])
print(' '.join(map(str, result)))

주어진 배열을 정렬한 후 어떤 값보다 작은 값들의 개수는 정렬된 배열에서 그 값이 첫번째로 나올 때 index가 됩니다. 예를 들어 0 1 1 3 3 5 7 같은 배열이 있다고 할 때 3보다 작은 수의 개수는 처음으로 3이 나오는 인덱스이므로 3개가 됩니다. 위의 로직은 sorted가 시간복잡도를 결정하며 O(NlogN)이 됩니다.

📝 해결 과정에서 만난 문제, 고민들

• 문제의 조건처럼 모든 요소에서 i번째 요소보다 작은 값을 찾는 것이 아니라 한쪽 방향(예를 들어 1~(i-1)에서 더 작은 값의 개수)를 찾는다고 하면 DP를 사용할 수 있을까? -> 한쪽 방향으로 검색을 한다면 LIS와 비슷한 개념이라고 생각했습니다. 하지만 LIS를 사용한다고 속도에서 이득이 있을 것 같진 않습니다.
• 위의 고민에서 Stack을 사용하기 -> Stack의 전형적인 문제 중 특정 요소의 왼쪽 값 중 자신보다 크면서 인덱스가 가장 큰 요소를 찾는 문제가 있습니다. 이 문제처럼 왼쪽만 관찰하며 더 큰 값일때만 pop하는 해결방식을 활용한다면 O(N)이 가능할 수 있을 것 같습니다.
• Counting Sort 활용해보기 -> 이 문제를 생각하며 O(NlogN)보다 효율적인 방식은 O(N)이고, Counting Sort의 개념을 활용해볼 수 있을까 하는 생각이 있었습니다. 하지만 주어진 숫자 범위가 너무 넓어 방법이 있다고 해도 비효율적이라는 결론을 냈습니다.
• 조건이 1,000,000 이하였기 때문에 log1000000이 19.xx 이므로 충분히 log(NlogN)의 속도로 통과가 가능하다고 생각했습니다. 하지만 시간 초과가 났습니다. 생각해보니 sorted_list의 index 메소드가 O(N)이므로 O(N^2)로 속도 이슈가 발생하게 됩니다. 위의 로직을 아래와 같이 변경해보겠습니다.

💻 다시 풀이한 코드

from sys import stdin

input = stdin.readline
N = int(input())
x_list = list(map(int, input().split()))
sorted_list = sorted(list(set(x_list)))
sorted_dict = {value : index for index, value in enumerate(sorted_list)}
result = [0 for _ in range(N)]
for i in range(N):
    result[i] = sorted_dict[x_list[i]]
print(' '.join(map(str, result)))

🛠 수정 코드 해설

• 기본적으로 비슷한 코드이지만 dictionary를 활용해서 그 위치를 저장했습니다. 위에서는 index를 통해 매번 검색을 했지만 아예 그 인덱스 위치를 저장시켜 꺼내는 구조로 만들었습니다. Codility의 문제 중 주어진 정수 배열에서 주어진 숫자와 합의 결과가 같은 두 수 찾기 문제에서도 이와 비슷하게 target - 수를 저장해서 꺼내는 구조가 있었습니다. dictionary를 사용하면 O(1)로 효율적인 코딩이 가능합니다.

https://www.acmicpc.net/problem/18870