[프로그래머스] 짝지어 제거하기

1. 문제

---

2. 풀이 과정

---

• 단순하게 풀기
  1. 문자열을 한 문자씩 읽기
  2. 같은 문자가 연속으로 나오면 문자열에서 그 부분 제외시키기
  3. 문자열의 길이가 0이 될 때까지 혹은 문자열의 길이가 0이아닌데 문자열 길이의 변화가 없을 때 까지 반복
  4. 문자열의 길이가 0이면 결과는 1, 그렇지 않다면 0
• 스택으로 풀기
  1. 문자열을 한 문자씩 읽기
  2. 스택이 비어있거나 제일 위의 데이터와 다르면 해당 문자를 스택에 넣기
  3. 제일 위의 데이터와 같으면 스택 pop 하기
  4. 문자열을 돈 이후 스택이 비어있으면 1, 비어있지 않으면 0

3. 내 코드

---

단순하게 풀기

class Solution
{
    public int solution(String s)
    {
        int flag = 1;
        
        while(s.length() > 0) {
            int len = s.length();
            char c = s.charAt(0);
            for(int i = 1; i < s.length(); i++) {
                if(c == s.charAt(i)) {
                    s = s.substring(0, i - 1) + s.substring(i + 1); // 연속되는 부분 지우기
                    break;
                } else {
                    c = s.charAt(i);
                }
            }
            
            if(len == s.length()) { // 길이가 변하지 않았다면 더이상 연속되는 문자가 없다는 뜻
                flag = 0;
                break;
            }
        }
        
        return flag;
    }
}

시간복잡도

• O(N^2)

이 문제의 최대 입력 크기는 100만이다. 그렇기 때문에 O(N^2)으로 풀 수 없는 문제이다. 시간복잡도를 줄이기 위해선 스택을 활용해야 한다.

 

스택으로 풀기

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(stack.isEmpty() || stack.peek() != c) {
                stack.push(c);
            } else if(stack.peek() == c) {
                stack.pop();
            } 
        }
        if(stack.isEmpty()) {
            return 1;
        } else {
            return 0;
        }
        
    }
}

시간복잡도

• O(N)

스택을 활용했더니 O(N)으로 확 줄일 수 있었다.

4. 다른 정답 코드와 비교

---

[『코딩 테스트 합격자 되기 - 자바편』 해설 코드]

import java.util.Stack;

public class Solution {

    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // ❶ 스택이 비어 있지 않고, 현재 문자와 스택의 맨 위 문자가 같으면
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop(); // ❷ 스택의 맨 위 문자 제거
            }
            else {
                stack.push(c); // ❸ 스택에 현재 문자 추가
            }
        }

        return stack.isEmpty() ? 1 : 0; // ❹ 스택이 비어 있으면 1, 그렇지 않으면 0 반환
    }

}

시간복잡도

• O(N)

역시 스택을 사용해서 풀었다.

5. 피드백

---

• 연속된 데이터에서 특정부분을 제거할 때 스택으로도 문제를 해결할 수 있다.
• 포함시킬 데이터를 계속 넣다가 제거해야할 상황이 생기면 그 부분을 pop하고 다시 나머지를 push하면 된다.
• 스택을 활용하는 방안은 정말 무궁무진한 것 같다.