백준 6550 - 부분 문자열(자바-그리디)

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

6550번: 부분 문자열

 

* 문제 요약

2개의 문자열 s 와 t 가 주어졌을 때, s 가 t 의 부분 문자열인지 판단하는 프로그램을 작성하라.

부분 문자열을 가지고 있는지 판단하는 방법은 t 에서 몇개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기한다.

 

* 입력

- 여러개의 테스트 케이스로 이루어져 있다.

- 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t 가 빈 칸을 사이에 두고 들어온다.

- s 와 t 의 길이는 10만을 넘지 않는다.

 

* 출력

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

 

* 예시

 

* 해결 과정

- 문자열 s 와 t 를 input 배열의 0, 1번째 인덱스로 각각 저장한다.

- 문자열 s 의 길이를 기준으로 바깥 반복문을 시작한다.

- 문자열 t 의 각 인덱스 별 글자를 탐색하기 위한 index 변수를 초기화 해두고, 문자열 t 의 길이를 기준으로 안쪽 반복문을 시작한다.

- 현재 문자열 s 의 i 번째 글자와, 문자열 t 의 index 번째 글자를 비교하여, 서로 같은 경우 정답 문자열 sb 에 문자열 s의 i 번째 글자를 추가해주고 index 변수에 1 을 더하여 문자열 t 의 다음 글자를 볼 수 있게끔 해준 뒤 안쪽 반복문을 종료시킨다.

- 만약 문자열 t 의 끝까지 문자열 s 의 i 번째 글자와 똑같은 글자를 찾지 못했다면, 문자열 t 안에 문자열 s 가 부분 문자열로 존재하지 않는다는 뜻이므로 바깥 반복문 까지 종료시킨다.

- 위의 과정이 끝난 후 정답 문자열 sb 와 input 배열의 0 번째 인덱스, 즉 문자열 s 가 서로 같다면 Yes 를 출력, 그렇지 않다면 No 를 출력해준다. 

 

* 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            String str = br.readLine();
            if (str == null)
                break;
            else {
                String[] input = str.split(" ");
                int index = 0;
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < input[0].length(); i++) {
                    boolean check = false;
                    while (index < input[1].length()) {
                        if (input[0].charAt(i) == input[1].charAt(index)) {
                            sb.append(String.valueOf(input[0].charAt(i)));
                            check = true;
                            index++;
                            break;
                        } else {
                            index++;
                        }
                    }
                    if (!check) {
                        break;
                    }
                }
                if (sb.toString().equals(input[0])) {
                    bw.write("Yes\n");
                } else {
                    bw.write("No\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

각 상황마다 문자열 s 의 i 번째 글자와, 문자열 t 의 index 번째 글자를 비교하여 조건에 맞는 처리를 해주는 방식으로 문제를 풀었다.

반복문의 각 단계별로 조건에 맞춰 최적의 판단을 하는 방식으로 풀었으므로 그리디 알고리즘 문제라고 볼 수 있다.