[백준/BOJ] - 18870번 python 풀이 - 딕셔너리

 

---

요문제는 보자마자 이건 직관적으로 구현은 쉽겠지만 여차하면 시간 초과가 날 문제라고 느꼈다.

N값이 백만인데 리스트에 넣고 정렬하는 시간만 해도 엄청나기에 다른 자료 구조를 고려했다.

딕셔너리의 경우 탐색하는 데 드는 시간 복잡도가 낮기 때문에 해당 구조 채택.

 

일단 순서를 아래 코드의 주석에 달아놓은 거 처럼

맨처음 리스트에 값을 저장시키고 

하나하나 꺼내면서 반복문 변수를 통해 주어진 수의 idx를 value로 설정해줬다.

 

하지만 단순 dict로 선언할 경우 중복되는 key의 경우, value 값을 list로 변환해주어야 하는데,

해당 과정을 구현하면 반복문이 지저분 해질 거 같아 다른 방법을 모색했다.

 

바로 defaultdict라는 친구인데 이 친구는 key 값이 추가 되면 value의 디폴트 자료형을 미리 선언할 수 있다는 장점.

 

애초에 key - value 값이 주어졌을 때 value 자체를 list에 담아두면 추후에 겹치는 key 값이 입력으로 들어와도 

단순 append를 통해 value 값을 리스트에 추가해 줄 수 있다는 장점이 있다.

 

결과적으로 순서를 정리해보면

defaultdict 선언.

주어진 수를 dict에 넣어준다.(value 값은 idx 값)

key 기준 오름차순 정렬(오름차순 정렬을 했을 때의 idx 값이 사실상 그 수의 좌표 압축  값이기 때문에 오름 차순 진행

하지만 dict는 idx 개념이 없기에 이해가 쉽게 끔 idx라고 치환해서 설명한 것) - sorted로 오름 차순 정렬하면 자료구조가 list로 변환되므로 dict로 다시 바꿔줘야함

 

앞서 말한 idx 대신 0부터 시작해 반복문 사이클 마다 ++1이 되는 변수 temp를 통해 해당 역할 대체.

 

temp 값을 기존 0으로 초기화 해준 리스트인 result에 넣어줌. - 기존 딕셔너리에서 꺼낸 value 값은 idx 값

 

아스트로피를 활용해 result를 깔끔하게 꺼낸다.

 

---

주저리

 

딕셔너리 자료구조가 갖는 시간 복잡도 이점을 활용한 풀이이다.

추가로 defaultdict라는 외부 함수를 통한 방법이 있으니 인지해두자.

 

 

---

"""

딕셔너리 느낌으로 원래 주어진 수의 
idx를 저장.

{2:0, 4:[1,3], -10:2, -9:4}
key 기준으로 오름차순 정렬
{-10:2, -9:4, 2:0, 4:[1,3]}
걍 딕셔너리 각 key를 조회할때 변수하나 ++ 해줘서 idx 대체.
idx값 따로 저장(0부터 시작) temp 만들고 결과값에 넣으면 될듯?

"""
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
arr = list(map(int,input().split()))
dic = defaultdict(list)

for i in range(n):
    v = arr[i]    
    dic[v].append(i)

d = sorted(dic.items())
d = dict(d)
temp = 0
result = [0 for _ in range(n)]
for key,val in d.items():
    for item in val:
        result[item] = temp
    temp+=1
print(*result)

---