[문자열, 구현] [3차] n진수 게임 (Lv.2)
접근 방식
구해야 할 숫자의 양을 대략 정해두고 반복문을 통해 처리한다.
10진수가 초과되면 A~F를 쓰기 때문에 문자열을 쓰게 되는데 계산하기 쉽도록 number라는 배열에 숫자들을 저장해두고 index값으로 계산하기로 했다.
자리수를 갱신하는 부분에 신경을 써야했다.
정답 코드
def convert(last, n):
number = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"]
result = ["0"]
current_index = 0
current_number = [0]
len = 1
while True:
if current_index == last + 1:
break
# current_number를 1올린다.
for i in range(-1, -len-1, -1):
current_number[i] += 1
if current_number[i] == n:
current_number[i] = 0
if i == -len:
current_number.insert(0, 1)
len += 1
else:
break
# current_number를 result에 넣어준다.
current_array = [number[i] for i in current_number]
result += current_array
# current_index를 1 올린다.
current_index += 1
return result
def solution(n, t, m, p):
answer = ''
last = p + (t - 1) * m
result = convert(last, n)
for i in range(p-1, last, m):
answer += result[i]
return answer배운점
구현하기 막막한 것들은 더욱 주석을 꼼꼼히 작성해야 한다.
[BFS] 리코쳇 로봇 (Lv.2)
접근 방식
처음엔 DFS로 1시간 가량 시도하였으나 최단거리를 구하는 것에는 BFS가 더 적절했다.
정답 코드
from collections import deque
def solution(board):
# board에서 R과 위치를 찾는다.
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == "R":
start = (i, j)
# BFS를 사용하여 최단 거리 계산
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
queue = deque([(start, 0)])
visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]
visited[start[0]][start[1]] = True
while queue:
current, depth = queue.popleft()
if board[current[0]][current[1]] == "G":
return depth
for i in range(4):
next_x = current[0] + dx[i]
next_y = current[1] + dy[i]
if next_x < 0 or next_x >= len(board) or next_y < 0 or next_y >= len(board[0]) or board[next_x][next_y] == "D":
continue
while True:
if next_x + dx[i] < 0 or next_x + dx[i] >= len(board) or next_y + dy[i] < 0 or next_y + dy[i] >= len(board[0]) or board[next_x + dx[i]][next_y + dy[i]] == "D":
break
next_x += dx[i]
next_y += dy[i]
if not visited[next_x][next_y]:
visited[next_x][next_y] = True
queue.append(((next_x, next_y), depth + 1))
return -1배운 점
DFS의 경우 백트래킹 문제에 쓰고, BFS의 경우 최단 거리를 찾을 때 유용하다 (간선의 가중치가 동일해야함)
[문자열, BFS] 단어 변환 (Lv.2)
접근 방식
최소 단계를 구하므로 BFS로 풀기로 했다.
begin에서 target으로 가는 과정이 같은 word라도 순서만 다를 수 있으므로 depth가 늘어날 때 visited 자체를 큐에 전달하는 방식으로 풀면 될 것 같다.
정답 코드
from collections import deque
def diff(word, compare):
cnt = 0
for i, w in enumerate(word):
if w != compare[i]:
cnt += 1
return cnt
def solution(begin, target, words):
if target not in words:
return 0
init_visited = [False for _ in range(len(words))]
queue = deque([(0, begin, init_visited)])
while queue:
depth, start, visited = queue.popleft()
for i, end in enumerate(words):
if diff(start, end) == 1 and not visited[i]:
# 만약 target 단어를 발견했으면 즉시 리턴
if end == target:
return depth + 1
new_visited = visited
new_visited[i] = True
queue.append((depth+1, end, new_visited))
return 0
배운 점
이 문제에서는 한 글자만 바꿔야 한다는 규칙이 있기 때문에 “big”, “cig” 끼리 비교할 때 한글자만 다른 것을 확인하는 로직이 필요했다.
그래서 나는
for i, w in enumerate(word):
if w != compare[i]:
cnt += 1이런식으로 enumerate 를 써서 했는데 모범답안을 보니
for c, w in zip(current, word):
if c != w:
count += 1이런식으로 zip 을 이용하는 방법이 있었다.
