흙금이네 블로그

아이디어 #1 룰렛 칸 수의 약수 크기인 룰렛 일부로 전체 룰렛을 구성할 수 있는지 확인한다. 풀이 #1 공백을 없앤 문자열 roulette으로 룰렛 모양을 입력 받은 후 함수 spin을 호출하여 반환값을 출력한다. 함수 roulette에서는 for문에서 i가 N의 약수일 때 그 크기만큼 슬라이싱한 룰렛 일부(패턴)를 전체 룰렛에서 찾는다. 찾은 개수 cnt가 룰렛 전체 크기를 패턴의 크기로 나눈 값과 같으면 1/i를 반환한다. 확률은 패턴 개수를 전체 크기로 나눈 값인데, cnt는 N의 약수이고 N을 cnt로 나눈 값은 결국 i이므로 1/i가 기약분수다. def spin(): for i in range(1, N+1): if N%i == 0: cnt = roulette.count(roulette[:i])..

아이디어 명령어에 따라 전구 상태를 변경한다. 풀이 #1 (Python) 입력된 명령어에 따라 전구 상태 리스트 bulb의 상태 값을 슬라이싱을 이용해 변경한다. import sys input = sys.stdin.readline N, M = map(int, input().split()) bulb = list(map(int, input().split())) for _ in range(M): a, b, c = map(int, input().split()) if a == 1: bulb[b-1] = c elif a == 2: bulb[b-1:c] = [1-i for i in bulb[b-1:c]] elif a == 3: bulb[b-1:c] = [0]*(c-b+1) else: bulb[b-1:c] = [1]*..

아이디어 수열을 뒤집어 KMP 알고리즘으로 접근한다. 풀이 수열 리스트 A를 뒤집어 저장한 다음, 부분 일치 테이블 lps에 일치하는 길이를 저장한다. 앞뒤수열이 존재하면 lps에서 가장 큰 값(앞뒤계수 최댓값)과 그 개수를 출력하고, 그렇지 않으면 -1을 출력한다. N = int(input()) A = list(map(int, input().split()))[::-1] lps = [0]*N j = 0 for i in range(1, N): while j > 0 and A[i] != A[j]: j = lps[j-1] if A[i] == A[j]: j += 1 lps[i] = j max_len = max(lps) if max_len > 0: print(max_len, lps.count(max_len)) e..

아이디어 문자열의 접두사와 접미사가 겹치는 부분의 길이만큼 줄일 수 있다. 풀이 KMP 알고리즘으로 부분 일치 테이블 lps를 만든 후, 문자열 S의 길이 N을 K번 더한 값에서 접두사와 접미사가 일치하는 부분 lps[-1]을 K-1번 더한 값을 빼준다. S, K = input().split() K = int(K) N = len(S) lps = [0]*N j = 0 for i in range(1, N): while j > 0 and S[i] != S[j]: j = lps[j-1] if S[i] == S[j]: j += 1 lps[i] = j res = N+(N-lps[-1])*(K-1) print(res)

아이디어 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..

아이디어 위상 정렬로 각 도시에 도착하는 가장 늦는 시간을 구한 뒤, 도착지로부터 역으로 쉬지 않고 달리는 도로를 찾아 나간다. 풀이 입력 값들의 관계에 따라 출발 도시 리스트 parent와 도착 도시 리스트 child에 도시와 시간을 저장하고, 입력차수 리스트 degree에서 도착 도시 번호의 입력차수 값을 증가시켜 나간 후 함수 find_time과 find_road를 호출한다. 함수 find_time는 BFS로 각 도시에 도착하는 가장 늦는 시간을 구해 리스트 max_time에 저장한다. 가장 늦는 시간을 구하기 위해 방문하려는 도시의 진입차수 degree 값이 0이 되면 큐에 넣고 탐색하도록 한다. 함수 find_road는 BFS로 두 도시의 max_time 값의 차를 구해 해당 도로를 지나는 시간..

아이디어 #1 두 배열씩 묶어 하나의 배열로 총 두 개의 배열을 만든 후, 투 포인터로 합친 배열 값들의 합이 0인 경우를 찾는다. 풀이 #1 입력 값들을 리스트 A, B, C, D에 저장하고, A와 B를 합친 리스트 AB, C와 D를 합친 리스트 CD를 만들어 정렬한다. 투 포인터로 두 리스트 AB와 CD의 원소 합이 0인 경우를 찾고, 중복 값이 있는 경우 그 경우의 수를 구해 결과값에 더한다. Python 3로는 시간 초과가 나고, PyPy3로 제출해서 통과할 수 있었다. import sys input = sys.stdin.readline N = int(input()) A, B, C, D = [], [], [], [] for _ in range(N): a, b, c, d = map(int, inpu..

alert 함수는 사용자가 확인 버튼을 누를 때까지 메시지를 보여주는 모달 창을 띄운다. alert('Hello'); prompt 함수는 텍스트 메시지와 입력 필드, 확인 및 취소 버튼이 있는 모달 창을 띄운다. title은 사용자에게 보여줄 문자열, default는 입력 필드의 초기값으로 생략할 수 있다([...] 안의 매개변수는 선택값). prompt(title, [default]); prompt 함수는 사용자가 입력 필드에 입력한 문자열을 반환하며, 취소 버튼이나 Esc를 누른 경우 null이 반환된다. let age = prompt('나이는?', 27); alert(age); IE에서는 입력 필드 초기값을 설정하지 않는 경우 undefined를 명시한다. IE 외의 브라우저에서도 두 번째 매개변수..