백준 - 11067번: 모노톤길 (Python)

목차

• 문제명
• 문제풀이
• 코드

 

백준 - 11067 : 모노톤길 

 

문제 유형 : 구현 (Implementation)

난이도 : 골드 5

 

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

11067번: 모노톤길

 

 

 

문제 풀이

 

모든 카페들의 좌표를 순서에 맞게 배열에 저장하여 카페 번호에 알맞는 좌표를 출력하는 방식으로 문제를 풀었습니다.

 

 

1. 모든 좌표를 x 좌표 기준으로 오름차순 정렬한다.

 

2. x 좌표를 key값으로, 해당 x 좌표 위 y 좌표들을 배열에 저장하여 value 값으로 딕셔너리에 따로 모은다.

 

3. 이전 카페의 y 좌표와 현재 카페의 y 좌표는 동일한 점과, 이전 카페의 y 좌표는 현재 x 좌표 위의 카페들 중 가장 위 혹은 가장 아래 카페의 y 좌표와 동일한 점을 이용한다.

 

4. 이전 카페 y 좌표가 현재 x 좌표 위의 카페들 중 가장 위면, 정답 배열에 현재 x축 위 카페들의 좌표를 역순으로 저장

 

5. 이전 카페 y 좌표가 현재 x 좌표 위의 카페들 중 가장 아래면, 정답 배열에 현재 x축 위 카페들의 좌표를 그대로 이어붙인다. (append)

 

6. m개의 번호에 대응하는 좌표 m개를 출력한다.

 

 

 

코드

 

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    positions = []
    n = int(input())
    for _ in range(n):
        x, y = map(int, input().split())
        positions.append((x, y))

    positions.sort() # 모든 좌표를 x 좌표 기준으로 오름차순 정렬시킨다.

    # x 좌표가 겹치는 y 좌표들을 딕셔너리에 따로 모은다.
    cafes = {}
    for x, y in positions:
        if x not in cafes:
            cafes[x] = [y]
        else:
            cafes[x].append(y)

    # 카페 좌표들을 순서대로 저장할 배열
    answers = ['empty']
    x_arr = [key for key in cafes]

    # 이전 카페의 y 좌표와 현재 카페의 y 좌표는 동일한 점을 이용한다.
    # 또한, 이전 카페의 y 좌표는 현재 x축 위의 카페들 중 가장 위 혹은 가장 아래 카페의 y 좌표와 동일한 점을 이용.
    cur_y = 0 # 가장 마지막으로 본 카페의 y 좌표
    for x in x_arr:
        y_arr = cafes[x]
        idx = y_arr.index(cur_y) # 이전 카페 y 좌표랑 같은 값의 인덱스 찾기
        if idx != 0: # 맨 위에 있으면 역순 정렬
            y_arr = reversed(y_arr)

        for y in y_arr: # 순서대로 정답에 삽입
            answers.append((x, y))

        cur_y = answers[-1][1] # 가장 마지막으로 본 카페의 y 좌표 갱신

    numbers = list(map(int, input().split()))
    m = numbers.pop(0)

    for num in numbers:
        print(*answers[num])

 

 

 

 

마무리

 

 

 

조금 더 효율적인 코드가 있지 않을까 싶다.