프로그래머스 - 110 옮기기 문제 (자바)

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

코딩테스트 연습 - 110 옮기기

무슨 알고리즘을 사용해야하는 거지라는 생각과 고민 끝에 다른 사람으 코드를 보고 이해한 문제로

 

1. 문자에서 110이 나오는 경우 카운트를 세고 stack에는 담지 않는다.

2. stack에서 0이 나오기 직전 위치를 잡는다.

3. 0 직전 위치를 기준으로 110을 카운트한 개수 만큼 넣어준다.

 

ex)

0111111010

-> stack 1110, cnt = 2

-> idx = 1, sb = 0111

-> sb = 0110111 cnt = 1 idx = 4

-> sb = 0110110111 cnt = 0; idx = 7

import java.util.Stack;

// 프로그래머스 110 옮기기 문제
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;

            for(int j=0; j<str.length(); j++) {
                char z = str.charAt(j);

                if(stack.size()>=2) {
                    char y = stack.pop();
                    char x = stack.pop();

                    if(x=='1' && y=='1' && z=='0') {
                        cnt++;
                    } else {
                        stack.push(x);
                        stack.push(y);
                        stack.push(z);
                    }
                } else {
                    stack.push(z);
                }
            }

            int idx = stack.size();
            boolean flag = false;
            sb = new StringBuilder();
            while(!stack.isEmpty()) {
                if(!flag && stack.peek()=='1') {
                    idx--;
                }

                if(!flag && stack.peek()=='0') {
                    flag = true;
                }

                sb.insert(0, stack.pop());
            }

            if(cnt>0) {
                while(cnt>0) {
                    sb.insert(idx, "110");
                    idx += 3;
                    cnt--;
                }
                answer[i] = sb.toString();
            } else {
                answer[i] = s[i];
            }
        }
        return answer;
    }
}

 

Reference

https://velog.io/@pss407/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A477886-110-%EC%98%AE%EA%B8%B0%EA%B8%B0