Punch!

1. 문제 설명

땅따먹기 게임을 하려고 한다.

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있다.

1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다.

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있다.

예)

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

1행에서 네번째 칸 (5)를 밟았다면, 2행의 네번째 칸 (8)은 밟을 수 없다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최댓값을 반환하라.

2. 코드

(1) 1차 시도 - 런타임 에러

answer = 0

def dfs(land, row, col, tot):
    global answer
    tot += land[row][col]

    if row == len(land) - 1:
        if answer < tot:
            answer = tot
        return 
    

    for i in range(4):
        if i == col:
            continue
        dfs(land, row+1, i, tot)
    
    
def solution(land):
    global answer
    
    for col in range(4):
        dfs(land, 0, col, 0)
    
    return answer

(2) 2차 시도 - DP

def solution(land):
    for i in range(1, len(land)): # 행 반복
        for j in range(4): # 열 반복
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])
    
    return max(land[-1])

3. 설명

우선 처음에 짠 코드는 깊이 우선 탐색 (DFS) 방법을 사용해서 구현했다.

재귀 함수로 열을 반복하며 (단, 연속된 동일한 열은 제외) sum을 누적하는 방식으로 했는데,

재귀로 호출되면서 알 수 없는 런타임 에러가 떴다.. (반례도 다 조사했을 때 문제 없었다ㅠㅠ)

그래서 다이나믹 프로그래밍으로 다시 구현했다.

이전 행에서의 최댓값을 뽑아서 현재 행에 더하는 방식으로 하여,

맨 마지막 행에서의 최댓값을 택하면 답이 된다!

1. 문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 한다. 

- U : 위쪽으로 한 칸 가기

- D : 아래쪽으로 한 칸 가기

- R : 오른쪽으로 한 칸 가기

- L : 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작하고, 좌표평면의 경계는 (-5, -5), (-5, 5), (5, 5), (5, -5)이다.

예) "ULURRDLLU"

게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 한다.

위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 된다.

(8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길)

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 반환하라.

2. 코드

(1) 내 코드

def solution(dirs):
    dx = [0, 0, 1, -1] # UDRL
    dy = [1, -1, 0, 0] # UDRL
    x, y = 0, 0
    
    garo = [ [False for _ in range(10)] for _ in range(11) ]
    saero = [ [False for _ in range(10)] for _ in range(11) ]
    
    answer = 0
    for dir in dirs:
        if dir == 'U':
            new_x = x + dx[0]
            new_y = y + dy[0]
        elif dir == 'D':
            new_x = x + dx[1]
            new_y = y + dy[1]
        elif dir == 'R':
            new_x = x + dx[2]
            new_y = y + dy[2]
        elif dir == 'L':
            new_x = x + dx[3]
            new_y = y + dy[3]
        
        if new_x < -5 or new_x > 5 or new_y < -5 or new_y > 5:
            continue
        
        if dir == 'R':
            if garo[5 - new_y][5 + x] == False:
                garo[5 - new_y][5 + x] = True
                answer += 1
        elif dir == 'L':
            if garo[5 - new_y][5 + new_x] == False:
                garo[5 - new_y][5 + new_x] = True
                answer += 1
        elif dir == 'U':
            if saero[5 + new_x][5 - new_y] == False:
                saero[5 + new_x][5 - new_y] = True
                answer += 1
        elif dir == 'D':
            if saero[5 + new_x][5 - y] == False:
                saero[5 + new_x][5 - y] = True
                answer += 1
        
        x, y = new_x, new_y
        
        
    return answer

(2) set 활용한 코드

def solution(dirs):
    s = set()
    d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    x, y = 0, 0
    
    for i in dirs:
        nx, ny = x + d[i][0], y + d[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            s.add((x,y,nx,ny))
            s.add((nx,ny,x,y))
            x, y = nx, ny
            
    return len(s)//2

3. 설명

(1) 내 코드

우선 내가 짠 코드는.. 정말 있는 그대로의 날 것의 코드이다.. ㅎ 좀 창피하긴 한데, set을 활용할 생각을 못했어서 이렇게 풀 수밖에 없었다ㅜㅠ

흔히 다이나믹 프로그래밍에서 하는 것처럼 방문 여부를 저장하기 위해 배열을 만들어준다.

단, UP, DOWN은 'garo[11][10]' 배열을,

LEFT, RIGHT는 'saero[11][10]' 배열이다.

배열의 인덱스와 좌표를 맞춰주기 위해서 규칙을 찾아봤을 때,

각각 5-x 또는 5+x, 5-y, 5+y를 해주면 맞춰진다.

각각의 경우를 조건문으로 해서 하나씩 조사해 나가면 된다.

(2) set 활용한 코드

우선 UDRL을 딕셔너리로 선언하고, 좌표 범위를 넘어서는지 조사한다.

그리고는 (시작좌표 x, 시작좌표 y, 도착좌표 x, 도착좌표 y)와 (도착좌표 x, 도착좌표 y, 시작좌표 x, 시작좌표 y)를 모두 집합에 넣는다.

- 집합에 넣는 이유 : 중복되는 이동 쌍이 없도록

- 마지막에 2로 나눠주는 이유 : 시작과 도착 좌표를 모두 넣어줬기 때문에, 그 절반 값이 이동 횟수임

배울 점이 많았던 코드였다. 이동 경로를 string으로 저장하지 않고, 시작과 끝 좌표 쌍을 모두 저장하는 방식,

그리고 집합을 사용하여 중복 제거하는 것까지!

1. 문제 설명

정수로 이루어진 배열 numbers가 있다.

배열에서 자신보다 뒤에 있는 숫자 중에서, 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 한다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 반환하라.

단, 뒷 큰수가 존재하지 않는 원소는 -1을 담는다.

예시)

- numbers = [2, 3, 3, 5]

정답 : [3, 5, 5, -1]

- numbers = [9, 1, 5, 3, 6, 2]

정답 : [-1, 5, 6, 6, -1, -1]

2. 코드

(1) 1차 시도

def solution(numbers):
    answer = []
    
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                break
        if len(answer) != (i+1):
            answer.append(-1)
    
    return answer

(2) 2차 시도

def solution(numbers):
    answer = [-1 for _ in range(len(numbers))]
    stack = []
    
    for i in range(len(numbers)):
    
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        
        stack.append(i)
        
    return answer

3. 설명

이 문제가 되게 단순해 보였지만, 시간 초과를 극복하려면 새로운 관점이 필요하기 때문에 어려웠다.

많은 사람들의 코드를 봤을 때, 2차 시도 코드와 비슷하거나 동일하다.

그래서 나는 어떻게 stack을 도입할 시도를 하게 되었는지를 생각해보기로 했다.

처음에는 절대로 저런 생각이 나지 않기 때문이다..

index 하나 하나씩을 해결해나가는 식이 아니라, 바로 뒤에 큰 수가 없다면 잠시 스택에 넣고 대기하는 형식이다.

이렇게 하나씩 뿌시는 경우에는 현재 인덱스에서 그 뒤의 인덱스 이후를 다 비교해봐야 하기 때문에, $O(n^2)$이 된다.

검토하고 있는 인덱스의 그 다음 인덱스 시점에서 바라본다.

만약 그 인덱스가 큰 수를 찾지 못했다면 스택에 넣는다!

기본적으로 현재 인덱스를 스택에 넣어주고, 조건 맞을 시에 pop() 하도록 구현한다.

위의 그림이 단계를 거치면서 스택의 변화를 보여준다.

즉, for 문이 돌아가는 그 시점의 인덱스는 answer 값이 변하는 시점의 인덱스가 아니라, 비교대상이라고 생각하면 된다!