흙금이네 블로그

[BOJ] 6550 - 부분 문자열 (Python, JavaScript) 본문

알고리즘

[BOJ] 6550 - 부분 문자열 (Python, JavaScript)

흙금 2023. 1. 25. 02:49

 

 

아이디어

 

순서대로 T에서 S의 문자들을 찾아 나간다.

 

 

풀이 #1 (Python)

 

테스트 케이스 수가 따로 주어지지 않으므로 sys.stdin.readlines으로 입력 값을 모두 읽는다.

각 테스트 케이스에서 find 메서드로 T에서 찾은 문자열 S의 문자들 인덱스를 차례로 idx에 저장하고,

그 다음 문자는 그 이후 인덱스부터 찾아 나가는 식으로 for문을 반복한다.

도중에 S의 문자가 T에 존재하지 않아 idx가 -1이 되면 No를 출력하고, S의 문자들을 모두 찾는 경우 Yes를 출력한다.

 

import sys

input = sys.stdin.readlines

for case in input():
    S, T = case.split()
    idx = -1
    for c in S:
        idx = T.find(c, idx+1)
        if idx < 0:
            print('No')
            break
    else:
        print('Yes')

 

 

T의 문자들을 모두 돌며 S의 문자들을 일일이 비교하는 코드보다 find 메서드로 찾아 나가는 코드가 더 빨랐다.

# 더 느린 코드
N = len(S)
idx = 0
for t in T:
    if t == S[idx]:
        idx += 1
        if idx >= N:
            print('Yes')
            break
else:
    print('No')

 

 

 

풀이 #2 (JavaScript)

 

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

입력 값에서 trim을 해주지 않으면 끝에 개행 문자가 하나 포함되어 split으로 인해 배열에 빈 문자열이 하나 더 생긴다.

 

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

for (let i=0; i<input.length; i++) {
    let [S, T] = input[i].split(' ');
    let N = S.length;
    let idx = -1;
    for (let j=0; j<N; j++) {
        idx = T.indexOf(S[j], idx+1);
        if (idx < 0) break;
    }
    if (idx < 0) console.log('No');
    else console.log('Yes');
}

 

Comments