[파이썬, Python] 백준 18870 : 좌표 압축

백준 18870 번 : 좌표 압축

📖 문제 📖

 

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

---

📺 입력&출력 📺

---

📝 풀이 📝

문제를 이해 하는데에 시간이 조금 걸렸던 편입니다.

하지만 문제를 이해하고 나니 논리는 생각보다 쉬운편 이였습니다.

 

만약, 입력값이 2 5 0 9 라고 한다면

수직선 상의 좌표는 이렇게 될 것입니다.

 

이 좌표를 압축하여

이렇게 만드는 것이 목표입니다.

 

제가 생각한 방법은 다중 리스트입니다.

 

[입력값, 원래 index값, 정렬한 뒤 index] 이렇게 리스트를 구성해주는 방법입니다.

1. 제일 먼저 입력값을 리스트로 받는다.

-> [2,5,0,9]

 

2. 마지막 출력에서 현재 위치대로 출력해야 하기 때문에 리스트에 추가로 현재 index를 저장해둔다.

-> [[2,0], [5,1], [0,2], [9,3]]

 

3. 입력값을 기준으로 정렬한뒤, 정렬된 순서대로 숫자를1씩 증가시키며 리스트에 추가 시킨다. (이전 인덱스와 같은 값이면 1을 증가하지않고 추가)

-> [[0,2,0], [2,0,1], [5,1,2], [9,3,3]]

 

4. 원래index값(arr[1])을 기준으로 정렬한다.

-> [[2,0,1], [5,1,2], [0,2,0], [9,3,3]]

 

5. 여기서 arr[2]값들을 출력 시켜주면 결과가 나옵니다.

압축한 결과 -> 1 2 0 3

 

---

👨‍💻 나의 코드 👨‍💻

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

for i in range(n):
    arrCopy.append([arr[i],i])

arrCopy.sort()
arrCopy2 = []
count = 0
arrCopy2.append([arrCopy[0],0])
for i in range(1,len(arrCopy)):
    if arrCopy[i-1][0]==arrCopy[i][0]:
        arrCopy2.append([arrCopy[i],count])
    else :
        count+=1
        arrCopy2.append([arrCopy[i],count])
arrCopy2.sort(key = lambda x:(x[0][1]))

for i in range(n):
    print(arrCopy2[i][1],end=' ')

 

사실 이 코드는 제가 보기에도 너무 복잡하고 메모리의 효율이 좋지 않습니다.

 

다중리스트로 할 때 중간 리스트 값에 원하는값을 추가 시키는 방법에 대해서 잘 모르기 때문에 리스트를 계속 새로 만들었기 때문입니다.

 

이번 기회에 리스트에 값을 추가하는 방법에 대해서 더욱 깊이 공부 해봐야 겠다는 생각을 했습니다. 

다중리스트로 입력 받는 법

 

n = int(input())
arr = [[int(i)] for i in input().split()]

for i in range(n):
    arr[i].append(i)

arr.sort()
count = 0
arr[0].append(count)
for i in range(1,n):
    if arr[i-1][0] != arr[i][0]:
        count+=1
    arr[i].append(count)

arr.sort(key = lambda x:x[1])

for i in range(n):
    print(arr[i][2],end=' ')

 

공부한 방법으로 메모리를 조금 더 줄여보았습니다!

하지만 시간은 오히려 살짝 늘어났습니다ㅠㅠ

---

👩‍👩‍👧‍👧 다른 사람의 코드 👩‍👩‍👧‍👧

n=int(input())
a=list(map(int,input().split()))
sa=sorted(set(a)) # set을 이용한 중복 제거 및 정렬

dic={}
for i in range(len(sa)):
    dic[sa[i]]=i #인덱스 사전 만들기
for x in a:
    print(dic[x],end=' ')

 

코드가 굉장히 간결했습니다ㅠㅠ

 

하나하나 분석해보자면

sa에 set(a)를 정렬한 결과를 저장합니다.

 

이후, {-10: 0, -9: 1, 2: 2, 4: 3} 이러한 인덱스 사전을 만들었습니다.

 

마지막으로 처음 받았던 값들을 하나씩 꺼내면서 dic에서 key값을 기준으로 value를 가져오는 논리로 구성되어 있는것을 확인할 수 있습니다.

 

dictionary에 대해서 이해가 부족한거 같아 조금 더 공부가 필요하다고 느꼈습니다.

 

제가 짠 코드에 비해서 메모리와 시간적인 측면에서 더욱 효율적인 코드라는 생각이 들었습니다.

실제로도 그랬습니다 하하^^ 메모리는 2배 시간은 3배가 차이나네요..