이번 문제는 프로그래머스의 레벨 3 110 옮기기이다.
문제를 차근차근 한 번 읽어보도록 하자.

최대 1000000개의 문자열이 주어진다.
이 때, 문자열의 길이는 최대 1000000으로 정해지며,
주어진 문자열 길이의 합이 1000000을 넘을 수 없다.

우리는 이제부터 문자열을 사전 순으로 가장 빠른 문자열로 고쳐야한다.
단, 부분 문자열 110만을 옮겨 가장 빠른 문자열로 만들어라!

완전 탐색?

과연 완전 탐색으로 이 문제를 풀 수 있을까?
110을 옮기는 모든 경우를 찾아보아야 하는 것인데,
직관적으로 보았을 때 불가능하다는 생각이 든다.

1000000 길이의 문자열 하나를 모두 완전탐색 하려면,
O(N^2) 혹은, 그 이상의 탐색이 필요하기 때문에 구체적으로 보아도 불가능하다.

Greedy?

그래서 그리디하게 풀 수 있는 방법이 있지 않을까 생각해보았다.
문득 어차피 110보다 큰 수는 111밖에 없다는 생각이 들었다.
그럼 앞에서 부터 111을 찾고, 이후 나오는 110과 교체해주면?
자연스럽게 사전 순으로 빨라지게 될 것이다.

또한 110보다 뒤에 나오는 111을 제외한 모든 문자열은?
당연히 110보다 작은 문자열이 된다.
즉, 110 보다 뒤에 있는 경우엔 당연히 문자열 순서가 느려진다.
그럼 해당 문자열과 110의 위치를 바꿔주어야 할 것이다.

여기까지는 생각을 할 수 있었다.
하지만 이것을 어떻게 구현할지가 문제이다.
111을 찾아 바꾸는 것 까진 구현을 했으나, 그 이후가 문제였다.
110보다 이후에 나오는 작은 수들과 바꾸는 과정을 구현하기 어려웠다.
또한 이 로직들에 대해서 제출을 했을 때 시간 초과가 발생함을 확인했다.

결국 다른 사람들의 풀이를 참고하게 되었다.
굉장히 놀라운 아이디어가 있었다.

110보다 큰 숫자는 언급했다시피 111 뿐이다.
그래서, 만약 문자열에 0이 없다면? 모든 110은 앞에 붙는다.
그럼 만약 0이 있다면? 이땐 가장 마지막 0 뒤에 110이 붙는다.
어째서 이런 논리가 가능할까?

간단하게 생각해서, 0이 큰 자리로 갈수록 숫자가 작아지기 때문이다.
만약 1110001이라는 숫자가 있을 때, 가장 빠른 문자열을 만드려면?
110을 100뒤로 옮긴 1001101`이 가장 빠른 문자열이 될 것이다.

가장 마지막 1 뒤로 옮긴 1001110은 어떨까?
110의 마지막 문자도 0임을 우리는 간과해서는 안된다.
해당 0이 마지막 1보다 뒤로 간 탓에 문자열의 순서는 더 느려졌다.
따라서 우리가 해야할 일은 아래와 같다.

  1. 문자열에서 만들어지는 110을 모두 제거한다.
  2. 가장 마지막으로 등장하는 0의 위치를 찾는다.
  3. 해당 위치의 뒤로 제거한 110들을 차례로 붙인다.

최종적으로 아래와 같이 구현되었다.

  • 110 추출
    • 처음엔 find 함수를 이용해서 구현했지만, 시간초과가 발생했다.
    • 결국 직접 substr를 이용해 110인 경우 즉시 지워주었다.
for (int j = 0; j < s[i].size(); j++) {
    result_str += s[i][j];

    if (result_str.size() >= 3) {
      if (result_str.substr(result_str.size() - 3, 3) == "110") {
        zero_cnt++;
        result_str.erase(result_str.size() - 3, result_str.size());
      }
    }
  }
  • 가장 마지막 0 찾기
    • for문 한 번으로 찾아낼 수 있다.
    • 찾지 못하는 경우는 1 밖에 없는 경우이다.
int zero_pos = -1;
for (int j = result_str.size() - 1; j >= 0; j--) {
    if (result_str[j] == '0') {
      zero_pos = j;
      break;
    }
}

string temp = "";
if (zero_pos == -1) {
    // 문자열에 0이 없는 경우
        while (zero_cnt--)
          temp += "110";

        temp += result_str;
        answer.push_back(temp);
  }
  else {
      for (int j = 0; j < result_str.size(); j++) {
          if (j == zero_pos) {
              temp += result_str[j];
              while (zero_cnt--)
                  temp += "110";
          }
          else
              temp += result_str[j];
          }

        answer.push_back(temp);
}