프로그래머스 | LV.3 110 옮기기 - 문자열 구현 & Stack 활용 문풀 (Java)

⬛ 프로그래머스 | LV.3 110 옮기기 - 문자열 구현 & Stack 활용 문풀 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/77886

프로그래머스

문제 설명

---

💚문제 접근 방식

기존 String에 존재하는 “110”을 임의의 위치에 삽입해서 가장 사전 순 앞순으로 만들 수 있는 String을 만들어 반환하는 문제이다.

예시로 하나씩 해보면 0이 더 앞으로 갈수록 가장 사전 앞순인 것을 알 수 있다. 즉 마지막 0 뒤에 110을 삽입해야 한다.

마지막 0 위치에 insert 해야 가장 앞순

1차 시도

“110” 기준으로 split(”110”) 처리를 하고, 잘린 앞 부분에 존재하는 가장 마지막 0 뒤에 110을 삽입하면 된다고 생각했다.

1. 잘린 앞부분에 0이 존재 X → 가장 앞에 “110”을 담기
2. 잘린 앞부분에 0이 존재O → indexLastOf()로 가장 마지막 0의 다음 위치에 “110”을 담기
3. 바뀐 상태의 String 에 대해서 앞의 과정을 다시 반복하며 더 사전 앞순 String 탐색

→ 이런 식의 생각을 먼저 했지만 구현하는 과정이 생각보다 복잡했다..

앞뒤로 자른 문자열을 다시 활용해서 문자열을 형성해주고, 그걸 이전 String 값과 비교해서 더 앞순인지 비교하고, 그 과정을 정확하게 구현하는 데에 실패했다.

---

2차 시도

결국 찾아봤는데 Stack을 활용하는 코드를 보고 아차 싶었다…

스택 사용할 생각은 솔직히 전혀 못했고 계속 문자열을 잘라서 붙일 생각만 했다.

스택은 중간의 전반적인 순서를 유지한 채 가운데 숫자를 빼고 다시 담을 때 사용할 용도이다.

 

[구현 순서]

1) 스택을 활용하여 현재 String에 존재하는 ‘110’ 개수 찾고, (110) 제외한 문자만 스택으로 쌓는다.

 

2) 스택 내용물 존재하는 동안, 110을 삽입할 (마지막 0 위치) idx 위치를 찾으면서, sb에 스택에서 pop한 문자 역순으로 담는다. (110을 제외한 sb 만 담긴 거임)

 

3) 110 개수만큼 for문 돌면서 sb의 idx 위치에 110을 삽입하여 사전 앞순 문자열을 생성한다.

Stack 활용한 풀이 설명

💚 제출 코드

import java.util.*;

class Solution {
    //사전 앞순 처리 
    public String changeNumber(String numbers){
    	// 애초에 110도 찾을 수 없다면 원래 숫자를 반환
        if(!numbers.contains("110")) return numbers;
        
        Stack<Character> s = new Stack<>();
        // 문자열을 붙여야하기 때문에 StringBuilder 사용
        StringBuilder sb = new StringBuilder();
        int count = stackAndFind(s,numbers);//개수
        int idx = s.size(); 
        boolean flag = false;
        
        while(!s.isEmpty()){
            char cnt = s.pop();
            System.out.println(cnt);
            if(!flag){
                if(cnt == '0'){ 
                    flag = true;
                }
                else{ //1일 때는 계속 --
                    idx--;
                }
            }
            sb.append(cnt); //110 제외한 문자만 역순으로 담긴 상태
        }
        sb.reverse(); // 스택 역순 저장되기 때문에 뒤집어준 거임 

        //탈출 상황에서는 앞쪽의 마지막 0위치를 idx로 찾은 상태임 (거기에 삽입할 거라)
        
        for(int i = 0; i < count; i++){ //110 개수 만큼 idx 위치에 붙인다.
            sb.insert(idx,"110");
        }
        return sb.toString();
    }
    
    //스택 쌓고 110 개수 구하기
    public int stackAndFind(Stack<Character> s, String numbers){
        int count = 0; // 개수
        
         // 순차 탐색
        for(int i = 0; i < numbers.length(); i++){
            char third = numbers.charAt(i);
            
            // 스택에 들어있는게 2개 미만이라면 넣기만함
            if(s.size() < 2){
                s.push(third);
            }else{
            	// 스택에서 2개를 꺼냄
                char second = s.pop();
                char first = s.pop();
                
                 // 110 쌍인지 확인하여 맞으면 count+1
                if(first == '1' && second == '1' && third == '0'){
                    count++;
                }
                else{ //110 제외하고는 그대로 담음 
                    s.push(first);
                    s.push(second);
                    s.push(third);
                }
            }
        }
        return count;
    }
    
    //솔루션 함수 
    public String[] solution(String[] s) {
        String[] answer = new String[s.length];
        for(int i = 0; i < s.length; i++){
            String numbers = s[i];
            answer[i] = changeNumber(numbers);
            System.out.println();
        }
        return answer;
    }
}

💚 회고

스택을 활용할 때 스택의 구조를 최대한 활용해서 풀어야 하는데 그런 이해도가 부족한 듯 하다.

손으로 직접 그려보면서 구현 과정을 제대로 이해할 수 있었다.