흙금이네 블로그

아이디어 동적 계획법으로 남은 a와 z의 개수에 따른 조합의 수를 구한 후, 이분 탐색의 원리로 문자열을 찾아 나간다. 풀이 행은 a의 남은 개수, 열은 z의 남은 개수를 의미하는 (N+1)*(M+1) 크기의 2차원 리스트 dp를 만든다. 한 문자가 0개 남았을 때는 다른 문자 개수와 상관없이 모두 다른 문자로 채워지는 한 가지 경우이므로 1로 초기화한다. 두 문자 모두 0개 남은 dp[0][0]은 경우의 수로는 0이 맞으나 이후 코드에서 발생하는 예외를 위해 1로 채운다. K가 주어진 문자 a와 z로 조합할 수 있는 단어 수의 범위를 넘어서면 -1을 출력한다. 그렇지 않으면 i는 N-1, j는 M부터 두 값이 모두 0 이상일 동안 while문을 반복하며 결과값 res를 채워 나간다. a는 z보다 사전순..

아이디어 #1 2차원 리스트의 행마다 한 줄씩 입력 받고, 출력 시에는 열을 우선으로 탐색한다. 풀이 #1 (Python) 빈 리스트 li를 만들고 인덱스 에러 방지를 위해 입력 받은 문자열 끝에 14개의 별 문자를 붙여 li에 추가한다. 빈 문자열 res를 만들고, 이중 for문에서 열을 우선으로 li를 탐색하며 별 문자가 아닌 문자를 res에 붙여 나간다. li = [] for _ in range(5): S = input() li.append(S+'*'*14) res = '' for j in range(15): for i in range(5): if li[i][j] != '*': res += li[i][j] print(res) 풀이 #2 (JavaScript) 풀이 #1 코드와 마찬가지 원리로 동작한..

아이디어 A와 B를 XOR했을 때 0이 나오려면 두 수가 같아야 한다. 순환 순열이므로 A를 두 배로 늘린 문자열에서 B의 개수를 찾는다. 풀이 A와 B 두 문자열을 입력 받을 때, A는 두 번 반복하도록 한 후 함수 find를 호출하여 그 반환값을 출력한다. 함수 find에서는 B의 길이를 N에 저장하고 B의 부분 일치 테이블 lps를 구한다. 두 배로 늘린 A에서 인덱스 1부터 시작하여 B를 찾고, 그 개수를 res에 저장하여 반환한다. 현재 A는 원래 입력 받은 A를 두 번 반복하도록 했으므로 처음과 끝의 중복 계산을 막기 위해 인덱스 1부터 시작한다. def find(): N = len(B) lps = [0]*N j = 0 for i in range(1, N): while j > 0 and B[i..