[백준] 18870 - 이분탐색 말고, 딕셔너리 활용해봐

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

18870번: 좌표 압축

 

이분탐색은 python3는 안되고 pypy3만 돌아간다.

아래는  '시간초과' 잔해들..

# BOJ_18870
import sys
input = sys.stdin.readline
# 입력
n = int(input())
nums = list(map(int, input().split()))
set_nums = list(set(nums))
# print(set_nums)
sort_nums = sorted(set_nums)
# print(sort_nums)
new_nums = [[0] for _ in range(n)]


def binary_search(target, data):
    start = 0
    end = len(data) - 1
    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return



# 각 갯수 세서 좌표 압축 만들기
count = 0
for i in range(len(nums)):
    # start_idx = sort_nums.index(nums[i])
    # 이분탐색으로 하자
    end_idx = binary_search(nums[i], sort_nums)
    # new_nums[i] = end_idx
    print(end_idx, end=' ')


# # 압축된 좌표들 출력
# new_strings = list(map(str, new_nums))
# print(' '.join(new_strings))

 

 

이분탐색을 쓴 이유는

해당 숫자의 인덱스를 찾기 위해서 이다.

인덱스를 찾는 것을

idex(n): O(N)

binary_search(target, data): O(logN)

으로 구해보았다.

 

하지만 막강한 딕셔너리는 O(1)이라는 것이다.

중복처리되고, sort 된 좌표 sort_nums를

dictionary에 각각의 요소와 요소의 인덱스로 key, value를 나타내 보자

요소: 요소의 인덱스

dic_nums = {sort_nums[i]: i for i in range(len(sort_nums))}

 

 

따라서 dic_nums[num]을 하면

sort_nums에서 

O(1)로도 num의 인덱스가 나오게 된다.

for num in nums:
    print(dic_nums[num], end=' ')

 

 

# BOJ_18870_dictionary
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
# 중복 제거
set_nums = list(set(nums))
# 오름차순 정렬
sort_nums = sorted(set_nums)
print(sort_nums)
dic_nums = {sort_nums[i]: i for i in range(len(sort_nums))}
print(dic_nums)
for num in nums:
    print(dic_nums[num], end=' ')

 

 

입력

5
2 4 -10 4 -9

중복 처리하고 오름차순 정렬한 sort_nums: [-10, -9, 2, 4]
sort_nums의 요소: 요소의 인덱스 dic_nums: {-10: 0, -9: 1, 2: 2, 4: 3}

 

출력

2 3 0 3 1