11067(모노톤길) - 해결

모노톤길

 

문제

제주 올레길 코스로 유명한 산책로가 있다. 산책로의 입구는 산책로에서 가장 서쪽에 위치하고 있다. 이 산책로는 단순 경로이며 수평 구간과 수직 구간으로만 구성되어 있어 모든 코너에서 90도 각도로 왼쪽 또는 오른쪽으로 회전만 할 수 있다. 또한 입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 이동을 전혀 하지 않아도, 즉, 보행자의 현재 위치를 나타내는 좌표의 x축 값이 작아지는 경우가 없이도 출구까지 도달할 수 있다. 그래서 이 산책로를 모노톤길이라고 부른다. 그림 1은 모노톤길의 예를 보여준다.

그림 1. 모노톤길의 예

 

이 산책로에는 n개의 카페가 곳곳에 들어서 있다. 특히 입구와 출구, 그리고 모든 코너에는 카페가 들어서 있다. 올레길 코스 관리자인 김씨는 이 산책로에 들어서 있는 모든 카페들의 위치 좌표를 가지고 있다. 입구 좌표는 항상 원점 (0,0) 이다. 그는 이들 카페에 1부터 n까지의 일렬 번호를 붙이려고 한다. 입구의 카페는 1번, 그 다음부터는 길을 따라가면서 만나는 순서대로 번호를 배정한다. 입구에서 출구로 갈 때, 카페 A를 카페 B보다 먼저 만나게 된다면, A에는 B보다 더 작은 번호를 배정한다. 따라서 그림 1의 산책로에서 좌표 (3,1)에 위치한 카페의 번호는 5이고, 좌표 (9,0)에 위치한 카페는 14번이고, 출구의 카페는 17번이다. 그는 산책로를 직접 걷지 않고 카페의 좌표들만으로 이 작업을 수행하고 싶어 한다. 그를 도와서 카페에 번호를 붙이는 작업을 수행하는 프로그램을 작성하시오.

 

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수를 나타내는 정수 n (2 ≤ n ≤ 100,000)이 주어진다. 그 다음 n개의 줄에는 각 줄마다 각 카페의 좌표 (x,y)를 나타내는 두 개의 정수 x와 y가 주어진다. (0 ≤ x ≤ 100,000, -100,000 ≤ y ≤ 100,000). 입구 좌표는 항상 (0,0)이다. 어떤 두 카페도 동일한 좌표를 가지는 경우는 없다. 마지막 줄에는 정수 m (1 ≤ m ≤ 10)과 m개의 정수가 주어진다. m개의 각 정수는 1 이상 n 이하로서 카페의 번호를 나타낸다.

 

출력

출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 카페 번호로서 주어진 m개의 정수에 대한 답을 순서대로 한 줄에 하나씩 출력한다. 정수 k에 대한 답은 번호가 k인 카페의 좌표 (x,y)를 나타내는 두 개의 정수 x와 y이다.

---

정렬해서 푸는데 시간 초과가 걸린다. 어디서 부터 해결을 해야할까?

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    cafes = [tuple(map(int,sys.stdin.readline().split())) for _ in range(N)]
    #cafes.sort()

    x, y = 0,0
    cnt = 0
    stack = [("start")]
    while cnt < len(cafes):
        sub = []
        for cafe in cafes:
            if cafe[0] == x:
                sub.append(cafe)
        cnt += len(sub)
        if sub == []:
            x += 1
            continue
        if y <= sub[0][1]:
            stack.extend(sub)
        else:
            sub.reverse()
            stack.extend(sub)
        x += 1
        y = stack[-1][1]

    #print("aaaa",stack)



    input = list(map(int,sys.stdin.readline().split()))
    T, cknum = input[0], input[1:]
    for num in cknum:
        print(f"{stack[num][0]} {stack[num][1]}")

우와~ 해결했다 스위핑 글을 보다가 반복문 1개로 할 수 있을거 같아서 해결하였다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kks227&logNo=220907708368 

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)

 

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    # 카페들을 받고 정렬
    cafes = [tuple(map(int,sys.stdin.readline().split())) for _ in range(N)]
    cafes.sort()

    # 위치를 저장하기 위한 x,y
    x, y = 0,0
    # 순서대로하기 위해서 처음은 start
    stack = [("start")]
    # 같은 x에 있는 cafe를 저장하기위해서
    # 위로가는지 아래로 가는지 판단하기 위해서
    sub = []
    # 순회 시작
    for i in range(len(cafes)):
        # 앞에 있는 카페이면 해당 x에 있는 카페들을 저장
        if cafes[i][0] > x:
            # 저장한 카페의 y가 마지막 카페의 y 보다 크거나 같다면 위로 순회하기 때문에 그대로 저장
            if y <= sub[0][1]:
                stack.extend(sub)
                sub = []
            # 아니라면 밑으로 순회하기 때문에 반대로 저장
            else:
                sub.reverse()
                stack.extend(sub)
                sub = []
            # 그리고 마지막으로 들린 카페의 좌표 저장
            x = cafes[i][0]
            y = stack[-1][1]
        # 같은 x에 있다면 저장
        sub.append(cafes[i])

    # 마지막 열에 있는 값을 저장하기 위해서
    # 하나이면 바로 저장 아까 처럼 위로 순회면 바로 저장
    if len(sub) == 1 or y <= sub[0][1]:
        stack.extend(sub)
    # 아래로 순회면 반대로 저장
    else:
        sub.reverse()
        stack.extend(sub)
    
    # 해당 인덱스를 저장해서 출력
    input = list(map(int,sys.stdin.readline().split()))
    T, cknum = input[0], input[1:]
    for num in cknum:
        print(f"{stack[num][0]} {stack[num][1]}")