(Python, Java) 프로그래머스 - 짝지어 제거하기

09 Jan 2022 in Algorithm on Programmers, Level2

[문제 링크]

Python 풀이

from collections import deque

def solution(s):
    answer = 1

    q = deque()
    for word in s:
        if not q:
            q.append(word)
        else:
            if q[-1] != word:
                q.append(word)
            else:
                q.pop()

    if q:
        answer = 0

    return answer

주어진 수 최대가 100만이다.
이는 단순한 규칙 노가다로는 해결되지 않는 복잡도이다.
이런 문제는 대부분이 자료구조를 사용해야하거나 특별하게 범위를 줄일 수 있느 규칙이 필요하다.

Java 풀이

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (stack.isEmpty() || stack.peek() != ch) {
                stack.push(ch);
            } else if (stack.peek() == ch) {
                stack.pop();
            }
        }

        if (stack.isEmpty())
            return 1;
        return 0;
    }
}

레벨3 풀다가 자바 연습하려고 레벨2 푸니까 너무 어렵게만 생각하는 것 같다. 항상 문제를 풀 때 어떤 자료구조를 사용해야할 지 먼저 생각하도록 하자.