[백준/알고리즘/python/java] 18870번 - 좌표 압축

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

이 문제도 처음에 시간제한에 걸려서 시간초과가 났었던 문제이다.

로직은 간단한데, 시간초과가 났다면, 분명 어떤 라이브러리를 사용하는 것이거나 더 효율적인 자료구조가 있는 것이다.

방법을 고수하지말고 바꿔야 하는 것을 명심하자. 문제마다 어떤 자료구조로 풀어야 효과적인지 판단하는 것도 중요한 것 같다. 

 

맨 처음 풀었던 코드는 아래와 같다. 

import sys
input = sys.stdin.readline

N = int(input())
number_list = [int(num) for num in input().split()]

sorted_number_list = sorted(number_list)
for i in number_list:
    order = 0
    seen = -1
    for j in sorted_number_list:
        if i > j and j != seen:
            order += 1
            seen = j
    print(order, end=" ")

먼저 N개의 좌표값을 공백으로 구분해서 입력받은 다음, 그대로 number_list에 넣는다. (이제 for문과 리스트를 합병해서 쓰는 것이 익숙해지고 있다.)

sorted_number_list 라는 변수에 정렬된 number_list를 저장하고, 

기존 number_list를 for문으로 돌면서 order라는 순서를 뜻하는 변수를 0으로 초기화한다.

그리고 seen 이라는 변수를 통해 이미 판단된 숫자, 즉 중복된 숫자를 판단하면서 order가 증가되는 것을 막기 위해 초기값을 -1로 설정해준다.

그러면, 문제에서 의도한 대로 출력값을 나타낼 수 있다.

즉, 입력된 숫자 중에 작은 숫자로부터 오름차순으로 그 값의 순서를 출력하되, 중복된 숫자는 동일한 순서값을 가진다는 의도를 표현해 낼 수 있는 것이다.

 

하지만, 처음 작성했던 코드는 벌써, for문을 두번이나 썼고, 매번 리스트를 순회하면서 찾아내기 때문에, 시간복잡도가 높은 편이다. 그래서, 시간초과는 예상했지만, pypy3에서도 통과되지 못했다.

다음으로 작성했던 코드는 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())
number_list = [int(num) for num in input().split()]

sorted_number_list = set(number_list)
for i in number_list:
    order = 0
    for j in sorted_number_list:
        if i > j:
            order += 1
    print(order, end=" ")

바뀐건 별로 없지만, seen이라는 변수 선언 보다는 set이라는 함수를 사용해, 중복된 값을 미리 없애줘봤지만, 역시나 시간초과에서는 벗어날 수 없었다. 그러면, 이제는 for문이 아니라 다른 방법을 찾아내야 할 때이다.

 

마지막으로 작성한 코드는 아래와 같다.

import sys
input = sys.stdin.readline

N = int(input())
number_list = [int(num) for num in input().split()]

sorted_number_list = sorted(set(number_list))

sorted_number_list = {
    sorted_number_list[index]: index for index in range(len(sorted_number_list))}

print(*[sorted_number_list[i] for i in number_list])

number_list를 set으로 중복값을 없애주고, 오름차순으로 정렬한 sorted_number_list를 딕셔너리로 만들어봤다.

sorted_number_list 길이만큼 for문을 돌 되, 

중복이 없는 정렬된 {sorted_number_list[인덱스 값] : 인덱스 값} 형태로 sorted_number_list를 만들어준다.

 

문제에 나와있는 예제 입력을 예시로 들면,  아래와 같다.

print(*[sorted_number_list[i] for i in number_list]) 가 뜻하는 것은

입력한 숫자가 있는 number_list 를 순회하면서, 해당 number에 해당하는 value값, 즉 인덱스 값을 모두 출력해달라는 뜻이다. 파이썬에서는 * 을 이용한 출력방법도 있으니 알아두면 편할 것이다.