[프로그래머스 LV3] 110 옮기기 (Stack, 스택)

🧐 프로그래머스 LV3. 110 옮기기

문제 설명

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

입출력 예

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

 

💡 문제 풀이

방향성이 아예 떠오르지 않아서 구글링으로 찾아 풀어본 문제다.

1. 0을 최대한 왼쪽으로 보내고, 1을 최대한 오른쪽으로 보낸다.

2. Stack을 활용해서 알고리즘을 풀어낸다.

찾아보니 요 2가지가 핵심 요인이었다.

1번을 위해서는 110을 뺀 후의 숫자에서 가장 오른쪽에 있는 0 인덱스 바로 뒤에 빼낸 110을 이어 붙이고,

2번은 Stack을 활용해서 기존 문자열에서 110을 빼내면 된다.

좀 더 자세한 풀이는 아래 포스팅을 참고했다.

https://yabmoons.tistory.com/668

https://wellbell.tistory.com/228

 

먼저 Stack을 활용해서 "110"을 빼내보자.

Stack<Character> stack = new Stack<>();
int cnt = 0; // 빼낸 110 개수
        
for (int i = 0; i < str.length(); i++) {
	char z = str.charAt(i);
            
	if (stack.size() >= 2) { // 스택 크기가 2 이상이면 110 판별
		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);
	}
}

위 코드를 실행하면 기존 문자열에서 110을 빼고 남은 문자만이 Stack에 담겨있다.

 

이제 110을 문자열의 가장 오른쪽에 있는 0 뒤에 넣어주자.

int idx = stack.size();
boolean flag = false; // 0 발견 여부
StringBuilder sb = new StringBuilder(); // stack에서 문자 옮길 곳
        
while(!stack.isEmpty()) {
	if(!flag && stack.peek() == '1') { // 0이 발견되지 않았고, 1이면
		idx--;
	}
            
 	if(!flag && stack.peek() == '0') { // 0이 발견되지 않았고, 0이면
		flag = true;
	}
            
	sb.insert(0, stack.pop()); // 왼쪽에 삽입
}
            
if (cnt > 0) { // 110 개수만큼 붙여준다.
	while(cnt-- > 0) {
		sb.insert(idx, "110");
		idx += 3;
	}
}

 

위 풀이 방식을 전체 코드로 풀어내면 다음과 같다.

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] = solve(s[i]);
        }
        return answer;
    }
    
    private String solve(String str) {
        Stack<Character> stack = new Stack<>();
        int cnt = 0;
        
        for (int i = 0; i < str.length(); i++) {
            char z = str.charAt(i);
            
            if (stack.size() >= 2) {
                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;
        StringBuilder sb = new StringBuilder();
        
        while(!stack.isEmpty()) {
            if(!flag && stack.peek() == '1') {
                idx--;
            }
            
            if(!flag && stack.peek() == '0') {
                flag = true;
            }
            
            sb.insert(0, stack.pop()); // 왼쪽에 삽입
        }
            
        if (cnt > 0) {
            while(cnt-- > 0) {
                sb.insert(idx, "110");
                idx += 3;
            }
        }
            
        return sb.toString();
    }
}

 

✨ 포스팅을 마치며

풀이방법을 떠올리기 어려웠고, 구현 자체는 그렇게 어렵지 않은 문제였다. 항상 문자열 관련 문제를 풀면서 생각한 건데 문자열 문제가 나오면 일단 스택 활용을 생각하며 접근하면 좀 더 효율적으로 풀 수 있을 것 같다.