[Algorithm] 18870. 좌표 압축

18870: 좌표 압축 (해시테이블)

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

• 문제 티어 : S2
• 풀이 여부 : Solved
• 소요 시간 : 23:38

정답 코드

# O(NlogN)
import sys
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().split()))
set_arr = sorted(list(set(arr))) # 좌표 정렬, 고유 값에 대한 인덱스 매핑
dict_arr = {set_arr[i]: i for i in range(len(set_arr))} # 각 값의 인덱스에 O(1)로 접근

compressed = [dict_arr[x] for x in arr]

print(*compressed)

접근 방식

dict_arr = {set_arr[i]: i for i in range(len(set_arr))} 로 해시테이블을 생성해 인덱스와 중복을 제거한 값으로 key, value 설정 → {-10: 0, -9: 1, 2: 2, 4: 3}

compressed = [dict_arr[x] for x in arr] 코드를 통해 해시테이블에서 key에 해당하는 value를 찾는 방법!

접근 시행착오(+ 코드)

문제를 이해한 바로는, ex) 2 4 -10 4 -9 의 입력이 주어졌을 때, 이를 정렬하면 -10 -9 2 4 4 이고

좌표를 압축해 가장 작은 수부터 0을 시작값으로 부여한다면 0 1 2 3 3 이 된다.

이를 바탕으로 원래 입력값의 순서에 따라 압축된 좌표 값을 넣어주면 된다고 생각했다.

결론적으로 아래와 같이 풀이해 시간초과가 났다. 해시테이블을 사용해야 할 것 같은 느낌!?

# O(N^2)
import sys
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().rstrip().split()))
set_arr = sorted(set(arr)) # O(NlogN)

for i in range(len(arr)): # O(N)
  arr[i] = set_arr.index(arr[i]) # 내부 선형 탐색 : O(N)

print(*arr)

배운점 또는 느낀점

해시테이블 문제 오랜만에 푸는 것 같다!

이번주에 해시테이블 문제를 많이 접해서 시간 줄이는 연습을 해야겠다!