흙금이네 블로그

아이디어 KMP 알고리즘을 이용해 문자열 T에서 P를 찾을 때마다 그 위치를 추가해 나간다. 풀이 첫 번째 for문에서 문자열 P에서 접두사와 접미사가 일치하는 최대 길이를 투 포인터로 찾고 리스트 lps에 저장한다. i와 j가 가리키는 두 문자가 같으면 그 길이를 lps에 저장하고, 그렇지 않으면 lps를 참조해 비교할 문자 인덱스를 조정한다. lps에 저장된 길이가 곧 일치하는 부분 문자열 이후의 인덱스를 나타내므로 패턴이 일치한 부분은 비교를 건너뛸 수 있다. 두 번째 for문에서도 같은 방법으로 문자열 T에서 문자열 P를 찾고 P를 찾으면 그 위치를 리스트 idx_list에 추가한다. T = input() P = input() N, M = len(T), len(P) lps = [0]*M j = 0..

아이디어 BFS로 정리된 상태에서부터 초기 상태가 될 때까지 탐색해 나간다(반대의 경우도 가능). 풀이 퍼즐의 상태를 편리하게 나타내기 위해 문자열로 처리하고, 자리 이동이 가능한 인덱스들을 리스트 move에 저장한다. 초기 상태를 문자열로 result에 저장하고, 함수 find를 호출해 반환값을 출력하도록 한다. 함수 find에서는 덱 queue에 정리된 상태, 0의 위치, 이동 횟수를 튜플로 삽입하고 BFS한다. 초기 상태와 정리된 상태가 같은 경우 곧바로 0을 반환하고, queue가 빌 때까지 초기 상태가 되지 못하면 -1을 반환한다. 현재 상태 now, 0의 위치 idx, 현재 이동 횟수 cnt를 차례로 queue에서 꺼낸 다음, for문에서 이동 후의 상태 문자열 s를 만들고 s가 초기 상태 r..

아이디어 데드라인 오름차순으로 정렬 후 차례로 우선순위 큐에 추가해 컵라면을 많이 받을 수 있는 문제만 남긴다. 풀이 데드라인과 컵라면 수를 리스트 homework에 입력 받은 후 함수 solve를 호출한다. 함수 solve에서는 homework를 데드라인 오름차순으로 정렬한 후, for문으로 차례로 돈다. 데드라인이 우선순위 큐의 크기 cnt보다 크면 우선순위 큐 queue에 추가하고, 결과값을 컵라면 수만큼 증가시킨다. 그렇지 않다면 컵라면이 큐의 최솟값보다 클 때 최솟값 대신 현재 값을 큐에 넣고 결과값에 반영한다. import sys, heapq input = sys.stdin.readline def solve(): res = cnt = 0 homework.sort(key=lambda x: x[0..