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

 

제출한 코드

 

1차 제출 코드 - 정확성 61.2 , 효율성 0 ( 시간초과 )

import java.io.*;
import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        if(s.length()%2 != 0){
            return 0;
        }

        List<Character> list = new ArrayList<>();
        for(int i = 0 ; i < s.length(); i ++){
            list.add(s.charAt(i));
        }        
        
        
        int idx = 0;
        while(!list.isEmpty()){
            
            if(list.get(idx) == list.get(idx+1)){
                list.remove(idx+1);
                list.remove(idx);
                idx = 0;
            }else{
                idx++;
                if(idx == list.size()-1){
                    break;
                }
            }
            
        }
        
        System.out.print(list.size());
        
        if(list.size() == 0){
            return 1;
        }else{
            return 0;
        }
    }
}

 

 

2차 제출한 코드 - 정확성 61.2 , 효율성 38.8

 

import java.io.*;
import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        
        // 홀수인 경우 반드시 실패
        if(s.length()%2 != 0){
            return 0;
        }
		
        // 비교를 위해서 Deque 2개 선언
        Deque<Character> left = new ArrayDeque<>();
        Deque<Character> right = new ArrayDeque<>();
                
        // right deque에 데이터 준비
        for(int i = 1 ; i < s.length(); i ++){
            right.add(s.charAt(i));
        }        
        
        // right이 빌 때 까지 진행
        while(!right.isEmpty()){
            
            // 왼쪽에 비교용 데이터가 없는 경우 right에서 1개 삽입
            if(left.isEmpty()){
                left.add(right.poll());
            }
            
            // 연속되는 알파벳인지 확인을 위한 값 준비
            char leftData = left.pollLast();
            char rightData = right.poll();
            
            // 연속 되는 경우 continue
            if(leftData == rightData){
                continue;
            }
            // 연속 되지 않는 경우 left에 둘다 추가
            else{
                left.add(leftData);
                left.add(rightData);
            }
        }
        
        // left가 비어있으면 성공
        if(left.isEmpty()){
            return 1;
        }else{
            return 0;
        }
    }
}

---

생각한 로직

 

1. 빠른 연산을 위해서 ArrayList, LinkedList가 아닌 Deque 사용

2. 2개가 연속되는지 확인을 위해 left, right를 구분하기 위해서 Deque를 2개 만든다.

3. right에 입력 값을 준비한다.

4. left의 마지막 값과 right의 맨 처음 값을 비교하면서 연속되는지 확인한다.

5. 연속 되지 않는 경우 left에 값을 전부 추가

6. left와 right둘다 empty인 경우 성공