[백준 알고리즘] 6550번 : 부분 문자열 (JAVA) 문제 풀이

문제

2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.

출력

입력된 s와 t의 순서대로 s가 t의 부분 문자열인 경우 Yes라 출력하고 아닐 경우 No라고 출력한다.

https://www.acmicpc.net/problem/6550

6550번: 부분 문자열

어떻게 풀 것인가?

문제를 처음 보았을때는 java의 다양한 문자열 관련 함수를 이용하여 풀려고 했다.

다만, 시간복잡도가 1초제한이라는 점과 처음에 문자열을 입력받는 부분에서 문제를 달리하여 풀어야겠다는 생각을 하였다.

그래서 단순하게 for문을 이용하여 2개의 문자열의 길이를 비교하는 방식으로 풀었다.

 

시간복잡도

시간복잡도는 가장 긴 문자 T의 문자의 길이만큼만 계산해주면 되기 때문에 O(N)이였다.

 

공간복잡도

공간 복잡도는 크게 고려하지 않았다.

 

풀면서 놓쳤던점

너무 어렵게 생각하지 말아야 겠다. 이제와서 보니 문제가 굉장히 쉬웠는데도 너무 어렵게 접근을 했던 것 같다.

 

이 문제를 통해 얻어갈 것

자바에서 문자열의 입력 방식과 문자열에 대한 새로운 접근을 배울 수 있었다.

 

내 코드 : 

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

public class Main {
	// 백준알고리즘 6550번 부분 문자열

	static String s;
	static String t;
	static String str;
	static int idx;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		while (true) {
			str = br.readLine();
			if(str == null) break;
		

			st = new StringTokenizer(str);

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

			idx = 0;

			for (int i = 0; i < t.length(); i++) {
				if (s.charAt(idx) == t.charAt(i)) {
					idx++;
				}
				if (idx == s.length()) {
					break;
				}
			}

			if (idx == s.length()) {
				sb.append("Yes").append('\n');
			} else {
				sb.append("No").append('\n');
			}

		}
		System.out.println(sb);

	}

}