접근 주어진 문자열의 각 문자를 결과 문자열(ans)에 추가한다. 만약 ans[-1] 이 폭발 문자열의 마지막 bomb[-1] 과 같다면 ans[-len(bomb):] 과 bomb[:] 을 비교하여 같으면 폭발시킨다. 사고 worst case time complexity 가 10**6 이길래 O(n) 으로 되는 문제인가 고민했다. 넉넉히 된다. 조건을 이해했을때 ‘모든 폭발 문자열이 폭발하고 새로운 문자열이 생긴다’ 여서 폭발 문자열을 발견할때마다 폭발하는거랑 결과가 혹시 다른가 고민해보았다. 반례가 떠오르지 않아 O(n) 스택으로 풀었다. 한가지 처음에 arr = arr[0:arr - len(bomb)] 이렇게 넣었다가 TLE 떴다. 저렇게 넣어도 파이썬이 optimization 하지 않을까 했는데 정직하게 주어진 인덱스만큼 복사하는것 같다. pop으로 뒤에 있는 문자열을 날리는 방법으로 풀어야 한다. ...
접근 열 길이가 기차의 수 + 1이고, 행 길이가 3인 dp 행렬로 접근한다. 13번째 행은 각각 현재 인덱스에서 13번째 열차가 골라졌다면 실을 수 있는 최대 손님의 수다. 입력으로 받은 train 리스트를 탐색하며 window 만큼 떨어져 있는 dp 를 업데이트 한다. dp 업데이트는 dp[현재 열 - window][현재행 - 1] 과 dp[현재 열 - 1][현재 행] 중 큰 것을 고른다. 사고 반복되는 연산을 최소화하는 DP 문제를 연습하는 중이니 다른 최적화도 가능하다면 시도해보자. 문제에서 소형 기관차의 길이가 길다면 겹치는 구간을 반복해서 구해야 할 것이다. ...
접근 방문 기록을 리스트로 기억한다. DFS 에 현재 탐색 중인 좌표들이 담긴 큐와 현재 위치를 인자로 받는다. 방문마다 방문 기록을 업데이트 해주고 DFS 를 진행한다. 방문한 곳을 마주하면 경우는 두 가지이다. Safe zone 으로 나갈 수 있는 경우, 만들어줘야 하는 경우. 사고 제약 조건이 적어 쉽게 접근할 수 있었다. 사이클을 찾으면 그 사이클과 사이클에 들어올 수 있는 모든 경로는 Safe Zone 하나로 도망 가능하다. 이 원칙 하나로 구현하면 큰 어려움 없이 풀 수 있다. ...
접근 위상 정렬을 이용해 현재 접근 가능한 수 중 가장 작은 값을 출력한다 N 사이즈의 풀 수 있는 다음 문제가 담긴 2차원 리스트, 접근하기 위해 풀어야 하는 선행 문제의 갯수가 담긴 int 리스트를 선언한다. M 개의 조건문을 받고 A -> B 를 바라보도록 리스트에 추가해준다. B 의 선행문제 갯수는 하나 올라간다. 선행문제 카운트 리스트를 훑으며 지금 진입 가능한 (선행문제가 0인) 문제 번호들을 Priority Queue 에 넣는다. Priority Queue 에서 값을 뽑는다. 이 문제가 바라보는 다음 문제들을 훝으며 각각의 선행 문제 갯수를 하나씩 뺀다. 이 과정에서 선행 문제 갯수가 0이 된 문제들을 Queue 에 추가해준다. 사고 혹시나 나처럼 헷갈리는 이들이 있을까 싶어 문제 조건을 확실히 해두고 싶다. ...
접근 처음 두 줄의 LCS 를 찾고, 그 결과와 마지막 줄의 LCS 를 찾는 순차적인 방법으로도 가능하다. 하지만 3차원 dp 로 처리하는 방법이 확장 가능성이 있기에 더 좋은 접근법이라 생각한다. import sys input = sys.stdin.readline f = input().strip() s = input().strip() t = input().strip() fl = len(f) sl = len(s) tl = len(t) dp = [[[-1] * tl for i in range(sl)] for j in range(fl)] def LCS(a, b, c): if a < 0 or b < 0 or c < 0: return 0 if dp[a][b][c] == -1: dp[a][b][c] = 0 if f[a] == s[b] == t[c]: dp[a][b][c] = LCS(a - 1, b - 1, c - 1) + 1 else: dp[a][b][c] = max(max(LCS(a, b - 1, c), LCS(a - 1, b, c)), LCS(a, b, c - 1)) return dp[a][b][c] print(LCS(fl - 1, sl - 1, tl - 1))
접근 dfs로 탐색을 하다 탐색한 부분이 다시 발견되면 cycle 이 성립한다. directed-graph 이기에 가능한 성질이다. 사고 단방향 그래프를 많이 다뤄보지 않아서 시간이 걸렸다. 처음에는 깊이 우선으로 탐색하다 방문한 곳이 나온다면 그 자리부터 한 바퀴를 세 주는 방법을 고려했다. 하지만 하나의 방문 확인 리스트로는 그 자리가 사이클 탐색까지 완료한 자리인지 아니면 사이클이 시작되는 자리인지 판단할 수 없다. 그래서 각각의 dfs가 시작될 때 temp_visited 를 따로 선언해주고 dfs 가 끝나면 temp_visited 에 들어간 자리들을 global_visited 에서도 업데이트해주었다. 우회적인 방법이라 판단되어 더 좋은 접근법이 얼마든지 있을 것 같다. ...