18870. [Python]좌표 압축

1. 문제

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 정

 

3. 파이썬 코드

 

N = int(input())

num_list = list(map(int, input().split()))
# 정렬된 리스트
answer = sorted(num_list)
# 인덱스 번호매칭
cnt = 0
# 딕셔너리 활용
ans_dict = {}
# 정렬된 리스트에서
for i in answer:
    # 딕셔너리에 값이 없으면
    if i not in ans_dict:
        # 값과 인덱스 번호를 넣어줌
        ans_dict[i] = cnt
        # 인덱스 번호 1 증가
        cnt += 1
# num_list 에서 대칭되는 key 값 출력
for j in num_list:
    print(ans_dict[j], end=" ")

 

4. 문제를 풀고난 후 생각

 

• 처음 문제를 읽고 제대로 이해를 하지 못해서 예제와 출력을 계속 봤던 문제였다.
• 처음 풀떄는 정렬을 진행한 후 인덱스 값을 그 숫자에 매칭시켜 주는방식으로 문제를 풀었다.
• 이 방식으로 풀자니 for문이 2개 중첩되어 시간복잡도가 1,000,000 * 1,000,000 까지 나올 수 있어서 정렬된 리스트 한개만을 사용하여 딕셔너리를 사용해 풀고자 생각했다.
• 정렬된 리스트의 값들에 딕셔너리를 통해 key 값으로는 리스트 값 value 값으로는 인덱스 번호를 차례로 넣어 줬으며 출력 단에서 처음 리스트를 반복문을 돌며 딕셔너리 key 값에 대응되는 value 값을 출력해 줬다.
• 딕셔너리와 리스트를 이용해 해결하는 문제로 되게 간단한 문제였던 것 같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 정렬