[코딩테스트][백준] 🔥 백준 3089번 "네잎 클로버를 찾아서" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

import bisect

n,m=map(int,input().split())
pos1=[]
pos2=[]
for _ in range(n):
    a,b=map(int,input().split())
    pos1.append((a,b))
    pos2.append((b,a))

opers=list(input())
pos1.sort()
pos2.sort()

x=0
y=0
for oper in opers:
    if 'U'==oper:
        index=bisect.bisect_left(pos1,(x,y+1))
        # print(pos1[index])
        x,y=pos1[index]
    if 'L'==oper:
        index=bisect.bisect_right(pos2,(y,x-1))
        # print(pos2[index-1][::-1])
        x,y=pos2[index-1][::-1]
    if 'R'==oper:
        index=bisect.bisect_left(pos2,(y,x+1))
        # print(pos2[index][::-1])
        x,y=pos2[index][::-1]
    if 'D'==oper:
        index=bisect.bisect_right(pos1,(x,y-1))
        # print(pos1[index-1])
        x,y=pos1[index-1]

print(x,y)        
        

🍀 네잎 클로버 탐험: 좌표 이동의 비밀 🗺️

4분면으로 이루어진 좌표 안에서 네잎 클로버가 N개로 해당 위치가 각 좌표가 x,y로 주어진다. 시작점이 0,0일 때, M개의 명령이 주어지면 해당 명령의 방향으로 가장 가까운 네잎 클로버로 이동하는 문제이다.

x,y의 최대 값과 최솟값이 -100,000~100,000 이므로 길이가 200,000이 되어서 2차원 배열로 나타내면 각 칸이 40억(?)개 정도 되서 메모리 초과가 날 수 밖에 없다. 그렇기 때문에 2차원 배열로 놓고 찾는 방법으로는 접근할 수 없다.

이 때, M개, 즉 명령의 갯수가 100,000라는 점에서 이 값을 가지고는 $O(NlogN)$인 알고리즘을 사용할 수 있다고 생각을 하였고 가장 간단한 정렬을 사용한다면 해당 값으로 이진탐색을 이용할 수 있을 거라는 생각까지 도달하였다.

이진탐색을 사용하여 접근하였을 때, 각 값을 찾아가는 기준이 필요한데 이때, 우리가 원하는 값을 현재 위치를 기준으로 왼쪽에서부터 오른쪽에서부터 찾아간다면 가장가까운 좌표를 찾을 수 있을 것이라 생각하여 bisect_left, bisect_right를 사용하면 되겠다는 생각을 하였다.

그렇다면 해당 값을 +1이나 -1을 해서 해당 좌표의 오른쪽 왼쪽, 위 아래로 나눈 후 좌표값을 찾아들어가면 된다. 명령에 따라 이를 수행하고 현재 위치를 이동시킨다면 쉽게 값을 구해낼 수 있다.

이렇게 Python으로 백준의 "네잎 클로버를 찾아서" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊