목차
- 카드 게임
- Original 배열
- 로봇 청소기
3. 카드 게임
문제
당신은 친구와 카드 뒤집기 게임을 하고 있다.
카드 뒤집기 게임은 연속으로 배치된 카드 중에 인접한 2개의 카드가 '앞면( 1 )'일 때 해당 카드를 '뒷면( 0 )'으로 뒤집는 게임이다.
이 게임은 당신이 먼저 시작해서 더 이상 카드를 뒤집을 수 없을 때 까지 진행하게 되며, 마지막으로 카드를 뒤집는데 성공한 사람이 승리한다.
예를 들어, 초기 상태 cards = [1, 1, 1, 1] 로 주어졌다고 하자.
당신은 2번째와 3번째 카드를 뒤집어 [1, 0, 0, 1] 로 만들 수 있다.
그러면 상대방은 연속된 2개의 앞면이 없어 뒤집을 수 없기 때문에, 당신의 승리가 된다.
주어진 초기 상태 cards 에 대해서, 당신이 반드시 승리하는 방법이 있는지 여부를 출력하시오.
입력설명
- 0 < cards.length <= 100
출력 설명
확실한 승리법이 있는지 여부를 반환
매개변수 형식
cards = [1, 1, 0, 1, 1]
반환값 형식
false
풀이
이 문제는 다이나믹 프로그래밍 기법으로 메모제이션을 사용해서 풀 수 있다.
모든 경우의 수에 대해 탐색하기 위해 순차적으로 연속된 1을 찾아 그 값을 0으로 바꾼다.
그리고 연속된 1이 없는 경우 내가 지게된다. 여기서 부터 백트래킹으로 승패여부를 결정한다.
핵심 아이디어는 연속된 1이 없는 시점 n이 내 차례라면 나는 지게된다.
- n(나): 패배
그러나 n-1시점이 내 차례라면 n시점이 상대방 차례 일 것임으로 나는 이기게 된다.
- n - 1(나) → n (상대) 패배
마찬가지로 n-2시점이 내 차례라면 다시 나는 지게 된다. n - 2(나) → n - 1(상대) → n(나)
이렇게 연속된 1이 없는 n시점을 패배로 두고 백트레킹을 해가면서 각 시점의 카드 상태를 dp 테이블에 저장해둔다.
스탭별로 봐보자. 순차적으로 연속된 1을 바꾼 값을 다시 dfs로 호출한다.
아래 state는 cards를 튜플형태로 변경한 값이다.
튜플로 변경한 이유는 memo라는 dp테이블에 key값으로 활용하기 위해서이다.
딕셔너리의 key값은 immutable 해야 하기때문에 리스트가 아닌 튜플로와야 한다.
def dfs(state):
# 탈출조건
for i in range(len(state)-1):
if cards[i] == 1 and cards[i+1] == 1: # 연속으로 1이면
# 그 값을 0으로 변경, 튜플임으로 리스트로 변경
new_state = list(state)
new_state[i], new_state[i+1] = 0, 0
result = dfs(tuple(new_state))예를들어 주어진 카드가 [1, 1, 1, 1] 이였다면 첫번째 순서에서 [0, 0, 1, 1] 된다. 여기서 dfs를 호출하여 다시 연속된 1을 찾고 그값을 0으로 바꾼다.
이렇게 하는 이유는 현재 예시는 [0, 0, 1, 1] 이지만 [1, 1, 0, 1, 1]인 경우:
- 앞에 연속되는 1을 두 개 제거하는 경우: [0, 0, 0, 1, 1]
- 뒤에 연속되는 1을 두 개 제거하는 경우: [1, 1, 0, 0, 0]
로 분기가 되기 때문에 dfs로 호출하여 다르게 처리해줘야 한다.
최종적으로는 이렇게 된다: [0, 0, 0, 0]
그렇게 1이 아무것도 없게되는 경우 나는 지게됨으로 memo[(0, 0, 0, 0)] = False를 기록해주고 False를 리턴한다. 그럼 이전 시점이 내 차례라면 이긴다는 뜻임으로 memo[(1, 1, 0, 0)] = True가 된다.
현재 상태를 저장하는 이유는 중복된 경우에 대한 탐색을 효율적으로 계산하기 위해서다.
def dfs(state):
# 탈출조건
if memo in state:
return state
for i in range(len(state)-1):
if cards[i] == 1 and cards[i+1] == 1: # 연속으로 1이면
# 그 값을 0으로 변경, 튜플임으로 리스트로 변경
new_state = list(state)
new_state[i], new_state[i+1] = 0, 0
result = dfs(tuple(new_state))
if not result:
memo[state] = True
return True
memo[state] = False
return False코드를 정리하면 아래와 같다.
전체코드
def solution(cards):
# 상태를 튜플로 변환 (리스트는 해시 불가능)
state = tuple(cards)
# 메모이제이션을 위한 딕셔너리
memo = {}
def dfs(state):
# 이미 계산한 상태는 재사용
if state in memo:
return memo[state]
# 현재 상태에서 가능한 모든 움직임을 확인
for i in range(len(state) - 1):
# 연속된 두 개의 카드가 1인 경우에만 뒤집기 가능
if state[i] == 1 and state[i + 1] == 1:
# 새로운 상태 생성
new_state = list(state)
new_state[i], new_state[i + 1] = 0, 0
# 상대방이 새로운 상태에서 어떤 움직임을 해도 이길 수 있다면
if not dfs(tuple(new_state)):
memo[state] = True
return True
# 어떤 경우에도 승리할 수 없다면 False
memo[state] = False
return False
return dfs(state)TestCase
# Test1
입력값 〉 [1, 1, 0, 1, 1]
기댓값 〉 false
# Test2
입력값 〉 [1, 1, 1, 1]
기댓값 〉 true4. Original 배열
문제
어떤 정수 배열 original 이 있다고 가정하자.
이 정수 배열은 중복된 값이 있을 수 있으며, 오름차순으로 정렬되어 있다.
이 정수 배열의 모든 값에 2를 곱한 뒤, 기존의 배열과 함께 임의로 섞는 변환을 적용하여 만든 배열을 nums 라고 하자.
예를 들어, original = {1, 4, 5} 인 경우, nums는 {1, 4, 5 , 2, 8, 10} 을 포함하여 순서가 다른 모든 배열이 될 수 있다.
nums 배열이 주어졌을 때, original 배열을 찾아 출력하시오.
nums 배열이 어떤 배열을 변환해서도 만들 수 없다면 빈 배열을 출력하시오.
입력설명
- 0 < nums.length <= 10000
출력 설명
original 배열을 구해 정수 배열로 반환
매개변수 형식
nums = {1, 8, 2, 4, 5, 10}
반환값 형식
{1, 4, 5}
풀이
이 문제에서 알 수 있는것은 자신의 두배의 값이 같은 리스트에 들어있으니 주어진 리스트의 합이 원본 리스트의 합이 3배임으로 원본 리스트는 주어진 리스트 합 / 3 이라는 것을 알 수 있고
원본 리스트의 갯수는 전체 리스트의 절반이라는 점이다.
따라서 모든 조합에 대하여 위 두 조건을 만족하면 정렬해서 리턴하도록 하였다.
그러나 주어진 테스트 케이스에 대해서는 통과하나 이후 테스트 케이스에 대해서는 타임아웃이 발생한다.
import itertools
def solution(nums):
total = sum(nums)
half_size = len(nums) //2
if total % 3 != 0:
return []
original_sum = total // 3
perms = list(itertools.combinations(nums, half_size))
for perm in perms:
if sum(perm) == original_sum:
return sorted(perm)
return []이 문제를 어떻게 최적화할 수 있는 다른 방법은 Counter를 사용하는 것이다.
하나씩 탐색하다가 자신보다 두배가 되는 값이 있으면 자신과 두 배의 숫자를 제거하는 식으로 동작한다.
import collections
def solution(nums):
counters = collections.Counter(nums)
results = []
for num in nums:
if counters[num] == 0: # A조건
continue
if counters[num*2] == 0: # B조건
return []
results.append(num)
counters[num] -= 1
counters[num*2] -= 1
return results
그런데 이 과정에서 사전에 정렬이 이뤄져야 한다.
왜냐하면 만약 배열이 [1, 8, 2, 4, 5, 10] 이렇게 되어있다고 하자. 그럼 아래와 같은 문제가 생긴다.
nums = 1results = [1]counters = {1: 0, 2: 0, 4: 1, 5: 1, 8: 1, 10: 1}
nums = 8B조건에 의해return []
num = 8 일때 그 두배인 16이 있어야하는데 이 값은 존재하지 않아 B조건이 참이되어 빈 리스트가 반환된다.
그러나 사전 정렬이된 배열이라면 [1, 2, 4, 5, 8, 10] 가 되면 아래 순서대로 진행되며 정답을 얻어낼 수 있다.
nums = 1results = [1]counters = {1: 0, 2: 0, 4: 1, 5: 1, 8: 1, 10: 1}
nums = 2counters[2] = 0 임으로 continue
num = 4results = [1, 4]counters = {1: 0, 2: 0, 4: 0, 5: 1, 8: 0, 10: 1}
num = 5results = [1, 4, 10]counters = {1: 0, 2: 0, 4: 0, 5: 0, 8: 0, 10: 0}
nums = 8- A조건에 의해 Continue..
- nums = 10
- A조건에 의해 Continue..
배열의 끝에 도달하게 되어 성공적으로 답을 얻어내며 정렬시간(O(nlogn) + 탐색시간 O(n) 가 된다.
전체코드
from collections import Counter
def solution(nums):
# nums의 길이가 홀수면 조건을 만족할 수 없음
if len(nums) % 2 != 0:
return []
# 오름차순 정렬
nums.sort()
# 숫자 빈도 카운트
count = Counter(nums)
original = []
for num in nums:
# 현재 숫자가 이미 매칭된 경우 건너뜀
if count[num] == 0:
continue
# 2배 값이 없으면 원래 배열을 구성할 수 없음
if count[num * 2] == 0:
return []
# 원래 배열에 추가
original.append(num)
# 사용한 숫자 빈도 감소
count[num] -= 1
count[num * 2] -= 1
return originalTestCase
# Test 1
입력값 〉 [1, 8, 2, 4, 5, 10]
기댓값 〉 [1, 4, 5]
# Test 2
입력값 〉 [20, 16, 8, 18, 9, 4, 8, 6, 12, 10]
기댓값 〉 [4, 6, 8, 9, 10]5. 로봇 청소기
문제
당신은 이번에 동아리에서 주최하는 로봇청소기 만들기 대회에 참가하게 되었다.
당신은 복잡한 알고리즘을 만들기에 앞서, 단순한 로봇을 만들어 동작을 실험해보려 한다.
당신이 만든 기초적인 로봇청소기의 동작은 다음과 같다.
- (0, 0) 좌표에서 오른쪽을 보고 출발한다.
- (0, 0) 좌표에서 (0, 1) 좌표를 바라본 방향을 오른쪽으로한다.
- 아래 스텝을 반복한다.
- 현재 위치를 청소한다.
- 바로 앞으로 이동할 수 있으면 이동한다.
- 바로 앞으로 이동할 수 없으면 시계방향으로 90도 회전한다.
당신은 로봇청소기를 2차원 정수 배열로 표현된 board에서 테스트하려 한다.
board[t][j] 에는 (t, j) 좌표의 상태가 기록되어 있으며, 이 상태는 아래와 같다.
- 0: 청소를 해야 하는 일반 바닥
- 1: 로봇청소기가 통과할 수 없는 장애물
이 때, 청소가 되는 칸의 수를 정수로 반환하시오.
입력설명
- 0 <
board.length<= 100 - 0 <
board[i].length<= 100
매개변수 형식
board = {{0, 0, 0, 0},
{0, 1, 1, 0},
{0, 0, 0, 0},
{1, 0, 1, 1}}반환값 형식
10
풀이
이 문제는 bfs최단 경로 찾기와 유사하며 차이점은 진행할 수 있는 방향이 있다면 그 방향으로 계속 움직이다, 벽에 막혀있으면 90도씩 회전하는 것에 차이가 있다
해당 부분은 directions로 각각 90도의 방향으로(첫 방향은 [0, 1]) 회전하게 끔 설정하고 자신의 방향도 같이 큐에 담도록 하여 진행하여 모든 방향에 대해 90도씩 회전하다가 없으면 더 이상 청소가 불가능 함으로 거리를 리턴하도록 하였다
예시 입출력 설명
아래 -로 표기한 10칸이 청소된다.
----
-11-
----
1011def solution(board):
def bfs(end):
rows = len(board)
cols = len(board[0])
visited = [[False]*cols for _ in range(rows)]
start = (0, 0)
#visited[start[0]][start[1]] = True
dist = d = 0
que = collections.deque([])
que.append((start[0], start[1], d, dist))
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while que:
x, y, d, dist = que.popleft()
for _ in range(len(directions)):
dx, dy = directions[d]
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols:
if not visited[nx][ny] and board[nx][ny] != 1:
visited[nx][ny] = True
que.append((nx, ny, d, dist+1))
break
d = (d+1) % 4
return distTestCase
# Test 1
입력값 〉 [[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
[1, 0, 1, 1]]
기댓값 〉 10
# Test 2
입력값 〉 [[0, 0, 1, 0],
[0, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0]]
기댓값 〉 4출처
해당 문제와 코드는 제로베이스(ZeroBase)에서 제공받았습니다.
모든 자료는 저작권법에 의하여 보호받는 저작물로서 이에 대한 무단 복제 및 배포를 원칙적으로 금합니다.
Comment