[BOJ #18870] 좌표 압축 (Python)

문제링크

18870번: 좌표 압축

 

 

CODE

N = int(input())

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

sortedList = sorted(inputList)
sortedObject = {}

count = 0
for i in range(len(sortedList)):
    if(sortedList[i] in sortedObject): 
        continue;
    sortedObject[sortedList[i]] = count
    count = count + 1

for k in inputList:
    print(sortedObject.get(k))

 

로직

1. 배열을 입력받는다 => inputList

2. inputList를 정렬한 버전의 sotedList를 생성한다. => sorted 사용

3. sortedObject <dictionary>에 {key: 원래 값, value: 압축된 값}으로 넣어준다. 

    이때, 이전에 dictionary에 들어갔던 Key값이 또 들어오면 (중복된 값이 들어오면) 같은 value를 넣어주어야 한다. 

4. 처음에 입력받은 배열 순서대로 (inputList) sortedObject의 value를 출력한다. 

 

사용 개념

python의 dictionary의 프로퍼티 동적할당 및 key값 가져오기

1. 정렬은 하되, 원래 자기 자신의 위치가 어디인지 알아야 한다.

2. 정렬을 해서 순서를 0부터 부여하되, 중복된 값이 오면 같은 숫자를 부여해주어야 한다. 

 

그래서 생각했던 게 dictionary다.

Javascript에서는 Object로 프로퍼티가 동적할당이 가능하다. 파이썬에도 dictionary가 이 역할을 해준다. 

원래 값에 대한 압축된 값이 저장되어 있어야 하므로, {key: 원래 값, value: 압축된 값}의 형식으로 값을 넣어주었다. 

 

sorted vs sort

파이썬에서 정렬을 한다면 sort와 sorted가 있다. 같아 보이는 함수지만, 좀 다르다. 

 

sort(inputList)를 하면, inputList자체가 정렬이 된다. 

하지만 sorted(inputList)를 하면 inputList가 바뀌지 않고, 정렬된 리스트를 반환한다. 

 

sort는 리스트 형태의 자료형만 정렬이 가능하다.

반면에, sorted는 리스트 형태뿐만이 아니라 객체, 딕셔너리 형태의 자료형도 정렬이 가능하다. 

다만, lambda라는 필드에다가 정렬 기준을 정해주어야 한다. 

 

dictionary = [
('바게트', 3800),
('초코 조각 케이크', 5600),
('소보루', 2000)
]

print(sorted(dictoionary, key=lambda bread: bread[1]))


#[('소보루', 2000), ('바게트', 3800), ('초코 조각 케이크', 5600)]

 

sorted는 아래 문제로도 활용해 볼 수 있다. 

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

10814번: 나이순 정렬