[프로그래머스] (Lv.2) 짝지어 제거하기 **

문제

 

---

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

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

b aa baa → bb aa → aa →

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

 

제한사항

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

-  출력 예시  -

정답 코드

---

<  내 정답 코드  >        ★    오답    ★

class Solution {
    public int solution(String s) {
        String[] strArr = s.split("");
        List<String> list = new ArrayList<>(Arrays.asList(strArr));

        int i = 1;

        while (true) {
            if (i == list.size() || list.size() == 0) {
                break;
            }

            char preChar = list.get(i - 1).charAt(0);
            char nextChar = list.get(i).charAt(0);
            if (preChar == nextChar) {
                list.remove(i - 1);
                list.remove(i - 1);
                i = 1;
                continue;
            }
            i++;
        }

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

 

<  내 정답 코드  2  >        ★    오답    ★

class Solution {
    public int solution(String s) {
        Stack<String> stack = new Stack<>();
        stack.push(String.valueOf(s.charAt(0)));

        for (int i = 1; i < s.length(); i++) {
            String str = String.valueOf(s.charAt((i)));

            try {
                if (stack.peek().equals(str)) {
                    stack.pop();
                } else {
                    stack.push(str);
                }
            } catch (Exception e) {
                stack.push(String.valueOf(s.charAt(i)));
            }
        }

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

 

<  내 정답 코드  3  >

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

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

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

이것을 주의하자!

---

-  첫 번째 시도!!   문제를 풀기 전 어떤 자료구조를 사용하면 좋을지 생각한다. 기본적으로 '문자열',  'Array',  'List',  'Set',  'Map' 이 정도로 고민하는데, 이번에는 삭제가 가능한 List 를 이용하기로 했다. 그래서 문자열에서 바로 ArrayList 로 만들었고, 앞 문자와 뒤 문자가 동일하면 remove( ) 메서드를 이용해서 삭제했다. 코드가 동작을 해서 정확성 테스트는 모두 통과했지만, 효율성 테스트에선 모두 실패했다. '시간 초과' 가 나왔다. 즉 구현은 되지만, 시간복잡도가 높아서 효율이 좋지 못하다는 것이다. 첫 번째 실패...!

 

-  두 번째 시도!!   고려했던 자료구조 중에서 놓치고 있던 것이 있었다. 바로 'Stack' 이다. 생각해보니 Stack 에 원소를 하나씩 넣은 후 동일한 문자가 들어오면 pop( ) 해주면 끝이었다. 너무 간단했다. Stack 에는 객체만 들어올 수 있어서 char 형 변수를 넣지 못한다는 판단하에 String 형으로 Stack 을 만들었다. 그리고 peek( ) 메서드를 사용했을 때 Stack 이 비어있으면 ' EmptyStackException ' 이 발생하기 때문에 맨 처음 원소는 미리 넣어주고, 예외 발생하면 catch 문에서 다음 첫 번째 원소를 넣기로 했다. 정확성 테스트는 모두 통과했는데, 효율성 테스트에서 단 한 개가 실패했다. 두 번째 실패...!

 

-  세 번째 시도!!   Stack 에는 객체만 들어올 수 있다고 생각해서 char 형을 버렸었는데, Wrapper 클래스의 'Character' 이 있다. 그래서 Stack<Character> 로 만들면 char 형 변수가 오토박싱으로 들어가게 된다. 또한 try - catch 문으로 예외처리를 하지 않아도, if 문에서 "해당 Stack 이 비어있지 않다면..." 라는 조건을 달면 EmptyStackException에 걸리지 않는다. 더 간단하게 구현하니 모든 테스트에 통과했다.

 

-  이번 연습의 포인트는,

 

      (1)   Stack  자료 구조를 항상 염두하기

      (2)   스택이 비어있는 상태에서 peek( ) 메서드를 사용하면 EmptyStackException 이 발생함

      (3)   Character 클래스를 이용해 Stack 을 만들면, char 형을 저장할 수 있음

      (4)   try - catch 문을 쓰지 않아도 if 문을 통해 예외가 발생 안되도록 할 수 있음