[Baekjoon] 6550_부분 문자열

Silver V

문제(출처: https://www.acmicpc.net/problem/6550)

---

< 부분 문자열 >

 

문제 풀이 

 

s가 t의 부분 문자열인지 확인한다.

 

 

 my solution (Java)

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

public class _6550_ { // 부분 문자열

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		String str = "";
		while ((str = bf.readLine()) != null) {
			st = new StringTokenizer(str);

			String s = st.nextToken();
			String t = st.nextToken();

			int arr[][] = new int[s.length() + 1][t.length() + 1];

			for (int i = 0; i < s.length(); i++) {
				for (int j = 0; j < t.length(); j++) {
					if (s.charAt(i) == t.charAt(j)) {
						arr[i + 1][j + 1] = Math.max(arr[i][j] + 1, arr[i][j + 1]);
					} else {
						arr[i + 1][j + 1] = Math.max(arr[i][j + 1], arr[i + 1][j]);
					}
				}
			}
			if (arr[s.length()][t.length()] == s.length()) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}
}

 

Main

변수)
str , s, t : 입력받은 문자열
arr : 부분 문자열

 

문자열을 각각 입력받은 후 두 문자열의 부분 문자열을 찾는다. 그 후 부분 문자열의 최대 개수가 s의 문자열 길이와 같다면 s가 t의 부분 문자열이란 뜻이므로 Yes를 출력하고 s의 문자열 길이와 같지 않다면 No를 출력한다.

---

---