16. Python(좌표 압축)

[toc]

좌표 압축

문제

1. https://www.acmicpc.net/problem/18870

---

제출(오답)

코드1 - 시간 초과

import sys

def rst_function(a_lst):
    rst = []
    for value in a_lst:
        if value not in rst:
            rst.append(value)
    return rst

n = int(sys.stdin.readline())
n_lst = list(map(int, sys.stdin.readline().split()))
n_lst_1 = rst_function(n_lst)

rst_lst = []
for num in n_lst:
    rst = 0
    for i in range(len(n_lst_1)):
        if num > n_lst_1[i]:
            rst += 1
        else:
            continue
    rst_lst.append(rst)

print(*rst_lst)

# 입력
5
2 4 -10 4 -9

# 출력
2 3 0 3 1

---

오답 풀이

1. 틀린 이유

• For문을 여러 번 사용해서 시간 초가 됨

2. 다른 방법

1) 함수로 묶기

def rst_function(arr):
    sorted_lst = sorted(set(arr))  # 중복을 제거한 후 정렬
    rank_dict = {num: idx for idx, num in enumerate(sorted_lst)}  # 값과 인덱스에 동시에 접근
    return [rank_dict[num] for num in arr]  # 각 숫자의 순위를 리스트로 변환하여 반환

• 중복 제거 후 오름차순 정렬
• 정렬 후 순서대로 인덱스 값 부여
• 원시 리스트에서 num을 받아 rank_dict[num]의 인덱스 값을 리스트 형태로 반환

2) 출력

n = int(sys.stdin.readline().strip())
n_lst = list(map(int, sys.stdin.readline().split()))
rst_lst = rst_function(n_lst)
print(*rst_lst)

• rst_function 함수가 실행된 후 반환된 리스트를 공백으로 구분하여 한 줄에 출력

---

제출(정답)

코드2

def rst_function(arr):
    sorted_lst = sorted(set(arr))
    rank_dict = {num: idx for idx, num in enumerate(sorted_lst)}  
    return [rank_dict[num] for num in arr]

n = int(sys.stdin.readline().strip())
n_lst = list(map(int, sys.stdin.readline().split()))
rst_lst = rst_function(n_lst)
print(*rst_lst)