간만에... 시간 초과를 맞이했다... 세상에서 시간 초과랑 메모리 초과가 다 싫어 ~~ ..

18870: 좌표 압축

1. 내 풀이: 실패

저번 시간까지 자랑스럽다던 나 어디갔어... 사실 이건 문제부터 이해를 못했다 ㅎ 좌표 압축이라길래 내가 이런 걸 배웠나? 싶었지만 이미 문제에서 친절히 좌표 압축의 결과를 설명해주고 있었음 ^^!
해당 좌표보다 더 작은 숫자들을 출력하는 문제였다. set이랑 list 이용하면 쉽겠네 ~ 라고 생각한 내가 바보지 ~~~

import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
set_num = list(set(num))
set_num.sort()

cnt = []
for i in range(N):
    cnt.append(set_num.index(num[i]))

for i in cnt:
    print(i, end=' ')

이렇게 하면 답은 잘 나온다. 나는 항상 이게 문제다. 답은 잘 나오는데 어디 하나 나사가 빠진... 이번 풀이에서 깨달은 것은,

1. 파이썬 기본 제공 메소드(count, index 등)의 시간 복잡도는 크다...!

라는 것. 저번에도 count 함수 썼다가 시간 복잡도를 해결 못해서 꽤 어려움을 겪었던 것 같다. 나중에 코테에 저런 게 나오면 고민을 해보아야겠지?

결론은 난 이 문제를 못 풀었다 ^^...

2. 다른 풀이

참고한 블로그는 아래와 같다.
(https://eunhee-programming.tistory.com/116)

코드는,

import sys 
N = int(sys.stdin.readline()) 
arr = list(map(int,sys.stdin.readline().split())) 
arr2 = [] 

arr2 = list(sorted(set(arr))) 
dic = {arr2[i]:i for i in range (len(arr2))} 

for i in arr: print(dic[i],end=' ')]

간결해...! 여기서 포인트는 딕셔너리를 활용했다는 것이다.

1. 숫자들을 리스트로 받는다.
2. 새로운 리스트 arr2를 생성해준다.
3. arr2의 중복을 없애고 이를 정렬해준다.
4. arr2의 하나하나의 값과 인덱스를 딕셔너리로 받아준다.
5. 프린트...!

와우 어떻게 이렇게 생각하지? index() 함수를 이용해서 해당 값을 찾는 부분이 이렇게 표현될 수 있다니... 놀랍도다.

이 블로그에서 언급한 딕셔너리의 특징은,

• 딕셔너리: {key 값: value 값}
• key 중복 허용 X
• key가 중복될 경우, 마지막에 입력된 key의 value값을 선택

오호...! 놀라워 놀라워. 앞으로 리스트말고 튜플이나 딕셔너리와 같이 다양한 자료구조를 사용해보도록 해야겠다!!!

오늘도 신기한 알고리즘의 세계 끝!