프로그래머스 - 110 옮기기

leehyunjon·2022년 9월 13일

문자열 자료구조 프로그래머스

Algorithm

목록 보기

113/162

110 옮기기 : https://school.programmers.co.kr/learn/courses/30/lessons/77886

Problem

Solve

첫번째 풀이

"110"을 찾아서 해당 문자열을 하나 제거하고 1이상인 문자열이 있다면 해당 문자열 앞에 "110" 추가, 문자열 뒷부분에 0이 있다면 해당 문자열 뒤에 "110"추가 하는 식으로 구현했었다.
결과는 시간복잡도, 메모리부족 난리 났었다.

두번째 풀이

시간복잡도가 각 문자열에서 "110"을 제거하고 갱신하는것 까지 O(1)이나 O(log)로 해결해야했기 때문에 접근이 맞다고 생각하고 암만 생각해봤지만, 모르겠어서 다른분의 풀이를 봤다.

핵심은 각 문자열을 반복해서 "110"인 문자열을 찾고 위치를 찾아주는 것이 아니라, "110"문자열을 모두 찾고 뒤에 위치하고 있는 0에 "110"을 넣어주는 것이였다.

이렇게 되면 indexOf로 각 문자열에서 "110"을 반복적으로 탐색했는데, 이렇게 되면 해당 문자열에서 "110"개수만큼 반복되기 때문에 시간복잡도가 날수 있었다.

해결방법으로 Stack을 사용하면 각 문자열에서 한번의 탐색으로 "110"인 문자열을 모두 제거할 수 있고, "110"이 모두 제거된 문자열에서 뒤에 있는 0에 "110"문자열을 추가해주게된다면
문자열 배열 s에 대해서 총 O(n+m)의 시간복잡도가 되기때문에 시간초과를 막을 수 있게 된다.

세번째 풀이

두번째 풀이에서 각 문자열의 "110"을 제거한 문자열에서 마지막 0 뒤에 "110"을 추가해준다고 했는데, sb.insert(sb.lastIndexOf("0"),"110")으로 구현했더니 lastIndexOf연산으로 "110"의 개수만큼 뒤에서 부터 선형탐색이 되어 통과는 되지만 너무 오래걸렸다.

처음 "110"추가를 제외하고는 추가한 "110"뒤에 "110"문자열이 추가되는 것이기 때문에 초기 문자열에 lastIndex로 index를 초기화해주고 그 뒤부터는 index+=3으로 문자열을 추가할 위치를 갱신해주었더니 훨씬 빠르게 통과되었다.

Code

import java.util.Stack;
class Solution {
    public String[] solution(String[] s) {
        for(int i=0;i<s.length;i++){
			 s[i] = change(s[i]);
		}
		return s;
    }
    
    String change(String s){
        Stack<Character> stack = new Stack<>();

		//해당 문자열에서의 "110"개수
		int regexCount = 0;
        //한번의 탐색으로 "110"찾고 제거하기
		for (int i = 0; i < s.length(); i++) {
			if (stack.size() < 2)
				stack.push(s.charAt(i));
			else{
				if (s.charAt(i) == '0') {
					char midRegex = stack.pop();
					if (midRegex == '1' && stack.peek() == '1') {
						stack.pop();
						regexCount++;
					} else {
						stack.push(midRegex);
						stack.push(s.charAt(i));
					}
				}else{
					stack.push(s.charAt(i));
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		//stack에 있는 "110"문자열을 제외한 나머지 문자열 초기화
		while(!stack.isEmpty()){
			sb.append(stack.pop());
		}
		sb.reverse();

		//"110"개수만큼 맨 뒤의 0을 찾아 "110"문자열을 추가해준다.
        //"110"을 한번 추가해주었다면 다음 "110"추가 위치는 원래 위치의 +3이 된다.
		int lastIndex = sb.lastIndexOf("0");
		for(int i=0;i<regexCount;i++){
			sb.insert(lastIndex+1, "110");
            //0 위치 갱신
			lastIndex += 3;
		}

		return sb.toString();
    }
}