✏️ 문제

📝 문제 풀이 (시간 초과)

시도한 방법은 입력받은 리스트 num을 집합으로 바꾸어 주어 중복을 없앤 후 각각 값을 비교해 출력하는 방법이었다.
하지만 결과가 시간초과여서 시간복잡도를 줄여야 하는 상황이었다.

중복을 제거하고 정렬한 집합인 set_num과 입력받은 num 리스트를 비교하고 집합 set_num의 인덱스를 출력하는 방법은 for문이 두번 돌아가기 때문에 O(n)의 시간복잡도를 갖고 있다.

소스코드는 다음과 같다.

import sys
n = int(sys.stdin.readline().rstrip())
num = list(map(int, sys.stdin.readline().split()))
# num을 집합으로 바꾸어 중복 없애기 + 오름차순 정렬
set_num = sorted(set(num))

for i in range(n):
    for j in range(len(set_num)):
        if num[i] == set_num[j]:
            sys.stdout.write(str(j)+' ')

결과는 시간초과로 나온다.
다른 방법을 생각해야 했다.

👩🏻‍💻 문제 해결 (성공)

dict를 이용해 문제를 풀어보기로 했다.
정렬된 set_num의 값이 key값, set_num의 인덱스를 value 값으로 한 dict를 생성한다.
num 리스트의 값과 dict의 key 값이 같으면 value값을 출력해주는 소스코드이다.

시간 복잡도가 O(1)이기 때문에 위 방법보다 시간이 훨씬 단축된다. 소스코드는 다음과 같다.

import sys
n = int(sys.stdin.readline().rstrip())
num = list(map(int, sys.stdin.readline().split()))
set_num = sorted(set(num))

dic = {set_num[i]:i for i in range(len(set_num))}

for i in num:
    sys.stdout.write(str(dic[i])+' ')

dict를 사용해서 문제를 푸니 성공했다.

'시간 초과' 라는 문구를 본게 거의 처음이라서••• 당황했지만 이리저리 생각을 해봤다! 사실 저것도 다른 사람들의 풀이를 보면 그렇게 빠른 방법인지는 모르겠지만(?)
이제 문제 풀면서 시간 복잡도도 어느정도 생각해봐야겠다.