백준 18870 - sorted / dictionary / set 이용 / 시간복잡도

내 풀이 1 (오답)

# 시간 복잡도 O(n^2) -> 시간초과
# N = int(input())

# result = []
# cnt = 0

# num = list(map(int, input().split()))

# for i in range(N):
#     for j in range(N):
#         if num[i] > num[j]:
#             cnt += 1 
#     result.append(cnt)
#     cnt = 0

# for i in range(N):
#     print(result[i], end = " ")

리스트를 돌면서 자신보다 작은 수가 나오면 cnt +1을 하는 구조로 짜다보니
이중 for문이 나와서 시간복잡도가 O(N^2)이 돼서 시간초과가 됐다.
그래서 계속 어떻게 하면 시간복잡도를 O(N)으로 줄일까 고민했는데
나중에 정답을 찾아보니 O(N)도 시간초과더라... 더블 현타;;

내 풀이 2 (오답)

# N = int(input())

# num = list(map(int, input().split()))

# sort_num = sorted(num)

# # print(type(num))

# # print(num.sort())

# print(num.count(2))

# # B = [1000, 999, 1000, 999, 1000, 999]

# # C = [999, 999, 999, 1000, 1000, 1000]

# for i in range(N):
#     num[num.index(num[i])] = sort_num.index(num[i])

# print(num)

내 풀이에서 정답으로 가려면?

2가지를 생각해야했다.

1. SET 함수 사용
👉 인덱스를 사용해야하는데 좌표가 중복되는 좌표면 인덱스를 중복되는만큼 할당해야해서 문제 조건에 맞지 않았다.

💡 SET를 사용하여 정렬된 리스트에 중복 제거해서 인덱스 부여

2. dictionary 사용

👉 중복을 제거하고 나서 리스트의 값으로 정렬된 리스트의 인덱스를 할당하려고 보니
내 풀이 2같이 for문으로 할당하려고 하다가 기존 리스트와 정렬된 리스트의 size가 맞지 않아서 for문으로 할당하기가 힘들었다.

하지만, dictionary를 사용해도 정렬된 리스트와 기존 리스트의 size가 다른 것은 동일하므로
발상의 전환이 필요하다!

Key point
💡 for문으로 기존 배열을 돌면서 기존 배열의 값을 정렬된 리스트의 index로 저장하는 것 X
💡 dictionary의 key를 중복이 제거된 값 / value를 정렬된 리스트의 index(좌표 압축값)으로 해서 dictionary를 호출하여 print 하는 것!!
dictionary의 특성 : key값을 호출하면 value를 출력한다.

-> 이렇게 진행한 정답을 보자.

N = int(input())

num = list(map(int, input().split())) # [1000, 999, 1000, 999, 1000, 999]

sort_num = (sorted(set(num))) # [999, 1000]

dic_num = {}

for i in range(len(sort_num)): # dictionary에 중복제거, 정렬된 리스트의 값을 key로, 중복제거, 정렬된 리스트의 index를 value로
    dic_num[sort_num[i]] = i
    
for i in num: # 기존 리스트에 있는 값(1000, 999, 1000, 999, 1000, 999) 반복문 돌면서 dic_num[i] (key) 호출 -> value(인덱스) 출력
    print(dic_num[i], end = " ")

👉 dictionary를 돌면서 print만 하기 때문에 시간복잡도는 O(1)이 된다!!