[PS] 코딩테스트

저번 주에 봤던 모 기업의 코딩테스트 문제 중에 시간 안에 못 풀었던 문제를 메모해두었다가 다시 풀었다.

문제 1.

• 분류 : BFS
• 유사문제 : 백준 물통

l1, l2 = map(int,input().split())
from collections import deque
que = deque([(0,0)])
visited =[ [False] * (l2 + 1) for _ in range(l1 + 1)]
visited[0][0] = True
ans = set()

def add_que(node):
    if visited[node[0]][node[1]] == False:
        visited[node[0]][node[1]] = True
        que.append(node)

while que :
    now = que.popleft()

    ans.add(now[0])
    ans.add(now[1])

    add_que((l1,l2))
    add_que((l1, now[1]))
    add_que((now[0], l2))
    add_que((0, now[1]))
    add_que((now[0], 0))
    add_que((0,0))

    amount = min(l2-now[1], now[0])
    add_que((now[0]-amount, now[1]+amount))
    amount = min(l1-now[0], now[1])
    add_que((now[0] +amount, now[1]-amount))

ans.remove(0)
[ print(i, end=' ') for i in sorted(ans)]

풀이과정

• 두 개의 물통 A와 B가 있다고 가정한다.
• 가능한 액션
  1. 물통 가득 채우기
  2. 물통 다 비우기
  3. 다른 물통으로 물 옮기기
• (a물통에 남은 양, b물통에 남은양)으로 상태 체크 여부를 확인한다.

1. (0,0)으로 큐를 초기화한다.
2. 큐에서 꺼낸 노드(현재)에 가능한 액션을 모두 취한다
3. visited을 통해 액션을 취한 뒤의 노드가 이미 조회된 노드인지 판별한다.
4. 조회된 적 없으면 큐에 push한다.
5. pop한 노드의 값들을 set에 add하여 중복을 제거한다.
6. 마지막에 초기화를 위해 셋팅했던 0을 set에서 지우고 정렬하여 출력한다.

문제 2.

• 분류 : 투포인터, 슬라이딩 윈도우

road = list(input())
road = list(map(int, road))
n = int(input())
start, end = 0, 0
repair = [-1]

for i in range(len(road)):
    if road[i] == 0:
        if len(repair) == n+1:
            repair.pop(0)
        repair.append(i)

    l1 = end - start
    l2 = i+1 - repair[0]

    if l2 > l1 :
        start = repair[0] + 1
        end = i + 1

print(end-start)

풀이과정

• start, end는 가장 긴 배열의 시작과 끝을 가리킨다.
• repair에는 0 -> 1로 변경된 인덱스가 저장된다. (처음에는 없으므로 -1로 셋팅)
• l1 : 현재 start, end 포인터가 가리키는 배열의 길이
• l2 : 수정된 0 다음 부터 ~ 현재노드 포함한 길이

1. 현재 노드가 0 이면 repair에 넣는다. 길이가 n+1이면 맨 앞의 노드를 pop한다. (크기가 항상 n+1유지, 왜 n+1이냐면 가장 앞쪽의 수정된 노드를 알고 있어야 하기 때문이다. )
2. 현재 end- start 길이 vs 가장 왼쪽의 수정된 노드 다음부터 ~ 현재 노드 포함한 길이 비교
3. 후자가 더 크다면, start, end 갱신
4. end가 마지막노드때까지 반복
5. end-start하면 가장 큰 부분 배열의 길이를 출력하게 된다.