백준 2195 문자열 복사 python, java

문자열 복사지만 실제 복사를 하진 않는다.
인덱스를 이용해서 접근하는 방법을 사용했다.

📜 문제 바로 가기 : 문자열 복사

제출코드

파이썬

import sys
input = sys.stdin.readline

S = input().rstrip()
P = input().rstrip()

ans = 0
p_idx = 0 # 만들어야 하는 P문자의 인덱스
while p_idx < len(P):
    ans += 1
    max_Pidx = 0
    for i in range(len(S)):
        if S[i] == P[p_idx]: # 첫문자가 맞다면
            tmp_Pidx = p_idx
            for j in range(i, len(S)):
                if S[j] != P[tmp_Pidx]:
                    break
                tmp_Pidx += 1

                if tmp_Pidx == len(P):
                    break

            max_Pidx = max(max_Pidx, tmp_Pidx)

    p_idx = max_Pidx


print(ans)

자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        String S = br.readLine();
        String P = br.readLine();

        int ans = 0;
        int p_idx = 0;

        while (p_idx < P.length()) {
            ans += 1;
            int max_idx = 0;
            for (int i = 0; i < S.length(); i++) {
                if (S.charAt(i) == P.charAt(p_idx)) {
                    int tmp_idx = p_idx;
                    for (int j = i; j < S.length(); j++) {
                        if (S.charAt(j) != P.charAt(tmp_idx)) {
                            break;
                        }
                        tmp_idx += 1;

                        if (tmp_idx == P.length()) {
                            break;
                        }
                    }

                    max_idx = Math.max(max_idx, tmp_idx);
                }
            }

            p_idx = max_idx;

        }

        System.out.println(ans);

    }

}

---

접근방법

p_idx : 찾아야 할 차례의 P문자열의 인덱스값이다.
p_idx의 문자열로 시작하는 위치의 문자열 S의 인덱스를 찾으면 그부분부터 최대한 이어질 수 있는 부분까지 확인한다.
max_Pidx, tmp_Pidx 값을 사용하여 p_idx 부터 최대한 이어지는 길이를 찾아 p_idx 갱신한다.
p_idx 값이 P문자열의 길이를 넘어가면 종료한다.