[파이썬] 백준 3089 : 네잎 클로버를 찾아서 (골드2)

[파이썬] 백준 3089 : 네잎 클로버를 찾아서 (골드2)

3089번: 네잎 클로버를 찾아서

---

문제

---

풀이

방향성 생각

• 명령이 주어진 방향에는 항상 네잎클로버가 존재한다.
• UD 입력이 주어지면 x좌표를 고정시키고 y좌표에 대해서 이분탐색을 진행한다.
• LR 입력이 주어지면 y좌표를 고정시키고 x좌표에 대해서 이분탐색을 진행한다.
• 숫자가 커지는 방향으로 갈 때는 bisect_right을 써서 이동하려는 인덱스 반환받아서 업데이트.
• 숫자가 작아지려는 방향으로 갈 때는 bisect_left를 써서 인덱스에 -1 해주고 업데이트.

전체코드

from bisect import bisect_left as bl, bisect_right as br
from collections import defaultdict as dd
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())
X,Y = dd(list),dd(list)
for _ in range(n):
    x,y = map(int,input().split())
    X[y].append(x)
    Y[x].append(y)
cmds = input()

for x in X:
    X[x].sort()
for y in Y:
    Y[y].sort()
    
x,y = 0,0
for cmd in cmds:
    if cmd == 'L': x = X[y][bl(X[y],x)-1]
    elif cmd == 'R': x = X[y][br(X[y],x)]
    elif cmd == 'U': y = Y[x][br(Y[x],y)]
    elif cmd == 'D': y = Y[x][bl(Y[x],y)-1]
print(x,y)

 

코멘트

모듈쓰니까 간결하고 좋음