[ 프로그래머스 / Programmers Level 3 ] 110 옮기기 ( 자바 / JAVA )

[ 프로그래머스 / Programmers Level 3 ] 110 옮기기 ( 자바 / JAVA )

https://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

s의 길이 ≤ 1,000,000 1 ≤ s의 각 원소 길이 ≤ 1,000,000

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

예제 입출력

입출력 예 #1

다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.

"1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.

다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.

"100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.

그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.

다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.

"0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.

그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.

풀이

stack에 110을 제외하고 PUSH

stack 내의 문자들을 Stringbuilder에 저장하면서 가장 마지막 0의 위치 찾기 ‼️

원래 문자에 110 이 존재하지 않았었다면, 원본 그대로 저장

존재했다면, 마지막 0 뒤에 '110'을 찾은 갯수 만큼 추가

코드

import java.util.Stack; public class PR_110옮기기 { public static 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 stack = new Stack<>(); int cnt = 0; for(int j = 0 ; j < str.length() ; j++){ char z = str.charAt(j); if(stack.size() > 1){ 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(); // 0의 마지막 위치 찾기 while(!stack.isEmpty()){ if(!flag){ if(stack.peek() == '1') idx--; else flag = true; } sb.insert(0, stack.pop()); } if(cnt > 0){ while(cnt-- > 0){ sb.insert(idx, "110"); idx += 3; } answer[i] = sb.toString(); } else // 110 이 없다는 의미이므로 그대로 answer[i] = s[i]; } return answer; } public static void main(String[] args) { String[] s = {"100111100"}; String[] answer = solution(s); } }

from http://hyeyun.tistory.com/63 by ccl(A) rewrite - 2021-10-19 19:27:27