기록

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 풀이 입력 문자열 w를 배열 ans에 넣는다. 마지막으로 넣은 문자가 패턴 p의 마지막 문자와 같고 ans의 크기가 p의 크기보다 크다면 패턴 p의 마지막 문자부터 ans를 검사한다. 검사 결과가 true일때 패턴 p의 길이만큼 ans.pop() ans에 저장된 문자들을 join연산으로 붙여서 프린트한다. ans의 크기가 p의 크기를 비교하는 조건이 없으면, 뒤에서부터 문자열을 검사하는 코드에서 ans의 길이가 p보다 작을때 인덱스를 벗어나..

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 파이썬으로 작성한 코드는 시간초과로 테스트를 통과하지 못했다. N의 범위가 작다보니 정답 값을 리스트에 저장해서 통과하는 방법이 가능하다. 그 이외의 다른 방법을 찾지 못해 자바로 코드를 작성하였다. queen의 위치가 다음과 같을 때 [2, 4, 1, 3]처럼 저장할 수 있다. 1 1 queen 1 queen 2 2 2 3 3 3 queen 4 queen 4 4 후보자 n(1~N)은 arr의 각각의 원소에 대해 조건을 만족해야 한다. 1) 같은 행에 위치하지 않는다..

문제 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 풀이 파이썬을 이용한 풀이는 같은 방식으로 코드를 작성해도 시간초과로 테스트를 통과하지 못했다. 시간을 줄일 수 있는 해결방법을 찾지 못해서 자바로 풀이를 진행하였다. table에는 알파벳의 포함 여부를 기록한다. 단어별로 a부터 z까지 문자의 포함 여부를 기록하여, 단어 하나당 0부터 2**26(67108864)까지의 수를 저장한다. 쿼리의 내용은 비트 연산자를 이용하여 bitmask에 저장한다. table을 순회 하면서 (원래값&bitmask)==원래..

문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 1. 미세먼지의 확산 : 함수 diffusion "확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다."라고 명시하고 있기 때문에, 확산되는 먼지의 양은 '변화가 있기 전의 먼지/5'로 계산하여야 한다. BOARD NEW_BOARD 10 9 10 9 0 0 0 0 [초기값] BOARD NEW_BOARD 10-10/5-10/5 = 6 9+10/5 = 11 10 9 0+10/5 = 2 0 0 0 [(0, 0) 미세먼지 10의 확산] BOARD NEW_BO..

문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 풀이 1) 실패 함수 PI PI는 패턴에서 건너뛸 수 있는 문자의 개수를 의미하며 다음과 같이 구할 수 있다. ABAA의 PI = 1 접두사 접미사 접두사==접미사 1(문자의 개수) A A True 2(문자의 개수) AB AA False 3(문자의 개수) ABA BAA False A, AB, ABA, ABAA에 대해 위와 같은 방법으로 PI값을 구하면, [0, 0, 1, 1]이라는 배열을 얻을 수 있다. (인덱스 0은 0으로 연산) 위처럼 하나씩 ..

문제1016번: 제곱 ㄴㄴ 수첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.www.acmicpc.net풀이에라토스테네스의 체를 이용한 문제로, 위 코드에서는 1) 소수 구하기와 2) a, b사이의 값이 제곱수로 나누어지는지 확인하는 두 가지 기능이 한 번에 작성되어 있다. ans에 탐색해야하는 자연수의 개수를 담고, '제곱수의 배수'를 만날 때마다 1씩 값을 줄여나간다.코드def solution(a, b) : ans = b-a+1 prime = [i for i in range(floor(b**0.5)+1)] # 소수를 저장할 공간 num..