one Book a Day

문자열 매칭 연습하기위해 kmp사용했고 사실 그냥 패턴을 기준으로 split하거나 replace로 변경시켜주면 더 쉽다. import sys sys.stdin = open('input.txt') def make_failure_function(p): failure_function = [0] * (len(pa)) counter = 0 for idx in range(1, len(p)): while counter > 0 and p[counter] != p[idx]: counter = failure_function[counter-1] if p[counter] == p[idx]: counter += 1 failure_function[idx] = counter return failure_function def kmp..

회문 1은 1개만 찾으면 됐지만 회문2는 모든 회문중 가장 긴 문자열을 찾는다. import sys sys.stdin = open('input.txt') def find_palindrome(sentences): for k in range(100, 0, -1): for i in range(100): for j in range(100-k+1): if sentences[i][j] == sentences[i][j+k-1]: left = j right = j+k-1 while sentences[i][left] == sentences[i][right] and left

dfs 탐색 진행했습니다. import sys sys.stdin = open('input.txt') def dfs(v): if v == 99: return True for u in graph[v]: if not visited[u]: visited[u] = True if dfs(u): return True for _ in range(10): test, edge_n = map(int, input().split()) graph = {i: [] for i in range(100)} edge_set = list(map(int, input().split())) visited = {i: False for i in range(100)} for i in range(0, edge_n*2, 2): graph[edge_set..

겹치는 구간이 몇개냐 세주면 된다. def count_bus(n): bus_stops = [0 for _ in range(5000)] for _ in range(n): start, end = map(int,input().split()) for i in range(start-1,end): bus_stops[i] += 1 P = int(input()) qa_set = [] for i in range(P): qa_set.append(bus_stops[int(input())-1]) return qa_set for test in range(1, int(input())+1): N = int(input()) answer = count_bus(N) print(f'#{test}', end=' ') print(*answer)

문자열이 다 빌때까지 제거하며 더해줬다. def read_vertical(s): answer = '' cnt = 0 while cnt

예전 강의실 배정문제처럼 풀었다. round가 반올림이 아니라 사사오입이라는걸 깨달은 아주 소중한문제.. 내 한시간.. from heapq import heappop,heappush from math import ceil def find_time_units(n): students = [] for _ in range(n): start, end = map(int,input().split()) if start > end: start, end = end, start start = ceil(start/2) end = ceil(end/2) students.append([start,end]) students.sort() time_units = [] heappush(time_units,students[0][1]) fo..

배열회전 너무 잘써먹는듯.. 대신 사고가 좀 갇히는것 같기도 하다. 다른 방법도 많은데 import sys input = sys.stdin.readline def rotate_clock(n, matrix): rot90 = [k[::-1] for k in zip(*matrix)] rot180 = [k[::-1] for k in zip(*rot90)] rot270 = [k[::-1] for k in zip(*rot180)] merge_matrix = [[] for _ in range(n)] for matrix in rot90,rot180,rot270: for i in range(n): merge_matrix[i].append(''.join(map(str,matrix[i]))) return merge_matr..

뒤에서부터 작은걸 만나면 그 차이만큼 결과에 더해줍니다. for test in range(1,int(input())+1): N = int(input()) prices = list(map(int, input().split())) answer = 0 max_price = 0 for j in range(N-1,-1,-1): if max_price > prices[j]: answer += max_price - prices[j] else: max_price = prices[j] print(f'#{test} {answer}')

널리 알려진대로 dp이용해서 풀이. import sys input = sys.stdin.readline def stick_paper(n): length = n//10 dp = [0] * (length+1) dp[0],dp[1] = 1,1 for i in range(2,length+1): dp[i] = dp[i-2]*2 + dp[i-1] return dp[length] for test in range(1,int(input())+1): print(f'#{test} {stick_paper(int(input()))}')

stack을 이용해 같은게 옆에있으면 같이 빼버린다. def repeat_str(s): init = len(s) stack = [] cnt = 0 while s: pre = s.pop() if stack: if pre == stack[-1]: stack.pop() cnt += 1 else: stack.append(pre) else: stack.append(pre) return init - 2*cnt for test in range(1,int(input())+1): s = list(input()) print(f'#{test} {repeat_str(s)}')