백준 18870번- '좌표 압축' (PYTHON 풀이)

문제:

 

문제를 몇번이나 읽었는데 이해를 못하겠어서 문제 이해를 위해 서치를 진행했다. 해당 문제는 각 자리 수보다 작은 수의 개수를 찾는 것이라고 이해하면 될 것 같다.

예시를 보면 (2 4 -10 4 -9)를 입력했고 (2 3 0 3 1)을 출력한다. 이는 각 자리를 기준으로 자기보다 작은 수가 몇개인지를 찾는 것이다.

즉, 2보다 작은 수는 -10, -9 이기 때문에 첫 번째 자리에 2를 출력하고 4보다 작은 수는 2, -10, -9 이기 때문에 두 번째 자리에 3을 출력한다.

즉, 자기 보다 작은 수의 개수를 출력하면 되는 문제였다!

 

풀이:

N = int(input())
a = list(map(int,input().split()))
count = [0] * N

for i in range(len(a)):
    for j in range(len(a)):
        if a[i] > a[j]:
            count[i] += 1
print(count)

입력 받은 수 개수만큼 0으로 초기화된 리스트를 만들고 각 값을 비교하면서 자기보다 작은 수면 1씩 더하는 코드를 작성했다. 비쥬얼스튜디오에서 잘되어서 맞겠거니했는데 시간초과가 발생했다,,  O(n^2)의 시간복잡도라 엄청 커서 그런가보다,,

그리고 첫 번째 예제만 입력했어서 잘 출력됐었는데 제출한 다음 살펴보니 두번째 예제와 같이 중복된 수가 있을 경우 이때는 수를 1 더해주면 안된다. 그래서 set을 통해서 중복값을 제거해주는 코드가 필요하구나 싶어서 이를 유의해서 다시 코드를 작성하였다.

 

최종 코드:

import sys 

N = int(input())
a = list(map(int, sys.stdin.readline().split()))

unique = sorted(set(a))

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

for j in a:
    print(dic[j], end = ' ')

 

일단 시간 초과를 줄이기 위해 여러 코드를 작성해보았는데 계속 시간 초과가 나서 질문 게시판을 활용하였다. 딕셔너리를 이용해서 인덱스 형태로 문제를 풀면 시간 초과를 막을 수 있다는 댓글을 봐서 이를 활용하였다.

 

혹시 몰라 sys로 입력을 받았고 이전엔 놓쳤던 set을 통해 중복값을 제거해주었다. 그리고 딕셔너리로 문제를 풀기 위해서 꼭 해야하는게 정렬인데 정렬은 set과 함께 작성해주었다. 정렬을 해야하는 이유는 이따가 적도록 하겠다.

 

이후 딕셔너리를 만들어서 정렬된 리스트를 돌면서 딕셔너리에 저장해준다. 딕셔너리 역시 인덱싱 개념은 아니지만 비슷하게 키값을 활용하여 사용이 가능하기 때문에, 각 값을 키로 두고 이를 for문을 통해 인덱싱 값처럼 0부터 끝까지 번호를 매긴다.

여기까지 하면 dic = {-9 : 0,  -1 : 1 ...} 이런 형태로 사용자로부터 입력 받은 값이 정렬된 다음 0부터 ~ N-1 까지 값이 추가될 것이다.

이후 각 자리에 대해 인덱스가 생겼기 때문에 다시 정렬 전 기존 리스트를 기준으로 해당 키를 딕셔너리에 넣어서 이에 해당하는 value를 출력 형식에 맞게 출력해주면 된다.

 

앞서서 이 문제는 각 자리에, 자기보다 작은 수의 개수를 출력하면 된다고 하였다. 그런데 어떻게 개수를 직접 센 것도 아닌데 딕셔너리를 활용해서 풀 수 있는 것일까?

이는 정렬 때문이다. 정렬을 안하면 딕셔너리로 이 문제를 풀 수 있을지 모르겠다 (실력자라면 가능하려나..) 아무튼 아래 예제를 기준으로 정렬을 하게 되면 밑에 표와 같이 값이 바뀌게 된다. 이때 첫 번째로 오는 수는 자기보다 작은 수가 없으니 0개일 것이고 그 다음부턴 아래 위치에 해당 하는 수가 자기보다 작은 수이기 때문에 +1씩 더해진다. 이를 핵심 아이디어로 두고 코드를 작성하면 결국 맨 처음 우리가 풀고자 했던 문제와 같은 맥락의 코드가 된다.

-9 → 0개  
-1 → 1개 (-9)  
2  → 2개 (-9, -1)  
4  → 3개 (-9, -1, 2)  
10 → 4개 (-9, -1, 2, 4)

이번 문제는 처음에 너무 쉽다고 생각하면서 풀었는데 시간 초과 때문에 애를 좀 먹었다. 자료구조 시간에 배웠던 것처럼 시간 복잡도가 중요한 것은 알고 있지만 이를 코드에 적용해서 풀려고 하면 너무 어려워지는 것 같다. 역시 아직도 많이 부족하다 더 열심히 해야할 것 같다!