프로그래머스 2017:팁스다운 [짝지어 제거하기] Java 문제 풀이

https://programmers.co.kr/learn/courses/30/lessons/12973?language=java 

코딩테스트 연습 - 짝지어 제거하기

import java.util.Stack;


class Solution
{
    public int solution(String s)
    {
        
     Stack<Character> stack = new Stack<>();
        
        for(char c : s.toCharArray()){
            if( ! stack.isEmpty() && stack.peek() == c ) stack.pop();
            else stack.push(c);
        }
        
        return stack.isEmpty() ? 1 : 0;
    }
}

 

문제 요약

1. 같은 문자가 연이어 나온다면 제거할 수 있습니다.
2. 계속 반복해서 문자열을 없앤다면 1을 리턴합니다.

 

예시

• s 가 "baabaa"라면 가운데 "aa"를 없앱니다.
•  "bbaa"에서 "bb"를 없앱니다.
• "aa" 마지막으로 "aa"를 없애면 문자열의 길이는 0입니다. 
• 1을 리턴합니다.

 

로직

1. Stack<Character> 를 만듭니다.
2. 문자열을 순회합니다.
3. 스택이 비어있다면 push(Element e) 메소드를 사용해서 문자열을 스택에 넣습니다.
4. 스택이 비어있지않다면 다음 문자열이 스택에 있는 문자열과 같은지 체크합니다.
5. 같다면 현재의 문자열은 stack에 넣지 않고, 전 문자열은 pop() 메소드를 사용해서 빼냅니다.

 

문자열의 순회가 끝났을때 스택이 비어있다면 1을 리턴, 반대라면 0을 리턴합니다.

 

 

다른 개발자 분의 풀이

import java.util.Stack;

class Solution
{
    public int solution(String s)
    {

        byte[] bytes = s.getBytes();
        int length = bytes.length;

        Stack<Integer> stack = new Stack<>();

        int iLeft = 0, iRight = iLeft + 1;
        for (; iLeft < length && iRight < length; ) {
            if (bytes[iLeft] == bytes[iRight]) {
                // bytes[iLeft] = 0;
                // bytes[iRight] = 0;

                if (stack.empty()) {
                    /*
                    while (iLeft >= 0 && bytes[iLeft] == 0) iLeft--;
                    while (iRight < length && bytes[iRight] == 0) iRight++;

                    if (iLeft < 0) iLeft = iRight;
                    if (iRight <= iLeft) iRight = iLeft + 1;
                    */

                    iLeft = iRight + 1;
                    iRight = iLeft + 1;
                } else {
                    iLeft = stack.pop();
                    iRight++;
                }
            } else {
                stack.push(iLeft);

                iLeft = iRight;
                iRight = iLeft + 1;
            }
        }

        return iLeft >= length && iRight >= length ? 1 : 0;
    }
}

 

1바이트 문자열에 쓸 수 있는 신박한 풀이네요.  

 

한 수 배웠습니다.