[프로그래머스(Programmers)][자바(java)] (Lv3) 110 옮기기 <월간 코드 챌린지 시즌2>

 

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

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

 

문제 요약

 

입력 받은 문자열 x에서 "110"을 적절한 위치로 옮겨 사전 순으로 가장 앞에 오는( 가장 작은 ) 문자열 return 

 

문제 풀이

 

import java.util.Stack;

public class Solution {

	public static String[] solution(String[] s) {
		int l = s.length, len, i, j, idx, c; boolean f; char x, y, z;
		String str;
		StringBuilder sb;
		Stack<Character> stack;
		for (i = 0; i < l; i++) {
			str = s[i];
			len = str.length();
			c = 0;
			stack = new Stack<>();
			for (j = 0; j < len; j++) {
				z = str.charAt(j);
				if (stack.size() >= 2 && z == '0') {
					y = stack.pop();
					x = stack.pop();
					if (x == '1' && y == '1' && z == '0') {
						c++;
						continue;
					} else {
						stack.push(x);
						stack.push(y);
						stack.push(z);
					}
				} else
					stack.push(z);
			}
			if (c > 0) {
				idx = stack.size();
				f = false;
				sb = new StringBuilder();
				while (!stack.isEmpty()) {
					if (!f && stack.peek() == '1')
						idx--;
					if (!f && stack.peek() == '0')
						f = true;
					sb.insert(0, stack.pop());
				}
				while (c-- > 0)
					sb.insert(idx, "110");
				s[i] = sb.toString();
			}
		}
		return s;
	}
}

 

*  스택, 그리디

-  입력받은 문자열 배열 String[] s 을 차례로 탐색  ( 0 <= i < s.length )

-  String str = s[i] 에서 "110"가 없을 때까지 반복적으로 찾고, 그 개수( int c )를 구함
    -  str에서 문자를 탐색하며 stack에 하나씩 넣음
    -  현재 문자가 '0'이고, 앞의 두 문자( stack.size() >= 2, stack.pop() )가 모두 '1'일 경우, "110" 이므로 빼줘야 함
    -  stack에서 pop()하고 c++ 해줌
    -  stack에는 "110"을 모두 뺀 문자열만 남아 있게 됨

-  "110"의 개수( c )가 1개 이상일 경우
    stack의 문자열들 사이에 "110"(들)을 끼워 넣을 적절한 위치( int idx )를 구함
    -  idx는 제일 끝 자리( stack.size() )로 초기화
    -  끝자리부터 stack.pop() 하며 0이 나오기 전 1이 나올 때마다 idx--
    -  StringBuilder sb 에 맨앞으로 append()

-  StringBuilder sb 에서 idx 위치에 "110"를 c개 만큼 넣음

-  s[i]에 sb.toString()한 값을 대입