JAVA 프로그래머스 Lv.3 110 옮기기

 

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

 

---

문제

1.  변환할 문자열이 담긴 배열 s가 입력으로 들어옴. 문자열 배열 s의 길이( 1 <= s.length <= 1000000, 1 <= s[i].length() <= 1000000 )
2. 1과 0으로 이루어진 문자열 x에서 "110" 이라는 문자열을 뽑아 임의의 위치에 다시 삽입하여 x을 사전 순으로 앞에 오도록 만든다.
3. 문자열 배열 s의 모든 문자열을 사전 순에서 가장 앞에 오도록 만들어 return한다.

---

 

초기 코드

import java.util.*;

class Solution {
    public static String stackToString(Stack<Character> result) {
    String s = "";
    while (!result.isEmpty()) {
      s = s.concat(result.pop().toString());
    }
    return s;
  }
    
    public String[] solution(String[] s) {
        Stack<Character> stack = new Stack<>();
    Stack<Character> result = new Stack<>();

    for (int i = 0; i < s.length; i++) {
      int count = 0;
      String temp = s[i];

      for (int j = 0; j < temp.length(); j++) {
        if (stack.size() > 1 && temp.charAt(j) == '0') {
          if (stack.peek() == '1') {
            stack.pop();
            if (stack.peek() == '1') {
              stack.pop();
              count++;
            } else {
              stack.push('1');
              stack.push('0');
            }
          } else {
            stack.push('0');
          }
        } else {
          stack.push(temp.charAt(j));
        }
      }

      while (!stack.isEmpty()) {
        if (stack.peek() == '1') {
          result.push(stack.pop());
        } else {
          for (int j = 0; j < count; j++) {
            result.push('0');
            result.push('1');
            result.push('1');
          }
          count = 0;
          result.push(stack.pop());
        }
      }
      if (count != 0) {
        for (int j = 0; j < count; j++) {
          result.push('0');
          result.push('1');
          result.push('1');
        }
      }
      s[i] = stackToString(result);

      stack.clear();
      result.clear();
    }
        
    return s;
    }
}

원래 문자열을 이용해서 문제를 풀어볼 생각이었는데

문자열을 합치고 수정하는 과정은 괜찮은데 마지막에 최종 문자열을 낼 때 조건을 어떻게 해야 될지 모르겠어서 문자열을 분해해서 스택을 이용하기로 했다.

 

스택에 분해한 문자열을 넣을 때 110 문자열이 되는 부분은 제거하고 이어서 문자열을 넣었을 때 스택에 여백이 없이 들어가서 편할 것 같아 스택을 선택했다.

 

대부분 성공이었는데 시간 초과가 난 것들이 있어서 코드 수정이 필요한 것 같다.

 

 

최종 코드

import java.util.*;

class Solution {
    public String[] solution(String[] s) {
         Stack<Character> stack = new Stack<>();

    for (int i = 0; i < s.length; i++) {
      int count = 0;
      String temp = s[i];

      for (int j = 0; j < temp.length(); j++) {
        if (stack.size() > 1 && temp.charAt(j) == '0') {
          if (stack.peek() == '1') {
            stack.pop();
            if (stack.peek() == '1') {
              stack.pop();
              count++;
            } else {
              stack.push('1');
              stack.push('0');
            }
          } else {
            stack.push('0');
          }
        } else {
          stack.push(temp.charAt(j));
        }
      }

      StringBuilder sb = new StringBuilder();

      while (!stack.isEmpty()) {
        if (stack.peek() == '1') {
          sb.append(stack.pop());
        } else {
          sb.append("011".repeat(Math.max(0, count)));
          count = 0;
          sb.append(stack.pop());
        }
      }
      if (count != 0) {
        sb.append("011".repeat(Math.max(0, count)));
      }

      s[i] = sb.reverse().toString();

      stack.clear();
    }
    return s;
    }
}

 

문자열 배열에서 문자열을 꺼내 분해하여 스택에 넣는 과정은 다르게 바꿀 방법이 없는 것 같기도 하고 딱히 시간 초과가 날 부분이 없는 것 같아 수정하지 않았다.

 

수정한 부분은 분해하여 만든 스택을 다시 110을 넣어 사전 순으로 앞에 올 수 있도록 문자열을 만드는 과정이다.

 

이 과정에서 많은 수정을 했다.

 

처음에는 최총 출력될 부분을 스택으로 만들어 모든 문자를 스택에 넣고 사용자 정의 함수에서 스택을 문자열로 합쳐 출력했는다.

아마 이 부분이 오래 걸렸던 것 같다.

 

다시 수정한 방법은 ArrayList에 문자열을 추가하여 출력하는 방법이었는데, 여기서 문제가 있던 점은 인텔리제이에서는 실행이 잘 됐는데 프로그래머스 내에서는 실행이 안 되는 거였다.

스택에서 하나씩 꺼내 ArrayList에 추가했기 때문에 해당 배열을 역순으로 바꾸어 문자열로 바꾸어야 됐는데 이 과정에 문제가 있었다.

reversed라는 함수를 사용했는데 이 함수가 프로그래머스에서는 왠지 모르겠지만 실행이 안됐다. 라이브러리를 새로 임포트하기엔 이미 util 전체 라이브러리를 임포트해서 더 할 수 있는 게 없는 것 같아 다른 방법을 사용하기로 했다.

 

마지막으로 사용한 방법이 최종 코드에 있는 StringBuilder이다.

사실 StringBuilder를 사용하는 게 제일 효율도 좋고 빠른데 잘 사용하지 않게 되는 것 같다.

과정은 ArrayList와 비슷했다.

스택에서 꺼낸 문자들을 StringBuilder에 추가하여 reverse로 문자열을 뒤집어 해당 문자열 배열에 다시 넣는 방법으로 완성했다.