<프로그래머스> 110 옮기기

<링크>

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

프로그래머스

 

 

 

<문제>

• 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.
  • x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.
• 예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.
• 변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

<제한사항>

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

 

<입력 및 출력>

 

 

 

<아이디어>

1. 110이 뜨면 가져와 가져와.
2. 110이 있는 만큼 반복해서 넣어줘야하니까..  카운트 변수 하나 만들기.
3. 110을 빼내면 3개 만큼 길이가 늘어나니까 stringBuilder()에 붙여주기.

 

<풀이 - Java >

import java.util.Stack;

class Solution {
	public String[] solution(String[] s) {
		String[] answer = new String[s.length];

		for (int i = 0; i < s.length; i++) {
			Stack<Character> stack = new Stack<>();
			int count = 0;

			// "110"을 모두 제거하면서 카운트
			for (int j = 0; j < s[i].length(); j++) {
				char a = s[i].charAt(j);

				if (stack.size() > 1) {
					char b = stack.pop();
					char c = stack.pop();

					if (a == '0' && b == '1' && c == '1') {
						count++;
					} else {
						stack.push(c);
						stack.push(b);
						stack.push(a);
					}
				} else {
					stack.push(a);
				}
			}

			// 111이 끝나는 곳을 탐색. 이곳에 붙이면 되니까.
			StringBuilder sb = new StringBuilder();
			int insert = stack.size();
			boolean flag = false;

			while (!stack.isEmpty()) {
				if (!flag) {
					if (stack.peek() == '1') {
						insert--;
					} else {
						flag = true;
					}
				}
				sb.insert(0, stack.pop());
			}
			while (count-- > 0) {
				sb.insert(insert, "110");
				insert += 3;
			}
			answer[i] = sb.toString();
		}

		return answer;
	}
}