[코딩테스트합격자되기-자바편] 문제11. 짝지어 제거하기

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

 

출처 : 프로그래머스 - 짝지어 제거하기

 

내용

 

알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 짝을 찾은 다음에는 그 둘을 제거한 뒤 앞뒤 문자열을 이어 붙입니다.

이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성하세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 반환해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제약 조건

 

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

 

 

어떤 알고리즘을 적용하려 했나요?

 

스택을 사용한다.

 

 

적용 근거는 무엇인가요?

 

문자열 길이가 1,000,000이하의 자연수이어서 시간 복잡도가 O(N^2)이 되면 안될 것 같다.
replace()를 사용하거나 이중 반복문을 사용할 경우 시간초과가 일어날 가능성이 있다.

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
16:42	16:53	11분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

 

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

s	result
baabaa	1
cdcd	0

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution() {
    // 1. stack 생성
    // for문
    for (s) {
        // stack 이 비어있으면 삽입 후 continue
        // stack 이 안 비어있으면 꺼낸 뒤 같은지 비교
        // 안 같으면 stack에 삽입
    }
    return stack 비어있으면 1 비어있지 않으면 0
}

 

 

구현

import java.util.Stack;

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

        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(s.charAt(i));
                continue;
            }
            char prev = stack.peek();
            if (prev == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

 

 

 

복기하기

 

저자 권장 시간	권장 시간 복잡도
30분	O(N)

 

답안과 나의 풀이를 비교해보세요

import java.util.Stack;

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

        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        return stack.isEmpty() ? 1 : 0;
    }
}

• 코드 한 번 더 다듬을 걸. 아쉽다.

 

 

요약하기

• 문제를 보고 스택인지 떠올리려면 많이 풀어보는 수밖에..