99클럽 코테 스터디
한줄코딩은 어제 하루의 일탈로 치고, 오늘은 평소처럼 실행시간 효율 위주의 풀이로 접근했다.
leetcode는 특이하게도 제출할 때마다 실행시간이 상위 몇%인지, 메모리가 상위 몇%인지 바로 알려주는데(제출할때마다 편차가 좀 크긴 하지만), 최적으로 깎는 재미가 있었다. 최적이라고 생각되면 제일 잘 뜰 때까지 같은 코드로 여러 번 제출해보기도 했다.
아, 그리고 챌린저 문제 퍼즐 조각 채우기는 99클럽 1기 때 이미 풀고 TIL 작성까지 완료한 문제라, 과거의 TIL 링크로 대체했다. (코드는 바로 볼 수 있게 맨 밑에 넣어두었다.)
비기너 문제 Range Sum of BST : https://leetcode.com/problems/range-sum-of-bst/description/
미들러 문제 타겟 넘버 : https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3
챌린저 문제 퍼즐 조각 채우기 : https://school.programmers.co.kr/learn/courses/30/lessons/84021
챌린저 문제 TIL : https://velog.io/@sogur928/TIL5
출처 : 프로그래머스, leetcode
비기너 문제 : Range Sum of BST
풀이 접근
오늘의 문제는 공통적으로 dfs로 풀린다.
이진 탐색 트리는 어떤 노드이건 왼쪽 자식에 달린 트리의 모든 노드보다 크고, 오른쪽 자식에 달린 트리의 모든 노드보다 작다는 성질이 있다.
따라서, 노드의 값이 low보다 작으면, 더 이상 해당 노드의 왼쪽을 전혀 탐색하지 않아도 되고, 반대로 노드의 값이 high보다 크면, 더 이상 해당 노드의 오른쪽을 전혀 탐색하지 않아도 된다는 점을 이용해서 효율을 최적화할 수 있다.
코드(Python3, Accepted, 96ms, 23.63MB)
풀이들은 큰 틀에서는 dfs라는 점에서 다 같지만, 디테일에 따라 실행시간이나 메모리가 조금씩 바뀜을 알 수 있다. 아래 코드는 실행속도 상위 3%까지 찍히는(다만 제출 운에 따라 20% 정도일 수도 있다) 코드인데, 메모리는 딱히 그렇지 못하다.
하지만 첫 제출 버전에서는 rangeSumBST 안에 dfs 함수를 그냥 따로 정의하고 dfs를 실행해서 answer를 반환했는데, 이 때는 실행 속도는 별로였지만 메모리가 상위 0.8%로 나왔다. 아무래도 rangeSumBST는 매번 low, high 값을 넣어줘야 해서 메모리를 조금 더 먹나? 하는 생각이 들었다.
root가 None이면, not root가 참이 되므로, 그냥 0을 반환하고, 그 이외의 경우에는 root의 값에 따라 왼쪽을 dfs 탐색할지, 오른쪽을 탐색할지, 둘 다 할지 결정해서 맞는 값을 반환한다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if not root:
return 0
elif root.val < low:
return self.rangeSumBST(root.right,low,high)
elif root.val > high:
return self.rangeSumBST(root.left,low,high)
else:
return root.val + self.rangeSumBST(root.right,low,high) + self.rangeSumBST(root.left,low,high)
미들러 문제 : 타겟 넘버
풀이 접근
경우의 수 문제이다. 다만 2^20 = 1048576가지 경우의 수를 항상 다 탐색하지는 않아도, dfs와 가지치기를 이용해서 효율을 좀 더 늘릴 수 있다.
구체적인 디테일으로는,
- numbers의 합과 target의 홀짝성이 다르면 무조건 answer가 0인 점을 이용해 가지치기
- +를 달 숫자들만 고르는 것으로 바꾸고 그에 맞게 target을 numbers의 합과 원래 target의 값의 평균으로 수정하기
- 문제에서 순서를 고정시켜놨지만 사실 그럴 필요 없다는 점(맨 앞에도 -를 붙일 수 있으니까)을 이용해 numbers를 오름차순 정렬하기(이러면 값이 큰 숫자부터 결정하므로 가지치기 효율이 늘어난다)
등을 적용했다.
코드(Python3, 통과, 최대 264.75ms, 10.3MB)
def solution(numbers, target):
if (sum(numbers) + target) % 2:
return 0
n = len(numbers)
numbers.sort(reverse = True)
target = (sum(numbers) + target) // 2
def dfs(idx, added):
if added >= target:
return added == target
if idx == n:
return False
return dfs(idx + 1, added) + dfs(idx + 1, added + numbers[idx])
answer = dfs(0, 0)
return answer챌린저 문제 : 퍼즐 조각 채우기
풀이 접근
과거의 TIL로 대체
https://velog.io/@sogur928/TIL5
코드(Python3, 통과, 최대 18.95ms, 10.6MB)
코드 설명도 해당 TIL에 있다.
def solution(game_board, table):
# 90도씩 회전시킨 조각을 다 만들기 위함, dfs할거니까 처음부터 바깥탈출안되게 벽발라놓기
n = len(table)
table.append([0]*(n+1))
game_board.append([1]*(n+1))
table_90 = [[0]*(n+1) for _ in range(n+1)]
table_180 = [[0]*(n+1) for _ in range(n+1)]
table_270 = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
table[i].append(0)
game_board[i].append(1)
for j in range(n):
table_90[j][n-1-i] = table[i][j]
table_180[n-1-i][n-1-j] = table[i][j]
table_270[n-j-1][i] = table[i][j]
# 오른쪽1 아래2 왼쪽3 위4 돌아갈땐5 6진법으로 조각의 정보를 저장
def dfs(x,y,p):
table[x][y] = -p # 회전시켰을때도 알아보기 위해 0으로 만드는게아니라 조각 번호의 음수로 바꿈
size[p-1] += 1 # 조각의 사이즈 저장
for i in range(4):
dx,dy = directions[i]
if table[x+dx][y+dy]>0:
pieces[p-1] *= 6
pieces[p-1] += i+1
dfs(x+dx,y+dy,p)
pieces[p-1] *= 6
pieces[p-1] += 5
return
def dfs_90(x,y,p):
table_90[x][y] = 0
for i in range(4):
dx,dy = directions[i]
if table_90[x+dx][y+dy]>0:
pieces_90[p-1] *= 6
pieces_90[p-1] += i+1
dfs_90(x+dx,y+dy,p)
pieces_90[p-1] *= 6
pieces_90[p-1] += 5
return
def dfs_180(x,y,p):
table_180[x][y] = 0
for i in range(4):
dx,dy = directions[i]
if table_180[x+dx][y+dy]>0:
pieces_180[p-1] *= 6
pieces_180[p-1] += i+1
dfs_180(x+dx,y+dy,p)
pieces_180[p-1] *= 6
pieces_180[p-1] += 5
return
def dfs_270(x,y,p):
table_270[x][y] = 0
for i in range(4):
dx,dy = directions[i]
if table_270[x+dx][y+dy]>0:
pieces_270[p-1] *= 6
pieces_270[p-1] += i+1
dfs_270(x+dx,y+dy,p)
pieces_270[p-1] *= 6
pieces_270[p-1] += 5
return
# 게임보드는 1이 아닌 0(구멍)을 기준으로 dfs해서 구멍 모양을 기록
def dfs_board(x,y,p):
game_board[x][y] = 1
for i in range(4):
dx,dy = directions[i]
if not game_board[x+dx][y+dy]:
holes[p-1] *= 6
holes[p-1] += i+1
dfs_board(x+dx,y+dy,p)
holes[p-1] *= 6
holes[p-1] += 5
return
pieces = []
size = []
directions = ((0,1),(1,0),(0,-1),(-1,0))
for i in range(n):
for j in range(n):
if table[i][j] > 0:
pieces.append(0)
size.append(0)
dfs(i,j,len(pieces))
pieces_90 = [0]*len(pieces)
pieces_180 = [0]*len(pieces)
pieces_270 = [0]*len(pieces)
for i in range(n):
for j in range(n):
if table_90[i][j]:
dfs_90(i,j,-table[n-1-j][i])
if table_180[i][j]:
dfs_180(i,j,-table[n-1-i][n-1-j])
if table_270[i][j]:
dfs_270(i,j,-table[j][n-1-i])
placed = [0]*len(pieces) # 게임보드에 이미 놓은 조각은 1로 표시
holes = []
for i in range(n):
for j in range(n):
if not game_board[i][j]:
holes.append(0)
dfs_board(i,j,len(holes))
for hole in holes:
for i in range(len(pieces)):
if not placed[i]:
if pieces[i] == hole or pieces_90[i] == hole or pieces_180[i] == hole or pieces_270[i] == hole:
placed[i] = size[i]
break
answer = sum(placed)
return answer