⭐⭐⭐⭐[백준] [파이썬] [이분탐색] [딕셔너리] 18870번: 좌표 압축

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

18870번: 좌표 압축 문제 보러가기

18870번: 좌표 압축

 

 

시간 제한: 2초 

메모리 제한: 512MB 

 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -10^9 ≤ Xi ≤ 10^9

예제 입력 1

5
2 4 -10 4 -9

 

예제 출력 1 

2 3 0 3 1

 

---

문제 설명 

즉, 자기보다 작은 수의 개수를 차례대로 출력하면 된다.

2보다 작은 수 -10, -9로 2개 

4보다 작은 수 2, -10, -9로 3개 

-10보다 작은 수 없음 0개 

4보다 작은 수 3개 

-9보다 작은 수 -10으로 1개 

즉 2,3,0,3,1을 출력 

 

이분 탐색으로 푸는 법 1 

import sys

sys.stdin=open('input.txt', 'r')

input = sys.stdin.readline

if __name__=="__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    sorted_arr = sorted(list(set(arr)))

    '''
    [2, 4, -10, 4, -9] -> [-10, -9, 2, 4] : 자신의 위치가 곧 답이 됨
    '''
    
    for i in arr:
        start = 0
        end = len(sorted_arr) - 1
        
        while start <= end:
            mid = (start + end) // 2
            if sorted_arr[mid] == i:
                print(mid, end=' ')
                break 
            elif sorted_arr[mid] < i:
                start = mid + 1
            else:
                end = mid - 1

 

 오름차순으로 정력 sorted를 하면 자신의 위치가 곧 자기보다 작은 수의 개수가 된다. 

import sys

sys.stdin=open('input.txt', 'r')

input = sys.stdin.readline

if __name__=="__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    sorted_arr = sorted(list(set(arr)))

    '''
    [2, 4, -10, 4, -9] -> [-10, -9, 2, 4] : 자신의 위치가 곧 답이 됨
    '''
    
    for i in arr:
        print(sorted_arr.index(i), end=' ')

 

이렇게 하면 간단하지만 시간초과가 발생한다. 주어지는 숫자 범위가 어마어마한것을 알수 있다 

• list.index(i)의 형태는 시간복잡도 O(N) ➡️ 매번 최대 1,000,000번의 수행이 되면서 시간초과
• { dict[요소] : 요소의 index } 의 형태 시간 복잡도 O[1] ➡️ 매번 최대 입력 수 만큼 수행

따라서 이번에 딕셔너리를 사용해보자 

 

딕셔너리 사용 

import sys

sys.stdin=open('input.txt', 'r')


if __name__=="__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    sorted_arr = sorted(list(set(arr)))

    dic = {sorted_arr[i] : i for i in range(len(sorted_arr))}
    
    for i in arr:
        print(dic[i], end = ' ')
        
    '''
    [2, 4, -10, 4, -9] -> [-10, -9, 2, 4] : 자신의 위치가 곧 답이 됨
    
    {-10: 0, -9: 1, 2: 2, 4: 3} 각 수가 자신의 위치를 딕셔너리로 저장 
    
    '''

 

 

이분탐색 2 

import sys

sys.stdin=open('input.txt', 'r')

from bisect import bisect_left

if __name__=="__main__":
    n = int(input())
    x_list = list(map(int, input().split()))
    sorted_x_list = sorted(list(set(x_list)))

    for x in x_list:
        # x에 대해 x보다 작은 값은 x보다 왼쪽에 있는 숫자들의 수를 출력
        print(bisect_left(sorted_x_list, x), end=" ")

 

bisect는 참 사용할거 같지 않아서 외우지도 않고 외운다 해도 막상 쓸때 떠오를것 같지 않아서 안외웠는데 이럴때 딱 쓸 수 있다. 

 

bisect : 파이썬에서 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공. "정렬된 배열"에서 특정한 원소를 찾아야할 때 매우 효과적으로 사용.