흙금이네 블로그

아이디어 문자열의 접두사와 접미사가 일치하는 최대 길이를 구한다. 풀이 #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..

아이디어 n은 문자열 내에서 반복되는 패턴의 반복 횟수를 의미하므로, 입력 받은 문자열에서 반복되는 패턴의 길이를 찾은 후 문자열 길이를 패턴의 길이로 나눈다. 풀이 #1 while문에서 입력 받은 문자열 s가 마침표라면 break로 while문을 탈출한다. s를 두 번 더한 문자열에서 인덱스 0이 아닌 s의 인덱스를 찾고, 문자열 길이를 찾은 인덱스(패턴의 길이)로 나눈다. 11585번 속타는 저녁 메뉴의 풀이 #2와 같은 원리로 동작한다. while 1: s = input() if s == '.': break print(len(s)//(s*2).find(s, 1)) 풀이 #2 바다코끼리 연산자를 이용하면 숏코딩이 가능하다. while문의 조건식에서 s에 입력 값을 할당과 동시에 반환하면서 마침표가 아..

아이디어 2차원 리스트를 이용해 바깥쪽부터 안쪽으로 빈 공간에 숫자를 채워 나간다. 풀이 #1 (Python) 방향에 따라 행열 인덱스 변화 값 튜플을 반시계 방향인 하우상좌 순으로 리스트 delta에 저장한다. 함수 fill에서는 0으로 채워진 N*N 2차원 리스트 table를 만들고, N*N부터 1까지의 숫자를 (0, 0)부터 채워 나간다. 현재 숫자를 문자열로 인덱스에 맞게 리스트 table에 저장하고, 현재 숫자가 M이면 pos에 현재 좌표를 문자열로 저장한다. 다음 인덱스가 범위를 벗어나거나 해당 위치에 이미 값이 채워져 있으면 d를 증가시켜 방향을 전환한다. 값이 모두 채워진 리스트 table을 한 줄씩 공백으로 join하여 출력하고, 마지막 줄에 pos를 출력한다. delta = [(1, 0..

아이디어 하나의 코드를 슬라이싱하여 길이가 K인 부분 코드들을 만들고 다른 코드들에 부분 코드가 포함되어 있는지 확인한다. 풀이 처음 입력 받는 코드의 길이를 M, 코드를 정수로 리스트 P에 받고, 나머지 코드들은 문자열로 리스트 code_list에 추가한다. P를 길이가 K인 부분 코드로 슬라이싱하여 a에 문자열로 저장하고, b에는 반대로 뒤집은 코드 문자열을 저장한다. code_list에 있는 코드들에서 a 또는 b가 모두 포함되어 있으면 YES, 그렇지 않으면 NO를 출력한다. import sys input = sys.stdin.readline N, K = map(int, input().split()) code_list = [] M = int(input()) P = list(map(int, inpu..

문자형으로의 형 변환은 메서드에서 매개변수를 문자형으로 받는 등 문자형 값이 필요할 때 일어난다. alert 메서드에 다른 형의 값을 매개변수로 전달하면 그 값은 문자형으로 자동 변환된다. String(value) 함수를 호출해 값을 직접 문자열로 변환할 수도 있다. let value = true; alert(value); // true alert(String(true)); // true 숫자형으로의 형 변환은 수학과 관련된 함수와 표현식에서 자동으로 일어난다. Number(value) 함수를 사용하면 값을 숫자형으로 명시하여 변환할 수 있다. 숫자형으로 사용하고자 하는 값을 문자 기반 폼을 통해 입력 받는 경우, 명시적 형 변환을 해주어야 한다. alert('6'/'2'); // 3 alert(type..