[BOJ] 20437 - 문자열 게임 2 (Python, JavaScript)

 

 

아이디어

 

W을 구성하는 문자들의 인덱스를 문자별로 저장해 인덱스 값의 차이로 문자열 길이를 구한다.

 

 

풀이 #1 (Python)

 

W를 구성하는 알파벳 소문자의 인덱스를 저장하기 위한 2차원 리스트 alpha를 만든다.

for문에서 함수 ord를 사용하여 W의 a부터 z를 0부터 25에 매칭해 alpha에 문자별로 W에서의 인덱스를 저장한다.

이후 alpha에서 문자별로 K개의 문자를 포함하는 문자열의 길이를 리스트 res에 추가해 나간다.

res에 값이 존재하면 res에서의 최솟값과 최댓값을 출력하고, 존재하지 않으면 -1을 출력한다.

 

import sys

input = sys.stdin.readline

def solution():
    T = int(input())
    for t in range(T):
        alpha = [[] for _ in range(26)]
        W = input().rstrip()
        K = int(input())
        for i in range(len(W)):
            alpha[ord(W[i])-97].append(i)
        res = []
        for a in alpha:
            N = len(a)
            if N >= K:
                for i in range(N-K+1):
                    res.append(a[i+K-1]-a[i]+1)
        if res:
            print(min(res), max(res))
        else:
            print(-1)

solution()

 

 

함수 내부에 작성하여 동작하도록 한 코드가 함수를 사용하지 않은 코드보다 더 빨랐다.

# 1.
import sys

input = sys.stdin.readline

T = int(input())
for t in range(T):
...

# 2. 더 빠른 코드
import sys

input = sys.stdin.readline

def solution():
    T = int(input())
    for t in range(T):
...

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1 코드와 마찬가지 방식으로 동작한다.

Array.from 메서드로 2차원 배열을 간편하게 만들 수 있는데, Array.from은 ES6부터 새로 추가된 문법이다.

자바스크립트에서는 charCodeAt 메서드로 문자를 아스키 코드로 변환한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

let T = input[0];
for (let t=1; t<input[0]*2; t+=2) {
    let W = input[t];
    let K = Number(input[t+1]);
    let alpha = Array.from(Array(26), () => new Array());
    for (let i=0; i<W.length; i++) alpha[W.charCodeAt(i)-97].push(i);
    let res = [];
    for (let a of alpha) {
        for (let i=0; i<a.length-K+1; i++) res.push(a[i+K-1]-a[i]+1);
    }
    if (res.length) console.log(Math.min(...res), Math.max(...res));
    else console.log(-1);
}

 

 

자바스크립트에서는 함수 내부에 작성한 코드와 그렇지 않은 코드의 메모리 사용량과 실행 시간 차이가 크지 않았다.

// 메모리는 더 많이 사용되나 더 빠른 코드
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function solution() {
    let T = input[0];
    for (let t=1; t<input[0]*2; t+=2) {
...