[알고리즘] 코딩인터뷰 완전분석 - 1.2 순열확인

1.2 순열확인

문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

• 두 문자열을 정렬한 뒤 비교하는 경우 - O(nlogn)

  #include <iostream>
  #include <algorithm>
  
  #define N 128
  using namespace std;
  
  int check_permutation(char *str1, char *str2) {
      sort(str1, str1 + N); 
      sort(str2, str2 + N); 
  
      for (int i = 0; i < N; i++) {
          if (str1[i] != str2[i])
              return -1;
      }
      return 0;
  }
  
  int main()
  {
      char str1[N] = "baac";
      char str2[N] = "abac";
      int ret; 
  
      if (check_permutation(str1, str2) < 0)
          cout << "These are not in permutation" << endl;
      else
          cout << "These are in permutation" << endl;
  }

  • 주어진 두개의 문자열을 정렬하여 for문을 통해 각각 비교한다. 두개를 비교해서 요소가 다른 경우는 순열이 아니기 때문에 return -1을 반환한다.

• 두 문자열을 정렬하지 않는 경우 - O(n)

  #include <iostream>
  
  #define N 128
  using namespace std;
  
  int check_permutation(char *str1, char *str2) {
      char tmp[N] = {0,};
  
      for (int i = 0; i < N; i++) 
          tmp[str1[i]]++;
  
      for (int i = 0; i < N; i++) 
          tmp[str2[i]]--;
  
      for (int i = 0; i < N; i++) {
          if (tmp[i] != 0)
              return -1;
      }
      return 0;
  }
  
  int main()
  {
      char str1[N] = "baac";
      char str2[N] = "abac";
      int ret; 
  
      if (check_permutation(str1, str2) < 0)
          cout << "These are not in permutation" << endl;
      else
          cout << "These are in permutation" << endl;
  }

  • tmp배열을 선언한다. str1을 하나씩 꺼낸 뒤 그 값을 다시 tmp배열의 인덱스로 사용하고 +1을 해준다. 만약 str1의 문자열이 abc로 주어졌으면, tmp['a']++ , tmp['b']++, tmp['c']++과 같이 진행될 것이다. 두번째 for문을 통해 첫번째 for문에서 +1 해준 것을 다시 -1 해준다. str2 문자열이 cba라면 첫번째 for문에서 +1 한 값들은 2번째 for문을 통해 -1 을 함으로써 결국 tmp 배열엔 0만 남아있게 된다.
  • 그리고 마지막 for문은 tmp배열을 하나씩 접근하며 0 아닌 다른 값이 있는지 확인한다. 만일 0이 아닌 다른 값이 있다면 str1과 str2는 순열 관계에 있지 않다.

• 혹시 해시 테이블을 사용할 수 없는가? 이 문제에서 해시 테이블은 유용한가? - O(n)

  #include <iostream>
  #include <unordered_map>
  
  using namespace std;
  
  int check_permutation(string str1, string str2) {
      unordered_map<char, int> umap;
  
      for (char &c : str1) {
          auto itr = umap.find(c);
          if (itr != umap.end())
              umap[c] = itr->second + 1;
  
          umap[c] = 1;
      }
  
      for (char &c : str2) {
          auto itr = umap.find(c);
          if (itr == umap.end() || itr->second - 1 < 0) 
              return -1;
  
          umap[c] = itr->second - 1;
      }
      return 0;
  }
  
  int main()
  {
      string str1 = "abbc";
      string str2 = "cbbac";
  
      if (check_permutation(str1, str2) < 0)
          cout << "These are not in permutation" << endl;
      else
          cout << "These are in permutation" << endl;
  }

• 서로 순열 관계에 있는 두 문자열은 같은 문자 집합으로 이루어져 있고, 그 순서만 다를 것이다. 순서도 같에 만들 수 있는가?

  • unordered_map대신 map을 사용하면 문자를 정렬시킬 수 있다.

• 앞선 2개의 코드는 아스키 코드가 들어올 것을 염두해두고 작성한 것이다. 만일 유니코드가 주어진다면, 넘어오는 문자열을 하나씩 꺼내 새로운 배열에 저장한 뒤 정렬시켜 비교하면 해결할 수 있다.