AOJ -비밀 문자열 [java]

 

핵심 아이디어

S를 앞에서부터 훑으면서 T의 문자를 순서대로 매칭. T의 모든 문자를 매칭했으면 YES.

부분 수열(Subsequence) 문제입니다.

---

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine().trim();
        String T = br.readLine().trim();

        System.out.println(isSubsequence(S, T) ? "YES" : "NO");
    }

    static boolean isSubsequence(String S, String T) {
        int ti = 0; // T에서 현재 매칭할 위치

        for (int si = 0; si < S.length(); si++) {
            if (ti == T.length()) break; // T 전부 매칭 완료

            if (S.charAt(si) == T.charAt(ti)) {
                ti++; // T 다음 문자로 이동
            }
        }

        return ti == T.length(); // T를 전부 매칭했으면 YES
    }
}

---

예제 1 직접 추적

S = b a n a n a
T = b a a a

si=0: S[0]='b' == T[0]='b' → ti=1
si=1: S[1]='a' == T[1]='a' → ti=2
si=2: S[2]='n' != T[2]='a' → 패스
si=3: S[3]='a' == T[2]='a' → ti=3
si=4: S[4]='n' != T[3]='a' → 패스
si=5: S[5]='a' == T[3]='a' → ti=4

ti(4) == T.length(4) → YES ✅