코딩테스트 준비 - 백준18870번 좌표압축 풀이:파이썬 딕셔너리 활용 (파이썬)

---

백준 18870번 풀이

---

문제풀러가기

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

18870번: 좌표 압축

---

문제

---

풀이

1. 문제 해설

 "Xi>Xj를 만족하는 서로 다른 좌표의 개수와 같아야된다" 라는 뜻은 즉 Xi가 리스트 안에서의 크기 순서를 출력하면 된다는 말입니다.

(크기 순서는 0부터 시작.)

예를 들면 arr=[ 1,0,5,2,1] 라고 하면,

여기서 arr[0], 즉 1로 예를 들면,

arr 리스트 안에서, 1>Xj이면서도 서로 다른 숫자는 0하나 밖에 없습니다.그러므로 1은 1을 출력

 

arr[1], 즉 0같은 경우 

0>Xj이면서도 서로 다른 숫자는 하나도 없습니다. 그러므로 0은 0을 출력

 

arr[2], 즉 5같은 경우

5>Xj이면서도 서로 다른 숫자는 3개(arr[0], arr[1], arr[3])가 있습니다. 그러므로 5는 3을 출력

*arr[4]를 포함하지 않는 이유는 문제에서 "서로 다른 좌표의 개수" 라고 하였으므로, arr[0]과 중복되므로 포함 안함.

 

arr[3], 즉 2 같은 경우

2>Xj는 arr에서, 0, 1, 1, 이렇게 3개가 있지만 1같은 경우 중복이므로(서로 다른 좌표의 개수와같아야 된다 했으므로) 2를 출력

 

arr[4], 즉1 같은 경우

첫 번째와 마찬가지로 0하나이므로 1을 출력

 

최종적으로 1,0,3,2,1 을 출력하게 됩니다.

2. 문제 규칙

결국 리스트안에서 자기보다 작은 숫자의 개수를 세는 것이므로, 자신이 리스트 안에서의 크기 순서를 출력하면 된다.

(크기 순서는 0부터 시작)

---

코드: 실패 (시간초과)

import sys
N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr2 = []

arr2 = list(set(arr))
arr2.sort()

for i in range(len(arr)):
  arr[i]=arr2.index(arr[i])

print(*arr,sep=" ")

 

리스트.index(i) : 시간 복잡도 O(n)

---

코드: 성공 

import sys
N = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
arr2 = []

arr2 = list(sorted(set(arr)))

dic = {arr2[i]:i for i in range (len(arr2))}

for i in arr:
  print(dic[i],end=' ')

# for i in arr: print(dic[i]) ... 
# 대신 아래 사용 가능
# print(*[dic[i] for i in arr])

딕셔너리 : 시간 복잡도 O(1)

---

파이썬 딕셔너리에 관해서..

1. 딕셔너리이름 = {"key값" : "value값"} 

2. key 중복 허용 X

3. key가 중복 될 경우 마지막에 입력된 key의 value를 출력.

ex)

a = {"key1":"value1", "key2":"value2", "key1":"value3"}

print(a["key1"])

#결과: 

#value3

 

1번 예제)

dic = {"key1":"value1", "key2":"value2", "key3":"value3", "key4":"value4",}

print(dic["key1"])

#결과
# value1

 

2번 예제)

arr = [1, 0, 2, -4, 6, 33, 22]

dic = {arr[i]:i for i in range (len(arr))}

print("dic =",dic)
print("dic[33] = ",dic[33])

#출력결과
# dic = {1: 0, 0: 1, 2: 2, -4: 3, 6: 4, 33: 5, 22: 6}
# dic[33] =  5