[프로그래머스 / JAVA] 짝지어 제거하기 (정답 코드)

자바 공부와 코딩테스트 준비를 병행할 겸 자바로 코테 준비를 며칠 전 시작했다.

막히거나 틀린 부분이 있더라도, 그냥 그대로 내가 스스로 작성한 부분들을 기록해 두려고 한다. 
그냥 미래의 복기용으로 나를 위해 적어둔 기록이다.
(이 사람은 어떻게 성공하거나 실패했는지 살펴보는 용도로도 적합할 것 같다.)

 

이 문제는 아이디어가 바로 떠오르지 않아, 접근법을 참고해서 코드를 작성했다.

처음에 내가 이 문제를 마주했을 때는, 인덱스 0부터 문자열의 끝까지 순회하면서 문자열을 자르고 붙이는 방식으로 해결해야 할 것 같다는 생각이 들었다.

그런데 제약 조건에서 나와있듯이, 문자열의 길이가 1,000,000 이하의 자연수로, 조금만 복잡하게 구현하면 바로 시간 초과가 떠버린다.

이 정도의 제약 조건이면, O(N)의 알고리즘을 이용해야 한다. 즉, 문자열을 순회하면서 한큐에 해결해버려야 하는 문제였다.

 

이 문제는 "현재 문자와 그다음에 나타날 문자"(인덱스 i와 i+1)의 시각으로 바라보면 해결 방법을 떠올리기 어렵다.

"현재 문자와 바로 이전에 나타난 문자"(인덱스 i와 i-1)의 시각으로 바라보면 편하다.

 

나(현재 문자) 바로 앞에 있는 문자가 나랑 같으면 짝이니까 지워주면 된다.

짝이 아직 안 지어진 앞쪽 문자열들은 어딘가에 저장해놔야 한다.

제일 최근에 집어넣은 문자가 제일 먼저 나오는 자료구조는 스택(Stack)이다.

나랑 스택의 맨 위의 문자가 같으면, 나는 없애버리고, 나랑 짝인 맨 위의 문자도 없애버려야 하니 스택을 한번 pop 시켜주면 된다.

 

전부 다 순회한 이후, 스택이 비어있으면 성공.

 

import java.util.ArrayDeque;

class Solution
{
    public int solution(String s)
    {
        char[] a = s.toCharArray();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        
        stack.push(a[0]); //맨 앞 문자는 그 앞에 짝이 없으므로 스택에 집어넣어놓기
        for (int i = 1; i < a.length; i++) { //맨 앞 다음 문자부터 맨 뒤 문자까지 순회
            if(stack.isEmpty()) { //스택이 비어있으면 이어질 짝이 없는거니까 스택에 push해 놓고 다음 문자로 넘어가기
                stack.push(a[i]);
                continue;
            }
            
            if(stack.peek() == a[i]) { //스택 맨위의 문자(현재 문자 바로 앞에 있는 문자)랑 같으면 짝지어주고 두개 없애버리기
                stack.pop();
            } else { //짝이 안맞으면 그냥 이 문자도 스택에 push하고 다음 문자로 넘어가기
                stack.push(a[i]);
            }
        }
        if (stack.isEmpty()) { //전부 다 돌았을 때 스택(문자열)이 비어있으면 성공
            return 1;
        } else { //아니면 실패
            return 0;
        }
    }
}

 

하루에 한문제 이상 꾸준히 풀자.

실수는 많이 할수록, 더 많이 배울 수 있다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스