[알고리즘] 코딩인터뷰 완전분석 - 1.4 회문 순열

1.4 회문 순열

주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

• unordered_map자료구조를 사용하는 경우 - O(n)

  #include <iostream>
  #include <unordered_map>
  #include <algorithm>
  #include <string>
  
  using namespace std;
  
  bool solution(string input) {
      unordered_map<char, int> umap;
      size_t len = input.length();
      int odd_count = 0;
  
      transform(input.begin(), input.end(), input.begin(), tolower);
  
      for (char &c : input) {
          if (c == ' ') {
              len -= 1;
              continue;
          }
  
          auto itr = umap.find(c);
          if (itr != umap.end()) {
              umap[c] = itr->second + 1;
              continue;
          }
  
          umap[c] = 1;
      }
  
      if (len % 2 == 0) {
          for (auto itr = umap.begin(); itr != umap.end(); itr++) {
              if (itr->second % 2 != 0)
                  return false;
          }
      }
      else {
          for (auto itr = umap.begin(); itr != umap.end(); itr++) {
              if (itr->second % 2 != 0) 
                  odd_count++;
              if (odd_count > 1)
                  return false;
          }
      }
  
      return true;
  }
  
  int main()
  {
      string input = "Tact Coa";
      bool res;
      res = solution(input);
      cout << boolalpha << res << endl;
  }

  • transform함수를 사용해 입력으로 들어온 문자열을 모두 소문자로 만든다.

• 공백 문자를 검사한다. 만일 공백 문자면 continue를 통해 그 다음 문자를 읽는다(공백일 경우 len변수의 값을 1 빼준다)

• tact coa라는 문자열이 들어오면 (a,2), (c,2), (o, 1), (t, 2) 와 같이 저장한다.

• 문자열의 길이를 짝수, 홀수로 구분하여 회문 순열을 검사한다.

  • 짝수인 경우 : 짝수인 경우 각 문자의 개수가 모두 짝수여야 한다. 만일 한 문자라도 홀수 개일 경우 false를 리턴한다.
  • 홀수인 경우 : 홀수인 경우 한 문자만 홀수 개여야 하고 나머지 문자는 모두 짝수 개여야 한다.

• 개선할 수 있는 부분

  • 개선 전

    if (len % 2 == 0) {
          for (auto itr = umap.begin(); itr != umap.end(); itr++) {
              if (itr->second % 2 != 0)
                  return false;
          }
      }
      else {
          for (auto itr = umap.begin(); itr != umap.end(); itr++) {
              if (itr->second % 2 != 0) 
                  odd_count++;
              if (odd_count > 1)
                  return false;
          }
      }
    
      return true;

    • 개선 후

    bool found_odd = false;        // 새로운 변수 선언, len 변수 삭제
    
    for (auto ir = umap.begin(); itr != umap.end(); itr++) {
        if (itr->second % 2 == 1) {
            if (found_odd) {
                return false;
            }
            found_odd = true;
        }
    }
    return true;

    • found_odd와 같은 변수 하나만으로 중복을 판별할 수 있음을 기억하자.

---

• 비트벡터를 사용하는 경우(대소문자, 공백을 고려하지 않은 풀이)

  #include <iostream>
  
  using namespace std;
  
  int get_char_number(char c) {
      return c - 'a';
  }
  
  int toggle(int bitVector, int index) {
      if (index < 0) return bitVector;
      int mask = 1 << index;
      if ((bitVector & mask) == 0) {
          bitVector |= mask; 
      } else {
          bitVector &= ~mask;
      }
  
      return bitVector;
  }
  
  bool check_exactly_one_bit_set(int bitVector) {
      return (bitVector & (bitVector - 1)) == 0;
  }
  
  bool solution(string input) {
      int bitVector = 0;
  
      for (char &c : input) {
          int x = get_char_number(c);
          bitVector = toggle(bitVector, x);        
      }
  
      return bitVector == 0 || check_exactly_one_bit_set(bitVector);
  }
  
  

int main() 
{
    string input = "tactcoa";
    bool res;
    res = solution(input);
    cout << boolalpha << res << endl;
}

• 우선 알파벳을 0~25 사이의 숫자로 치환한 후 해당 문자가 등장할 때마다 치환된 위치의 비트 값을 바꿔준다. 그 다음 한 개 이하의 비트가 1로 셋팅되어 있는지 확인한다.

• 1로 셋팅된 비트가 없는지 확인하고 싶다면 간단한게 이 값이 0과 같은지 확인하면 된다. 하지만 1로 셋팅된 비트가 단 한 개 있다면 다음 내용을 잘 살펴보자.

• 00010000과 같은 정수를 생각해 보자. 이 숫자에서 1을 빼 보면 00001111이 된다. 여기서 주목할 점은 두 숫자에 겹치는 비트가 없다는 점이다.

• 00101000에서 1을 빼면 00100111이 되고, 이 둘은 겹치는 비트가 존재한다.

• 따라서 어떤 숫자에서 1을 뺀 뒤 AND 연산을 수행 했을 때 그 결과가 0이 아니라 면 해당 숫자는 정확히 한 비트만 1로 셋팅되었다는 것을 알 수 있다.