[백준 3089번] 네잎클로버(파이썬)

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

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

이 문제는 구현방식은 간단한데

시간초과 관점에서 생각할 것이 많은 문제였습니다.

 

#백준 3089번 네잎클로버를 찾아서
dx=[0,0,1,-1]
dy=[-1,1,0,0]

N,M=map(int,input().split())
clover=[]
for _ in range(N):
    X,Y=map(int,input().split())
    clover.append([Y,X])
command=input().rstrip()
n_x=0
n_y=0

for c in command:

    if c=='L':
        while True:
            n_x+=dx[0]
            n_y+=dy[0]
            if [n_x,n_y] in clover:
                break
    elif c=='R':
        while True:
            n_x+=dx[1]
            n_y+=dy[1]
            if [n_x,n_y] in clover:
                break


    elif c == 'U':
        while True:
            n_x += dx[2]
            n_y += dy[2]
            if [n_x,n_y] in clover:
                break

    elif c == 'D':
        while True:
            n_x += dx[3]
            n_y += dy[3]
            if [n_x,n_y] in clover:
                break



print(n_y,n_x)

첫번째로 작성한 코드입니다.

clover 라는 리스트에

x,y좌표를 받고 출력해주는 방식이었죠.

이 방식은 시간초과가 떴습니다.

왜 시간초과가 떴을까 곰곰히 생각하다가

'clover가 엄청 많아지면

clover를 계속 호출하면서

안에 좌표랑 비교하는 게 오래걸리겠구나'

라는 생각을 했습니다.

 

# 백준 3089번 네잎클로버를 찾아서


N, M = map(int, input().split())
clover_y = [[]for _ in range(200000)]
clover_x = [[]for _ in range(200000)]
for _ in range(N):
    X, Y = map(int, input().split())
    clover_y[Y + 100000].append(X + 100000)
    clover_x[X + 100000].append(Y + 100000)
    # clover_x[X+100000].sort()
    # clover_y[Y+100000].sort()

command = input().rstrip()
n_x = 100000
n_y = 100000

for c in command:

    if c == 'L':

        while True:
            n_x -= 1
            if n_x in clover_y[n_y]:
                break

    elif c == 'R':

        while True:
            n_x += 1
            if n_x in clover_y[n_y]:
                break


    elif c == 'U':

        while True:
            n_y += 1

            if n_y in clover_x[n_x]:
                break



    elif c == 'D':

        while True:
            n_y -= 1
            if n_y in clover_x[n_x]:
                break


print(n_x - 100000, n_y - 100000)

그렇게 수정한 코드.

원래는 clover리스트의 크기를

20000*20000 로 설정했으나

파이썬에서 선언하려고 보니

이거 선언자체가 사실상 안되더군요.

그래서 x,y를 따로 나눠놓고

x좌표상에 얼마나 다른 y좌표가 있는지

y좌표상에 얼마나 다른 x좌표가 있는지 받는 후

탐색하는 걸로 코드를 짰습니다.

이 방식도 시간초과가 떴습니다.

 

왜 시간초과가 뜨는걸까.

곰곰히 생각해보다가 이런 경우가 있었습니다.

좌표값을 최대치로 생각해보면

저렇게 움직이는 동안 while문을 엄청 많이 돌아야합니다.

저러고보니깐 시간초과가 날 수 밖에 없었습니다.

그래서 코드를 아래와 같이 수정했습니다.

 

# 백준 3089번 네잎클로버를 찾아서


N, M = map(int, input().split())
clover_y = [[]for _ in range(200000)]
clover_x = [[]for _ in range(200000)]
for _ in range(N):
    X, Y = map(int, input().split())
    clover_y[Y + 100000].append(X + 100000)
    clover_x[X + 100000].append(Y + 100000)

for i in range(200000):
    if len(clover_x[i])>0:
        clover_x[i].sort()
    if len(clover_y[i])>0:
        clover_y[i].sort()

command = input().rstrip()
n_x = 100000
n_y = 100000

for c in command:
    #print(c)
    if c == 'L':
        #왼쪽으로 움직이는 경우
        #y좌표기준으로 큰 것부터 탐색하되
        #현재 x좌표보다 낮은게 나온다면 그 값을 받아준다
        max=len(clover_y[n_y])
        for i in range(max-1,-1,-1):
            if clover_y[n_y][i]<n_x:
                n_x=clover_y[n_y][i]
                break
        #print(n_x-100000,n_y-100000)

    elif c == 'R':
        #오른쪽이동
        #y좌표기준 작은것부터 탐색하되
        #현재 x좌표보다 큰 값이 있으면 그 값을 받아준다.
        max=len(clover_y[n_y])
        for i in range(max):
            if clover_y[n_y][i]>n_x:
                n_x=clover_y[n_y][i]
                break
        #print(n_x-100000,n_y-100000)
        
    elif c == 'U':
        #위로 이동
        #x좌표기준 가장 낮은 y좌표부터 탐색하되
        #현재 y좌표보다 큰 값이 나오면 그 값을 받아준다
        max=len(clover_x[n_x])
        for i in range(max):
            if clover_x[n_x][i]>n_y:
                n_y=clover_x[n_x][i]
                break
        #print(n_x-100000,n_y-100000)


    elif c == 'D':
        #아래로 이동
        #x좌표기준 가장 높은 것부터 탐색하되
        #현재 y좌표보다 낮은 게 있으면 그 값을 받아준다.
        max=len(clover_x[n_x])
        for i in range(max-1,-1,-1):
            if clover_x[n_x][i]<n_y:
                n_y=clover_x[n_x][i]
                break
        #print(n_x-100000,n_y-100000)



print(n_x - 100000, n_y - 100000)

 

pypy3로 제출하여 통과했습니다.

좌표를 이동할 때

반복문을 무지성으로 쓰는 것보다

시간초과를 줄일 수 있는 방법으로 쓸 수 있다는 걸 배웠습니다.