[Algorithm] 프로그래머스 - 110 옮기기 자바

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래멋 110 옮기기 자바 풀이를 작성하고자 합니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/77886

프로그래머스

 

해당 문제는 풀지 못하여 블로그를 참고하여 코드를 작성하였고 이에 대한 방법을 주석화하여 정리하였습니다.

 

 

 

1. 풀이 소스 

import java.util.*;

class Solution {
    public String[] solution(String[] s) {
        String[] answer = new String[s.length]; // 정답 배열 설정
        StringBuilder sb; 
        
        for (int i = 0; i < s.length; i++) {
            String str = s[i]; 
            Stack<Character> stack = new Stack<>(); 
            
            int cnt = 0; // 연속된 캐릭터 타입의 값이 110인 것의 개수 
            
            for (int j = 0; j < str.length(); j++) {
                char z = str.charAt(j); // 스택이 2 이상 && z가 0이라면 스택에서 두개를 빼서  110 비교
                
                if(z == '0' && stack.size() >= 2) {
                    char y = stack.pop(); 
                    char x = stack.pop();  
                    
                    if (x == '1' && y == '1' && z == '0') {
                        cnt++; 
                    } else {
                        stack.push(x);  // 110이 아니라면 다시 후입 선출을 위해 x y z 순으로 스택에 넣기
                        stack.push(y);
                        stack.push(z);
                    }
                } else {
                    stack.push(z); // 스택 사이즈가 2보다 작다면 z가 1이더라도 스택에서 빼서 110을 만들 수 없으므로
                }     
            }
            
            int idx = stack.size(); // idx는 stack 사이즈 (연속 수가 110이 아닌 경우 스택에 다 넣음)
            
            sb = new StringBuilder();
            
            // 참조1
            boolean flag = false; // 맨 처음 0이 위치하는 지점 전까지 idx를 감소하기 위함 하단에 예시
            
            while(!stack.isEmpty()) {
                if (!flag && stack.peek() == '1') idx--;
                
                if (!flag && stack.peek() == '0') flag = true;  // 스택에서 뺀 값이 0이라면 0 자리에 위치
                
                sb.insert(0, stack.pop()); // sb에 정순으로 입력함으로써 원래 문자열에서 110만 뺀 상태
            }
            
            if (cnt > 0) { // 110 개수가 양수라면
                while (cnt > 0) {
                    sb.insert(idx, "110"); // 스택에서 뺄 때 (역순이므로 나중에 나오는 값이 앞쪽) 0이 나오는 다음의 인덱스
                    idx += 3; // 3개를 추가했으므로 +3
                    cnt --; // cnt--
                }
                answer[i] = sb.toString();
            } else {
                answer[i] = s[i]; // 만약 추가할 110이 없다면 문자열 그대로 리턴
            }
        }
        return answer;
    }

}

 

 

2. 풀이 중점 사항

 

해당 문제의 중요한 포인트는 stack을 활용하여 문자열 탐색을 합니다. 110이 나온다면 카운트를 증가시키고 그 외의 문자열은 모두 스택에 넣습니다. 사전순 정렬을 이용한다면 110은 10, 0보다 앞서 있을 수 없습니다. 

즉 0이 나오는 시점 마지막 시점의 바로 뒤에 위치한다면 00000101000 110 11111 사전순 정렬에서 앞에 만들 수 있습니다.

 

이를 구현하기 위한 자료는 참고#1입니다.

 

가령 문자열이 다음과 같이 있습니다.

문자열: 11010111 

먼저 문자열을 탐색하여 110이 있다면 카운트를 증가시키고 연속된 숫자로 110이 아니라면 모두 스택에 넣습니다.

cnt = 1

stack : 10111        (후입 선출로 인덱스 4가 이 먼저 출력)

idx = 5 (stack size)

boolean flag = false // 해당 flag는 문자열에서 가장 마지막의 0, 스텍 기준으로는 가장 빠른 0이 나오면 true로 바꿈

sb.insert(0, stack.pop()) 스텍에서 나온 문자열을 정순으로 배치하기 위해 놓습니다.

 

시뮬레이션을 해보면 

sb = 111

stack : 10

flag = false

idx = 2

cnt = 1

 

sb = 0111

stack = 1 

flag = true

idx = 2

cnt = 1

 

sb = 10111

stack : x

flag = true

idx = 2

cnt = 1

 

cnt > 0 이므로 idx의 위치인 10111 의 10 <1> 11에 110을 추가합니다.

10110111 이렇게 설정하게 되면 문자열 기준으로 사전 순 정렬에서 더 빠른 정렬을 만들 수 있습니다.

만약 101이더라도 101101을 만들어야 하는데, 그 이유는 110을 사전순 정렬을 위해 잠시 빼놓았을 뿐 반드시 써야 하기 때문에

1이 하나더라도 1101로 만들면 이전 최초 문자열보다 더 빠른 문자열을 만들 수 있습니다.

 

최초 11010111 

변경 10110111

 

나머지 자세한 사항은 주석화 하였습니다.

이상으로 문제 풀이를 마치도록 하겠습니다. 감사합니다.!

 

참고 출처: https://wellbell.tistory.com/228