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

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

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

 

문제 요약 

1. 입력받은 문자열에서 붙어있는 문자 중 같은 문자가 있을 경우 제거한다.

   ex) baab -> bb

2. 위 예제와 같이 제거 후 남는 문자열로 1번 작업을 다시 실행한다.

3. 위 예제와 같이 모두 제거되는 경우 1을 반환, 아닌 경우 0을 반환한다.

 

풀이 방법

1. 자료형을 뭘 쓸까 하다 처음 든 생각은 Stack을 2개 써서 옮겨담는다 였으나

   생각해보니 index계산하기가 귀찮아서 ArrayList로 우회했다.

2. ArrayList에 입력받은 문자열을 쪼개서 나눠 담는다.

3. 리스트가 빌때까지 while문을 반복하며 그 안에서 for문으로 인접해있는 동일 문자를 찾으면 제거 하도록 한다.

4. for문으로 탐색 시 동일 문자가 없어 제거된 문자가 없을 경우 더이상 진행이 불가능 하다고 판단하고 0을 반환한다.

5. 모두 제거가 되었다면 1을 반환한다.

 

효율화 테스트 통과 방법

풀이방법 2번에서

입력받은 문자열을 쪼개서 리스트에 담을 때 

리스트의 마지막 문자와 담으려는 문자가 일치 할 경우 담지 않고 마지막 문자를 제거하는 로직을 추가.

while문을 돌릴 대상을 만드는 과정에서부터 인접하며 동일한 문자들을 제거하기 때문에

반복문의 횟수가 줄어드는 것을 확인 할 수 있다.

 

import java.util.ArrayList;

class Solution
{
    public int solution(String s)
    {
        ArrayList<String> strArr = new ArrayList<>();
        int answer = 1;
        for(String temp : s.split("")){
            if(strArr.size()>0){
//                     리스트에 담기전에 동일한 문자가 겹치는 경우
//                     대상 문자도 리스트에 담지 않고, 이와 인접한 마지막 문자를 제거한다.
                if(!strArr.get(strArr.size()-1).equals(temp)){
                    strArr.add(temp);
                }else{
                    strArr.remove(strArr.size()-1);
                }
            }else{
                strArr.add(temp);
            }
        }

        while(!strArr.isEmpty()){
            boolean isDeleted = false;
            for(int i=0; i<strArr.size()-1; i++){
                if(strArr.get(i).equals(strArr.get(1+i))){
                    strArr.remove(i);
                    strArr.remove(i);
                    isDeleted = true;
                    break;
                }
            }
            if(!isDeleted){
                answer = 0;
                break;
            }
        }
        return answer;
    }
}