문제 링크
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
알고리즘: 자료구조, Stack
풀이
문자열을 사전 순으로 가장 앞에 오게끔 만들어줘야 한다. 그렇게 하기 위해서 0을 최대한 앞으로 보내주는 게 우리의 목표이다.
문자열의 길이는 1,000,000이기 때문에 O(n) 풀이로 풀어줘야 통과할 수 있다.
O(n) 풀이는 Stack을 이용한 풀이다.
먼저 문자열을 순차 탐색한다.
1이면 무조건 Stack에 넣는다.
여기서 0일 때가 중요하다.
0이 나왔을 때 만약 Stack에 size가 0이면 sb_fix에 append해준다.
(sb_fix는 더 이상 변하지 않는 문자열이다.)
0이 나왔을 때 만약 Stack에 size가 1이면 stack.pop() 해주고 "10"을 sb_fix에 append해준다.
0이 나왔을 때 만약 Stack에 size가 >= 2이면 stack.pop() 두 번 해 주고 "110"을 sb_110에 넣어준다. 여기서 "110"을 왜 sb_fix에 넣지 않냐면 "110"은 계속 움직이는 문자열이기 때문에 "110"보다 사전 순으로 앞선 '0', "10"이 먼저 앞에 자리를 잡고 붙어줘야 한다.
이렇게 순차 탐색이 끝나면 Stack에 남은 1을 sb_110 뒤에 붙여주고, sb_fix와 sb_110을 붙여주면 해당 문자열이 사전 순으로 가장 앞선 문자열이 된다.
소스 코드
import java.util.*;
import java.io.*;
class Solution {
static StringBuilder sb_fix = new StringBuilder();
static StringBuilder sb_110 = new StringBuilder();
static Stack<Character> stack = new Stack<>();
public String[] solution(String[] s) {
String[] answer = new String[s.length];
for(int i=0; i<s.length; i++) {
String str = s[i];
for(int j=0; j<str.length(); j++) {
if(str.charAt(j) == '1') stack.push('1');
else if(str.charAt(j) == '0') {
if(stack.size() == 0) sb_fix.append('0');
else if(stack.size() == 1) {
stack.pop();
sb_fix.append("10");
} else {
//stack에 요소 1의 개수가 2보다 클 때
stack.pop();
stack.pop();
sb_110.append("110");
}
}
}
while(stack.size() != 0) sb_110.append(stack.pop());
answer[i] = sb_fix.toString() + sb_110.toString();
sb_fix = new StringBuilder();
sb_110 = new StringBuilder();
}
return answer;
}
}