Algorithm
[Algorithm] 백준 문자열 문제 - 부분 문자열(6550) 자바 풀이
GOSE_KOSE
2023. 5. 16. 09:40
안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.
이번 포스팅에 앞서, 최근에 제가 가고 싶었던 회사의 코딩테스트가 있었습니다.
준비를 안 한 것은 아니지만, 부족했고 정말 기본이라고 할 수 있는 문자열 문제에서 고생을 해서, 많은 자괴감이 들었습니다.
문자열에 대해서 다시 정리할 필요성을 느끼게 되어서 문자열 문제를 다시 풀어보았습니다.
문제 출처: https://www.acmicpc.net/problem/6550
6550번: 부분 문자열
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.
www.acmicpc.net
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를 이용하여 문자열을 담은 후, 큐에서 하나씩 빼며 문자열을 처리하도록 하였습니다
이상으로 백준 부분 문자열 문제 풀이를 마치도록 하겠습니다. 감사합니다.!