일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 백준
- php 프로그래밍 입문 3판
- 페이코 추천인코드
- 자바
- 자바 스프링
- php 프로그래밍 입문 예제
- php 프로그래밍 입문 문제풀이
- 페이코 친구코드
- C언어
- php 프로그래밍
- 페이코 추천인
- 플러터
- 배열
- php 프로그래밍 입문 솔루션
- C
- programmers
- php 프로그래밍 입문
- 스프링
- 파이썬
- php
- JAVA SPRING
- 페이코 초대코드
- Flutter
- Java
- 플러터 개발환경 설정
- 한정 분기
- php 프로그래밍 입문 연습문제
- 최단 경로
- SWEA
- spring
Archives
- Today
- Total
11-07 11:40
ImJay
[BOJ/Java] 9935. 문자열 폭발 본문
반응형
[BOJ/Java] 9935. 문자열 폭발
문제 해석
"문자열 폭발" 문제는 주어진 문자열에서 특정 "폭발 문자열"이 있을 경우, 그 문자열을 모두 제거하고, 제거 후 남은 문자열에 다시 폭발 문자열이 포함되어 있다면 이를 반복적으로 제거하는 과정을 거쳐 최종적으로 남은 문자열을 반환하는 문제다. 만약 모든 문자가 제거될 경우 "FRULA"를 출력한다. 이 문제는 특히 문자열 처리와 스택을 활용하는 알고리즘 설계 능력을 요구한다.
풀이 과정
이 문제를 해결하기 위해 스택을 활용하는 방법을 채택했다. 스택을 사용하는 이유는 문자열의 폭발이 발생할 때 효율적으로 문자를 제거하기 위해서이다. 다음과 같은 절차로 문제를 해결한다:
- 입력받은 문자열을 순회하면서 각 문자를 스택에 쌓는다.
- 새로운 문자가 스택에 추가될 때마다, 스택의 크기가 폭발 문자열의 길이 이상인지 확인한다.
- 스택의 크기가 폭발 문자열의 길이 이상일 경우, 스택의 최근 문자들과 폭발 문자열을 비교한다.
- 폭발 문자열과 일치하면 해당 문자들을 스택에서 제거한다.
- 모든 문자를 처리한 후, 스택에 남은 문자들을 문자열로 변환하여 반환한다.
- 스택이 비어있으면 "FRULA"를 출력한다.
이 과정에서 스택을 사용하면 각 문자의 추가 및 제거가 O(1) 시간에 이루어져서 전체적인 시간 복잡도를 효율적으로 관리할 수 있다.
코드
package edu.ssafy.im.BOJ.Gold.G4.No9935;
import java.io.*;
import java.util.Stack;
public class Main {
private static char[] s;
private static char[] b;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
s = br.readLine().toCharArray(); // 입력받은 문자열을 문자 배열로 변환
b = br.readLine().toCharArray(); // 폭발 문자열을 문자 배열로 변환
sb.append(sol()); // 처리 결과를 StringBuilder에 추가
bw.write(sb.toString()); // 결과를 출력
bw.flush();
bw.close();
}
private static String sol() {
Stack<Character> stack = new Stack<>();
for (char c : s) {
stack.push(c); // 문자를 하나씩 스택에 쌓는다
if (stack.size() < b.length) continue; // 스택의 크기가 폭발 문자열보다 작으면 다음 문자 처리
// 폭발 문자열과 스택의 최근 문자들을 비교
boolean flag = true;
for (int j = 0; j < b.length; j++) {
if (stack.get(stack.size() - b.length + j) != b[j]) {
flag = false; // 하나라도 다르면 폭발하지 않음
break;
}
}
// 폭발 문자열이면 해당 문자들을 스택에서 제거
if (flag) for (char t : b) stack.pop();
}
StringBuilder sb = new StringBuilder();
for(char c : stack) sb.append(c); // 스택에 남은 문자를 StringBuilder에 추가
return stack.isEmpty() ? "FRULA" : sb.toString(); // 결과 문자열 반환
}
}
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 주로 문자열 s를 순회하는 O(N)과 각 문자에 대해 최대 폭발 문자열 길이만큼 비교하는 O(M)의 곱, 즉 O(N*M)이 된다. 여기서 N은 입력 문자열의 길이이고, M은 폭발 문자열의 길이이다. 그러나 스택의 효율적인 사용으로 불필요한 반복을 줄이고 있어 실제 성능은 이보다 좋을 수 있다.
느낀점
스택을 활용하여 문자열 폭발 문제를 풀이하는 방법은 문자열 조작과 관련된 다양한 문제에 응용할 수 있는 효율적인 접근 방식을 제공한다. 이 문제를 통해 문자열 처리 기술과 자료 구조를 사용하여 문제를 해결하는 능력을 향상시킬 수 있었다.
반응형
'알고리즘 > BOJ - Java' 카테고리의 다른 글
[BOJ/Java] 19942. 다이어트 (0) | 2024.04.23 |
---|---|
[BOJ/Java] 20055. 컨베이어 벨트 위의 로봇 (0) | 2024.04.23 |
[BOJ/Java] 17837. 새로운 게임 2 (1) | 2024.04.23 |
[BOJ/Java] 9251. LCS (최장 공통 부분 수열) (0) | 2024.04.23 |
[BOJ/Java] 1938. 통나무 옮기기 (0) | 2024.04.23 |
Comments