[python_파이썬]백준_18870번_좌표 압축_풀이

공부하는허딩크 : https://www.youtube.com/live/g4Jrq889Aoc?feature=shared

예제를 보고 쉽게 생각해서 아래와 같은 코드를 만들었다.

 

<첫번째 시도 : 확인 안해도 실패>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

temp = max(map(abs, A))

for i in A:

    print(temp - i, end = ' ')

 

예제를 봤을때 절대값 가장 큰 값을 활용하면 된다고 생각이 들었는데 말도 안되는 생각이었다.

 

<두번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

answer = []

temp = set(A)

A_sorted = sorted(temp)

for i in A:

    answer.append(A_sorted.index(i))

for i in answer:

    print(i, end = ' ')  

 

단순히 작은 순서의 인덱스를 뽑아내는 거라 위의 코드를 생각했다. index함수를 사용해서 했는데 안되네...

 

<세번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

answer = []

temp = set(A)

A_sorted = sorted(temp)

for i in A:

    print(A_sorted.index(i), end = ' ')

 

이게 안되네.... 파이썬에서는 잘 나오는데....

 

<네번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

answer = []

temp = set(A)

A_sorted = sorted(temp)

#A_sorted = [-10, -9, 2, 4] / 0, 1, 2, 3

for i, j in enumerate(A):

    A[i] = A_sorted.index(j)

for i in A:

    print(i, end = ' ')

 

마지막 end에 공백을 없애볼까?

 

<다섯번째 시도 : 시간초과>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

answer = []

temp = set(A)

A_sorted = sorted(temp)

#A_sorted = [-10, -9, 2, 4] / 0, 1, 2, 3

for i, j in enumerate(A):

    A[i] = A_sorted.index(j)

for i, j in enumerate(A):

    if i < len(A):

        print(j, end = ' ')

    else:

        print(j)

 

방향을 다르게 생각해보자. 아니 그냥 다른 사람 풀이 참조하자.

index는 시간복잡도 O(N)가지고 있어서 계속 시간초과가 뜬다.

 

딕셔너리를 활용해보자

<여섯번째 시도 : 맞았습니다.>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

A_sorted = sorted(list(set(A)))

A_dict = {}

for i, j in enumerate(A_sorted):

    A_dict[j] = i

for i in A:

    print(A_dict[i], end = ' ')

 

처음부터 이걸 생각하지 않은 건 아니지만 앞으로 딕셔너리도 잘 활용해야 겠다.

 

<다른 사람 풀이>

index의 형태는 매번 최대 1,000,000번의 수행이 되면서 시간 초과됨.

A_dict = {A_sorted[i] : i for i in range(len(A_sorted))} 이 형태를 자주 활용해야 겠다.

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

A_sorted = sorted(list(set(A)))

A_dict = {A_sorted[i] : i for i in range(len(A_sorted))}

for i in A:

    print(A_dict[i], end = ' ')

 

<튜플활용 : 이것도 답이 되네.... 신기하다.>

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

b = []

for i, v in enumerate(A):

    b.append((i,v))

c = sorted(b, key=lambda x:x[1])

d = []

cnt = 0

for i in range(len(c)):

    if i==0:

        d.append((c[i][0], c[i][1], cnt))

    else:

        if c[i-1][1] != c[i][1]:

            cnt += 1

        d.append((c[i][0], c[i][1], cnt))

e = sorted(d, key=lambda x:x[0])

for i in range(len(e)):

    if i == (len(e) - 1):

        print(e[i][2])

    else:

        print(e[i][2], end=' ')