흙금이네 블로그

아이디어 동적 계획법으로 남은 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..

아이디어 리스트를 정렬해 성적이 낮은 학생 7명을 뽑는다. 풀이 성적을 저장할 리스트 scores에 초기값으로 100을 할당한다. 입력 받는 성적이 현재 scores에서 가장 높은 성적보다 작으면 더 작은 성적으로 대체하고 scores를 오름차순 정렬한다. 마지막에 하위 7명의 성적을 소수점 아래 세 자리까지 출력한다. import sys input = sys.stdin.readline N = int(input()) scores = [100]*7 for i in range(N): score = float(input()) if score < scores[6]: scores[6] = score scores.sort() for i in range(7): print(f'{scores[i]:.3f}') 힙을 사용..

아이디어 문자열의 접두사와 접미사가 일치하는 최대 길이를 구한다. 풀이 #1 KMP 알고리즘을 이용하여 부분 일치 테이블 lps를 구한 후, 맨 마지막 문자의 부분 일치 값을 전체 길이 N에서 뺀다. def last_lps(): S = input() lps = [0]*L j = 0 for i in range(1, L): while j > 0 and S[i] != S[j]: j = lps[j-1] if S[i] == S[j]: j += 1 lps[i] = j return lps[-1] L = int(input()) print(L-last_lps()) 테이블 생성 코드를 함수로 따로 빼지 않은 코드는 메모리 사용량은 비슷했으나 더 느렸다. # 더 느린 코드 L = int(input()) S = input()..

아이디어 정규 표현식에 따라 문자열을 처리해준다. 풀이 #1 (Python) re 모듈의 sub 함수를 이용하여 입력 받은 문자열을 조건에 맞게 파싱하고, 그 결과를 출력한다. import re li = [(r'', ''), (r'', '\n'), (r']*>', ''), (r'', ''), (r'', ''), (r' *', ''), (r' *', '\n'), (r' {2,}', ' '), (r'\n+$', '')] HTML = input() for p, s in li: HTML = re.sub(p, s, HTML) print(HTML) 풀이 #2 (JavaScript) 풀이 #1 코드와 마찬가지로 자바스크립트의 정규 표현식에 맞게 코드를 작성한다. const fs = require('fs'); cons..

아이디어 #1 비트마스킹으로 0~9의 수를 모두 사용했는지 여부를 확인하여 DP 테이블을 채워 값을 구한다. 풀이 #1 N, 시작 숫자, 사용 표시 비트 정보를 저장하는 3차원 리스트 dp를 생성하고, 0~9의 숫자에 대해 초기값을 설정한다. for문에서 0부터 1023(2진수 1111111111)까지의 비트로 해당 숫자를 사용하는 경우의 수를 dp에 누적하여 더해 나간다. 0과 9는 각각 1과 8에서 오는 경우를 더하고, 나머지 숫자들은 1만큼 차이나는 숫자로부터 오는 경우를 더한다. 시작 숫자가 1~9인 계단 수의 개수를 1,000,000,000로 나눈 나머지를 구해 출력한다. N = int(input()) dp = [[[0]*(1

아이디어 입력 받은 2차원 배열을 바깥쪽부터 안쪽으로 한 층씩 값을 R만큼 이동하여 새로운 2차원 리스트에 저장한다. 풀이 #1 (Python) N을 문자열로 입력 받고, 최종값을 저장하는 리스트 res를 만들고 함수 make_odd를 호출한다. 함수 make_odd에서 현재 숫자 n에서 홀수 개수를 total에 더하고, n의 길이를 m에 저장한다. 숫자의 길이가 1이면 total을 res에 추가하고 함수를 종료하고, 숫자의 길이가 2면 두 숫자를 더해 재귀 호출한다. 숫자의 길이가 3 이상이면 for문에서 i, j를 기준으로 n을 3개의 수로 분할하여 더한 값으로 재귀 호출한다. 함수가 모두 종료되면 res에서 최솟값과 최댓값을 출력한다. def make_odd(n, total): total += su..

아이디어 크기가 N인 순열로 만들어진 새로운 문자열의 패턴이 K가 되는 순열의 수를 구한다. 풀이 #1 입력 받은 단어들을 리스트 S_list에 저장하고, 순열을 만드는 함수 perm을 호출한다. 함수 perm의 for문에서는 차례로 순열에 따라 S_list의 단어를 배치하고 재귀 호출한다. 순열의 배치를 마치면 join으로 새로운 문자열을 만들고, 딕셔너리 S_dict에 문자열을 키로 문자열의 수를 저장한다. 함수 perm이 종료된 후 S_dict에 저장된 문자열 S와 문자열 수 cnt를 차례로 꺼내 문자열의 길이를 문자열 패턴의 길이로 나눈 값이 K이면 결과값 res에 cnt를 더한다. def perm(idx): if idx >= N: S = ''.join(S_list) if S in S_dict: ..

아이디어 입력 받은 2차원 배열을 바깥쪽부터 안쪽으로 한 층씩 값을 R만큼 이동하여 새로운 2차원 리스트에 저장한다. 풀이 #1 (Python) 원래 배열을 2차원 리스트 arr에 저장하고, arr과 같은 크기로 0으로 채워진 2차원 리스트 res를 생성한다. N과 M 중 더 작은 값을 2로 나눈 값만큼 for문을 반복하면서 리스트 바깥쪽에서 안쪽으로 접근한다. i, j는 현재 저장할 arr의 숫자 위치를 가리키고, r, c는 원래 위치에서 R만큼 회전하여 res에 저장할 위치를 가리킨다. d1과 d2는 하우상좌 순으로 인덱스 변화 값이 담긴 delta의 인덱스를 저장하는 변수로, 각각 arr과 res의 방향을 나타낸다. R만큼 회전한 위치를 r과 c에 저장하고, 현재 층의 값들을 모두 채울 때까지 wh..