프로그래머스 Lv3 - 110 옮기기
110 옮기기
정의
0과 1로 이루어진 문자열에서 110을 뽑아서 임의의 위치에 다시 삽입하여 변형할 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 구해야 한다.
풀이
이 문제를 크게 2 부분으로 나눌 수 있다.
- 문자열에서 모든 110을 뽑아내는 과정
- 뽑아낸 110을 임의의 위치를 찾아 삽입하는 과정
첫 번째 과정인 문자열에서 모든 110을 뽑아내는 과정은 스택 자료구조를 활용해 뽑을 수 있다.
int count = 0;
Deque<Character> stack = new ArrayDeque<>();
for (char ch : str.toCharArray()) {
if (stack.size() >= 2 && ch == '0') {
char p = stack.pop();
char pp = stack.pop();
if (p == '1' && pp == '1') {
count++;
continue;
}
stack.push(pp);
stack.push(p);
}
stack.push(ch);
}스택에 삽입하려는 문자가 0인 경우 스택의 가장 위에 쌓인 2개를 뽑아 모두 1인지 확인해 1이 맞다면 이 문자는 110이 되기 때문에 삽입하려는 문자 0과 함께 스택에 다시 넣지 않는다. 이 과정을 거치면 110이 빠진 뒤 새로 만들어지는 110도 모두 제거할 수 있게 된다.
이 때, count를 1 증가시켜주는데 여기서 count 변수는 110의 총 개수이다.
이제 2번째 과정인 110이 모두 제거된 문자열에 뺀 만큼의 110의 위치를 찾아 삽입해야 한다. 여기서 110이 삽입될 위치는 한 곳만 찾으면 된다. 왜냐하면 110은 사전 순으로 봤을 때 110 뒤에 위치할 수 있는 111을 제외하고 가장 뒤에 위치하기 때문에 110을 개수만큼 이어붙여 한 곳에 삽입하면 되기 때문이다.
결론부터 말하자면 110이 삽입될 위치를 찾는 것은 110이 모두 제거된 문자열을 뒤에서 부터 검사했을 때 가장 처음 발견하는 0 뒤에 이어붙여 삽입하면 된다.
왜냐하면 110은 1로 시작하기 때문이다. 1은 0보다 사전 순으로 뒤에 위치하므로 사전 순으로 앞에 오는 문자열을 만들기 위해서는 최대한 많은 0을 110 앞에 위치시켜야 한다. 그러므로 110이 모두 제거된 문자열의 가장 마지막 0 뒤에 110을 이어붙여져야 한다.
110은 마지막 글자로 0을 포함하고 있기 때문에 1보다는 앞에 위치해야한다. 즉, 0보다는 뒤에 1보다는 앞에 위치시켜야 한다.
String insert = "110".repeat(count);
int insertAt = sb.length();
while (insertAt > 0 && sb.charAt(insertAt - 1) == '1') {
insertAt--;
}
sb.insert(insertAt, insert);추가한 테스트 케이스
| 파라미터 | 리턴 |
| ["0", "1", "00", "01", "10", "11"] | ["0", "1", "00", "01", "10", "11"] |
| ["0110", "1110", "01100", "01101", "11100", "11101"] | ["0110", "1101", "00110", "01101", "10110", "11011"] |
| ["11001010101"] | ["01010101101"] |
정답 코드
import java.util.*;
class Solution {
public String[] solution(String[] s) {
String[] answer = new String[s.length];
for (int i = 0; i < s.length; i++) {
answer[i] = transform(s[i]);
}
return answer;
}
private String transform(String str) {
int count = 0;
Deque<Character> stack = new ArrayDeque<>();
for (char ch : str.toCharArray()) {
if (stack.size() >= 2 && ch == '0') {
char p = stack.pop();
char pp = stack.pop();
if (p == '1' && pp == '1') {
count++;
continue;
}
stack.push(pp);
stack.push(p);
}
stack.push(ch);
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pollLast());
}
String insert = "110".repeat(count);
int insertAt = sb.length();
while (insertAt > 0 && sb.charAt(insertAt - 1) == '1') {
insertAt--;
}
sb.insert(insertAt, insert);
return sb.toString();
}
}