[2017 팁스타운] 짝지어 제거하기

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

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

문제 설명

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

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

b aa baa → bb aa → aa →

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

제한사항

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

---

입출력 예

sresult

baabaa	1
cdcd	0

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

※ 공지 - 2020년 6월 8일 테스트케이스가 추가되었습니다.

 

 

#1. 2021.05.14
마지막 끝처리가 이상하다.
분명 마지막에 겹치는 문자까지 공백으로 변경했는데, 배열을 확인하면 문자열이 그대로 있다..

import java.util.Arrays;

class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        
        String[] sarray = s.split("");
        int previous = 0;
        
        for (int i=1; i<sarray.length; i++){
            
            System.out.println("pre : "+ previous+sarray[previous] + " / i : "+ i+sarray[i]);
            s="";
            for(int k=0; k<sarray.length;k++){
                s=s+sarray[k];
            }
            System.out.println(s);
            System.out.println(sarray[previous].equals(sarray[i]));
            
            if (sarray[previous].equals(sarray[i])){
                System.out.println("겹쳐요");
                sarray[previous]="";
                sarray[i]="";
                System.out.println("sarray[previous] : " + sarray[previous]);
                System.out.println("sarray[i] : " + sarray[i]);
                
                if(i==sarray.length-1){
                    System.out.println("끝끝");
                    break;
                }
                
                int check=0; //pre변경되었는지확인
                
                for(int t=i; t>=0; t--){
                    System.out.println(t + " - pre변경중"+!sarray[t].equals("0"));
                    
                    if(!sarray[t].equals("")){
                        previous = t;
                        System.out.println(t + " - pre변경완료"+sarray[previous]);
                        check=1;
                        break;
                    }
                }
                if(check==0){
                    System.out.println("변경실패");
                    if(i<sarray.length)
                    {
                        i++;
                        previous = i;
                        
                        System.out.println(sarray.length);
                        System.out.println(i + "최종변경");
                    }
                }
            }
            else{
                previous = i;
            }
        }
        

        //최종


        
        for(int k=0; k<sarray.length;k++){
                s=s+sarray[k];
        }
        System.out.println(s);
        if(s == "")
            answer = 1;
        return answer;
    }
}

 

#2. 2021.05.15 
문제는 s에 이미 문자열이 입력되어 있는 상태라는 것이었다.
최종 수정한 코드는 정확성은 맞지만 효율성이 많이 떨어진다.
다음에 효율성을 높일 수 있도록 다시 수정해봐야겠다.

 

import java.util.Arrays;

class Solution
{
    public int solution(String s)
    {
        int answer = 0; //최종반환값 (문자열을 모두 제거할 수 있으므로 1을 반환)
        String result = ""; //최종문자열
        
        String[] sarray = s.split(""); //입력받은 문자열을 문자열배열로 변환
        
        int previous = 0; //비교할 이전 문자열 인덱스값
        
        for (int i=1; i<sarray.length; i++){
            if (sarray[previous].equals(sarray[i])){
                sarray[previous]="";
                sarray[i]="";
                
                int check=0; //pre변경되었는지확인
                
                for(int t=i; t>=0; t--){
                    if(!sarray[t].equals("")){
                        previous = t;
                        check=1;
                        break;
                    }
                }
                if(check==0){
                    if(i<sarray.length)
                    {
                        i++;
                        previous = i;
                    }
                }
            }
            else{
                previous = i;
            }
        }
        

        //최종
        for(int k=0; k<sarray.length;k++){
                result=result+sarray[k];
        }
        if(result.equals(""))
            answer = 1;
        return answer;
    }
}