루프에서 Stack 최적화: Clear() vs Recreate

❤️사건의 시작

BOJ를 풀면서..

오랜만에 Stack을 가볍게 풀어보고 싶어서 BOJ를 찾았다.

처음엔 이게 뭔 소린가 싶었는데 주어진 예제들을 통해 이것은 괄호 짝맞추기와 같다는 것을 알게 되었다.

같은 게 나오면 pop하고 스택이 비었거나 peek()과 다른 문자라면 push해주기를 반복하여 최종적으로 스택이 비어있으면 카운트해주었다.

💛사건의 전개

갑자기 궁금해지다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

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

        while (N-- > 0) {
            String str = br.readLine();
            stack.push(str.charAt(0));

            for (int i = 1; i < str.length(); i++) {
                char c = str.charAt(i);
                if(stack.isEmpty()) stack.push(c);
                else if (stack.peek() == c) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }

            if(stack.isEmpty()) cnt++;
            else stack.clear();
        }

        System.out.println(cnt);
    }
}

위와 같이 풀었고 통과처리 됐다.
사실 풀기 전에 Stack stack = new Stack<>(); 이 구절을
루프 전에 선언하고 마지막에 clear() 해줄지 vs 루프 안에 넣어 N만큼을 새로 생성해줄지 를 고민하다가, N번 만큼 recreate하는 것은 효율이 안 높을 것 같아 전자를 선택했다.

근데 또 후자의 경우가 좋을 수도 있을 것 같겠다(?)는 생각이 들어,
혹시 모르니까 후자도 돌려보기로 했다!

💚사건의 클라이막스

clear() vs recreate

1번: recreate
2번: clear()

시간에 큰 차이는 없는데 메모리는 꽤 차이가 있어 보인다.

🍏 효율성 비교: 메모리 효율성

1번은 N 번만큼의 new 객체를 생성하므로, 반복적으로 메모리 할당/해제를 하게 된다. -> 메모리 사용량을 증가시키고 자주 가비지 컬렉션을 발생시킬 수 있다.
2번은 기존에 할당된 스택 객체 메모리를 재사용하기 때문에, 반복적으로 메모리 할당/해제로 인한 오버헤드를 줄일 수 있다.

🍏 효율성 비교: 시간 효율성

1번은 객체 생성은 일반적으로 O(1)의 시간복잡도를 가진다. 그러나 이를 N만큼 반복하므로 시간비용이 누적된다.
2번은 clear()는 보통 O(n)의 시간복잡도를 가진다. 그러나 스택을 재사용하므로 반복 객체 생성보다 효율적일 수 있다.

💙사건의 끝

그래서 결론은?

루프 전에 스택을 생성하고 clear() 메서드로 비우는 방법인 2번이 더 효율적이다.
메모리 할당 오버헤드를 최소화하고, 동일한 스택 객체를 재사용함으로써 메모리/시간 효율성 부분에서 이점을 얻을 수 있다.

1. 반복적인 메모리 할당/해제 오버헤드 감소
2. 더 낮은 시간 복잡도

코드

package stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Q3986_boj {
    /**
     * 메모리: 19588 KB ( / 256000 KB)
     *  시간: 276 ms    ( / 1000 ms)
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine());
        int cnt = 0;

        while (N-- > 0) {
            String str = br.readLine();
            stack.push(str.charAt(0));
            for (int i = 1; i < str.length(); i++) {
                char c = str.charAt(i);
                if (stack.isEmpty() || stack.peek() != c) {
                    stack.push(c);
                } else {
                    stack.pop();
                }
            }

            if(stack.isEmpty()) cnt++;
            else stack.clear();
        }

        System.out.println(cnt);
    }
}

➕ 언어에 따라 다르다

특정 언어나 런타임 환경에 따라 성능 차이는 달라질 수 있음을 알아야 한다!
그러나, 일반적으로 재사용하고 비우는 것이 더 효율적인 접근 방식이다 ㅎㅎ

👍🏻느낀 점

하나의 문제도 여러 관점으로 바라보면 다양한 깨달음을 얻을 수 있다는 교훈을 피부로 느낀 하루였다.
앞으로도 이러한 생각으로 공부해야겠다!
스택문제도 풀고 효율성 공부도 하고 여러 가지 배울 수 있는 하루를 보낼 수 있게 된 것에 감사하다🙏🏻