[알고리즘] 코딩인터뷰 완전분석 - 1.3 URL화

1.3 URL화

문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다(자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하길 바란다).

예제
입력 : "Mr John Smith", 13
출력 : "Mr%20John%20Smith"

• + 연산을 사용하는 경우 - O(n)

  #include <iostream>
  
  using namespace std;
  
  void replace_spaces(string str, int len) {
     string ret = "";
  
     for (int i = 0; i < len; i++) {
         if (str.at(i) == ' ') {
             ret += "%20";
             continue;
         }
         ret += str.at(i);
     }
  
     cout << ret << endl;
  }
  
  int main()
  {
     string str = "Mr John Smith";
     int len;
     len = str.length();
  
     replace_spaces(str, len);
  }

  • 공백을 만나면 '%20'을 ret 문자열 끝에 붙이고, 공백이 아니면 str의 한 문자를 ret문자열 끝에 붙인다.

• 만일 (충분히 큰)문자 배열이 주어지고 공백 개수를 사용하여 문제를 푼다면? - O(n)

  #include <iostream>
  
  using namespace std;
  
  void replace_spaces(char str[], int len) {
      int spaceCount = 0, index, i = 0;
  
      for (i = 0; i < len; i++) {
          if (str[i] == ' ')
              spaceCount++;
      }
  
      index = len + spaceCount * 2;
      str[len] = '\0';
  
      for (i = len - 1; i >= 0; i--) {
          if (str[i] == ' ') {
              str[index - 1] = '0';
              str[index - 2] = '2';
              str[index - 3] = '%';
              index -= 3;
          } else {
              str[index - 1] = str[i];
              index--;
          }
      }
  
      cout << str << endl;
  }
  
  int main()
  {
      char str[256] = "ben milhouse";
      int len = 12;
  
      replace_spaces(str, len); 
  }

  • 문자열 조작 문제를 풀 때 널리 쓰이는 방법 중 하나는 문자열을 뒤에서부터 거꾸로 편집해나가는 것이다. 왜냐하면 이렇게 해야 마지막 부분에 여유 공간을 만들어 유용하게 사용할 수 있기 때문이다. 이 방식을 사용하면 덮어쓸 걱정을 하지 않고 문자들을 바꿔 나갈 수 있다.

  • 위의 코드에선 문자열을 두 번 훑어나간다. 처음에 공백 문자를 세고, 이를 통해 최종 문자열에 추가 공간이 얼마나 필요한지 계산한다. 두번째로 훑을 때에는 역방향으로 진행하면서 문자열을 편집한다. 공백을 만나면 %20을 복사하고, 공백 문자가 아니면 원래 문자를 복사한다.