BOJ/백준-18870-python

cosmos·2021년 4월 27일

boj

하루에한개씩 알고리즘 문제 풀기!

목록 보기

176/709

문제📖

풀이🙏

첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X..... 가 주어진다.
수직선 위에 N개의 좌표 X.... 들을 좌표에 좌표 압축을 적용하라.
첫째 줄에 X ..... 를 공백 한 칸으로 구분해서 출력하라.
-> 처음에 제너레이터 함수형 프로그래밍으로 구하였지만 시간초과로인해 실패했다.
-> 두번째 시도에서 list indexing을했지만 시간초과로인해 실패했다.
-> dict indexing으로 기존 시간복잡도 O(n) -> O(1)로 성공하였다.

코드💻

시간초과 코드1

# boj, 18870 : 좌표 압축, python3
import sys

def compression(N):
    x_list = list(map(int,input().split()))
        
    result = [sum(num < i for num in x_list) for i in x_list]
        
    return ' '.join(map(str, result))

N = int(input())

print(compression(N))

시간초과 코드2

import sys

def compression(N):
    x_list = list(map(int,input().split()))
    sort_list = sorted(x_list)
        
    result = [sort_list.index(i) for i in x_list]
    
    return ' '.join(map(str, result))

N = int(input())

print(compression(N))

성공 코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr:
    print(dic[i], end = ' ')