[Algorithm] 백준 문자열 문제 - 부분 문자열(6550) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅에 앞서, 최근에 제가 가고 싶었던 회사의 코딩테스트가 있었습니다.

준비를 안 한 것은 아니지만, 부족했고 정말 기본이라고 할 수 있는 문자열 문제에서 고생을 해서, 많은 자괴감이 들었습니다.

문자열에 대해서 다시 정리할 필요성을 느끼게 되어서 문자열 문제를 다시 풀어보았습니다.

 

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

6550번: 부분 문자열

 

1. 풀이 소스 

 

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

public class Main {
    
    static Queue<Character> queue = new ArrayDeque<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String str;
        String target;
        String seq;
        StringTokenizer st;
        
        while ((str = br.readLine()) != null && !str.equals("EOF")) { // 종료 조건은 문자열이 null이 아니고 EOF가 아니여야 함
            st = new StringTokenizer(str);
            target = st.nextToken();
            seq = st.nextToken();
            
            for (int i = 0; i < target.length(); i++) {
                queue.add(target.charAt(i)); // 큐에 target 문자열 넣기
            }
            
            for (int i = 0; i < seq.length(); i++) {
                if (queue.isEmpty()) break; // seq를 순회하며 target을 넣은 queue가 비면 종료
                if (queue.peek() == seq.charAt(i)) { // 만약 큐에 있는 문자열과 seq 문자열이 같다면 큐에서 빼기
                    queue.poll();
                }
            }

            if (queue.isEmpty()) { // 큐가 비어있다면 부분 문자열임을 의미 
                sb.append("Yes").append("\n");
            } else {
                while(!queue.isEmpty()) { // 큐를 다시 비워주기 
                    queue.poll();
                }
                sb.append("No").append("\n");
            }
        }
        
        System.out.print(sb);
    }
}

 

 

2. 풀이 중점 사항

 

종료 조건으로 str = br.readLine() && !str.equals("EOF")를 토대로 종료 조건을 처리해주어야 합니다.

부분 문자열을 구성하기 위해 queue를 이용하여 문자열을 담은 후, 큐에서 하나씩 빼며 문자열을 처리하도록 하였습니다

 

이상으로 백준 부분 문자열 문제 풀이를 마치도록 하겠습니다. 감사합니다.!