[백준] 문제 27497번 - 알파벳 블록 - JAVA

[링크] https://www.acmicpc.net/problem/27497

---

💎 문제 분석 & 제약 조건

문제 분석 :

알파벳 블록을 조립해서, 버튼을 누른 횟수와 누른 버튼이 순서대로 주어질 때 완성된 문자열 출력하기

제약 조건 :

첫째줄에 버튼을 누른 횟수 N이 주어진다( 1<= N <=1000000)

둘째줄에 N개의 줄에 

• 1 c : 문자열 맨 뒤에 c가 적힌 블록 추가
• 2 c : 문자열 맨 앞에 c가 적힌 블록 추가
• 3 : 문자열을 구성하는 블록 중 가장 나중에 추가된 블록 제거

c는 알파벳 대문자 또는 소문자로 주어진다.

---

 

🚀 의사 결정

1. BufferedReader 로 문자열 입력 받기

2. 입력 받은 문자열을 누른 횟수에 따라 바꾸는 메서드 실행

Deque만 사용하거나 ArrayList를 사용하는 방식도 문제를 해결할 수 있지만, 각 자료구조의 특징에 따라 성능 차이 발생. 예를 들어, ArrayList에서 앞에 요소를 삽입하거나 삭제하는 것은 상대적으로 비효율적이므로 ,

Deque를 사용하는 방식이 연산을 양쪽 끝에서 자유롭게 처리할 수 있어 가장 적합하고 , 어떤 방향에서 블록을 제거할지 결정하는 과정에서 Deque만으로는 해결할 수 없는 부분을 Stack을 사용해서 보완

 => 연산 1 또는 2가 호출될 때, stack.push(true) 또는 stack.push(false)를 통해 어떤 방향(앞/뒤)으로 블록이 추가되었는지 추적

 => 연산 3이 호출될 때, stack.pop()을 통해 가장 마지막에 어떤 방향으로 블록이 추가되었는지 확인하고, 해당 방향에서 블록을 제거

Deque는 블록의 삽입과 삭제를 처리하고, Stack은 연산의 순서를 추적하여 제거할 블록의 방향을 결정

3. 완성된 문자열 출력

문자열을 효율적으로 처리하기 위해서 StringBuilder 사용, 문자열을 수정할 때마다 새로운 문자열 객체를 생성하는 것을 방지하여 메모리 사용을 최적화

BufferedWriter를 통한 출력 

BufferedWriter는 버퍼링된 방식으로 데이터를 출력하여, 여러 번의 출력 연산을 모아서 한 번에 출력하는 방식, 성능향상

---

📜 소스코드(Java)

풀이 )

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 버튼을 누른 횟수
        int N = Integer.parseInt(br.readLine());

        // deque 와 stack 이용
        Deque<Character> deque = new ArrayDeque<>();
        Stack<Boolean> stack = new Stack<>();

        // 연산 처리 메서드 호출
        for (int i = 0; i < N; i++) {
            String input = br.readLine(); // 입력받은 값
            buttonPush(deque, stack, input); // 버튼 누른 연산 처리
        }

        // 결과 출력 메서드 호출
        printResult(deque, bw);

        // 버퍼를 통해 출력한 내용을 실제로 flush
        bw.flush();
    }

    // 버튼을 누를 때마다 연산을 처리하는 메서드
    private static void buttonPush(Deque<Character> deque, Stack<Boolean> stack, String input) {
        char op = input.charAt(0);

		// 연산이 1 c (맨 뒤에 블록 추가)라면 stack.push(true)로 뒤에서 추가된 것을 기록
        if (op == '1') {
            deque.offerLast(input.charAt(2));
            stack.push(true);
            
	    // 연산이 2 c (맨 앞에 블록 추가)라면 stack.push(false)로 앞에서 추가된 것을 기록
        } else if (op == '2') {
            deque.offerFirst(input.charAt(2));
            stack.push(false);

	    // 연산이 3 (가장 최근에 추가된 블록 제거)이라면 stack.pop()을 통해
        // 마지막에 어떤 방향으로 추가된 블록을 확인하고, 그에 맞는 방향에서 블록을 제거
        } else if (!deque.isEmpty()) {
            if (stack.pop()) {
                deque.removeLast();
            } else {
                deque.removeFirst();
            }
        }
    }

    // 완성된 문자열을 출력하는 메서드
    private static void printResult(Deque<Character> deque, BufferedWriter bw) throws IOException {
        StringBuilder sb = new StringBuilder();

        for (char c : deque) {
            sb.append(c);
        }

        // 문자열이 비어 있으면 "0"을 출력, 아니면 완성된 문자열을 출력
        bw.write(sb.length() > 0 ? sb.toString() : "0");
    }
}