[BOJ/백준] 11067 모노톤길 파이썬

문제링크 : https://www.acmicpc.net/problem/11067

11067번: 모노톤길

 

길의 좌표를 줬을 때 잘 나열해놓고 원하는 카페 번호를 출력하면 된다.

 

일단 입력받은 x,y좌표를 오름차순으로 일단 정렬했다. 이는 길이 오른쪽부터 왼쪽으로 향하기 때문이다.

그리고 x좌표에 대해서 똑같은 값을 가진 점들의 개수를 세서 저장했다.

y좌표는 일단 오름차순으로 정렬되어 있다. 하지만 카페의 길이 현재 점에서 위로 갈수도 있고 아래로 갈수도 있다.

그리고 길은 수평, 수직방향으로만 연결이 가능한데 오름차순으로 정렬되어 있을 경우 만들지 못하는 경우가 있다.

그때 사용하기 위해 개수를 세서 저장했다.

 

그리고 시작 점은 무조건 0,0에서 시작한다.

그렇기에 첫점이 0,0이 아니라면 수정해줘야한다.

그리고 이후 점들에서도 현재 점좌표랑 이전좌표가 x값도 y도 다른 경우 이는 정렬이 잘못되어 있는 경우이다. 이경우도 수정해줘야한다.

 

아래 처럼 길이 있다고 해보자

0 1

  2

  3

길은 오름차순으로 정렬되어 있기 때문에 길의 순서는 0 3 2 1 순으로 되어 있을 것이다. 하지만 실제 길은 0 1 2 3으로 되어 있다. 이런 경우를 체크해서 수정해줘야한다. 이는 첫점에서도 해당된다.

 

순서를 바꾸는 건 미리 저장한 x개수를 활용한다.

현재 점에서 x개수 만큼의 좌표의 순서를 뒤집어서 원본을 수정하면 된다.

 

from sys import stdin

input = stdin.readline

tc = int(input())
def solv():
    n = int(input())
    points = []
    xcnt = [0] * 100001
    for _ in range(n):
        x,y = map(int, input().split())
        points.append((x,y))
        xcnt[x] += 1

    points.sort()
    idx = 0
    if points[0][0] != 0 or points[0][1] != 0:
        idx = modify_order(points, idx, xcnt)
    else:
        idx = 1
    while idx < n:
        if points[idx-1][0] != points[idx][0] and points[idx-1][1] != points[idx][1]:
            idx = modify_order(points, idx, xcnt)
        else:
            idx += 1
    targets = list(map(int, input().split()))
    for target in targets[1:]:
        print(*points[target-1])

def modify_order(points, idx, xcnt):
    tmp = points[idx:idx + xcnt[points[idx][0]]]
    op = -1
    start = xcnt[points[idx][0]] - 1
    end = -1

    for j in range(start, end, op):
        points[idx] = tmp[j]
        idx += 1
    return idx
for _ in range(tc):
    solv()

 

내 풀이는 굉장히 느렸다. 좀 최적화가 필요할듯 하다.