흙금이네 블로그

아이디어 #1 라그랑주에 의해 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명되었으므로 7453번 - 합이 0인 네 정수처럼 두 제곱수를 더한 값들에서 투 포인터로 합이 n이 되는 네 제곱수를 찾는다. 풀이 #1 (Python) 딕셔너리 cnt_dict에 두 제곱수 합을 키로, 0이 아닌 제곱수의 개수를 값으로 저장한다. 입력 n이 50,000 이하로 주어지므로 제곱수의 제곱근은 223 이하로 설정하고, 0은 제곱수가 아닌 것으로 본다. 세트 numbers에 두 제곱수 합들을 저장한 후 numbers를 오름차순으로 정렬한 리스트로 대체한다. 투 포인터를 이용해 numbers에서 네 제곱수 합이 n인 경우를 찾아 최소 제곱수 개수를 갱신해 나간다. n = int(input()) c..

아이디어 문자열의 접두사와 접미사가 일치하면서 문자열 중간에 등장하는 가장 긴 부분 문자열을 찾는다. 풀이 문자열 S에 대한 부분 일치 테이블 lps를 만든다. S의 접두사와 접미사가 일치하면서 가장 긴 부분 문자열 S[-j:]가 문자열 S의 중간에 등장하면 S[-j:]를 출력한다. S의 중간에 등장하지 않으면 그 다음 길이의 부분 일치 문자열을 찾아 출력하고, 없으면 -1을 출력한다. lps[-1]이 0이면 슬라이싱이 S[-0:]로 되어 문자열 S를 나타내고, S는 S[1:-1]에 포함되지 않아 if문이 실행되지 않는다. 또 lps[-1]-1은 -1이 되어 lps[-1]을 가리키게 되므로 elif문도 실행하지 않고 else문의 -1을 출력한다. def solution(): S = input() N = ..

아이디어 가능한 세 자릿수에서 각 질문에 대한 대답에 따라 불가능한 경우를 제외해 나간다. 풀이 #1 (Python) 세트 numbers에 1~9의 숫자 중 서로 다른 숫자 세 개로 구성된 세 자릿수를 문자열로 저장한다. 질문마다 질문한 숫자는 문자열로 Q에, 스트라이크 개수와 볼 개수는 정수로 strike와 ball에 저장한다. numbers에 있는 수를 구성하는 각 숫자가 Q와 자릿값까지 같으면 s를, 그렇지 않고 Q에 포함되면 b를 증가시킨다. 해당 숫자의 s와 b가 각각 strike와 ball에 같다면 temp에 추가하고, for문 종료 후에 기존의 numbers를 temp로 대체한다. import sys input = sys.stdin.readline def solution(): numbers ..