[1Day 1Algo] 백준 3986번 좋은 단어 (JAVA)

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

3986번: 좋은 단어

 



처음 봤을 때는 문자열 조작 문제로 생각했다.

그래서 일단 문제에서 원하는 패턴을 여러가지 생각해보았다.

 

가장 간단한 패턴으로 AABB / BBAA와 ABBA / BAAB 를 생각했다.

이 둘의 조합을 사용하여 ABAABA / BABAABABAA 와 같은 패턴을 만들어낼 수 있었다.

 

패턴을 가만히 살펴보니, 자료구조에서 배웠던 postfix, infix expression이 떠올랐다.

이는 stack을 이용해서 구현할 수 있었다.

 

그래서 2개의 stack을 이용해서 문제를 풀었다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            Stack<Character> stack = new Stack<>();
            Stack<Character> pairStack = new Stack<>();
            
            for (byte val : br.readLine().getBytes()) {
                stack.push((char) val);
            }
            
            for (int j = stack.size(); j > 0; j--) {
                if ((!pairStack.empty()) && (pairStack.peek() == stack.peek())) {
                    pairStack.pop();
                    stack.pop();
                } else {
                    pairStack.push(stack.pop());
                }
            }
            
            if (pairStack.empty()) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

 

 

그런데 다른 제출자들의 Java 실행시간을 보니, 300ms대가 아닌 200ms대가 나오는 경우도 있었다.

🤔🤔🤔🤔

Scanenr를 사용하지 않았기 때문에 IO의 문제가 아닌, 알고리즘 구조의 문제라고 판단했다.

 

내 코드를 천천히 다시 살펴보니 stack을 2개나 사용할 필요가 없다는 걸 깨달았다.

pairStack을 사용하는 대신, getBytes로 char을 하나씩 가져올 때, 비교를 해도 되기 때문이었다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 0;

        for (int i = 0; i < n; i++) {
            Stack<Character> stack = new Stack<>();

            for (byte val : br.readLine().getBytes()) {
                Character ch = (char) val;
                if ((!stack.empty()) && (stack.peek() == ch)) {
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
            if (stack.empty()) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}