[알고리즘] 코딩인터뷰 완전분석 - 1.1 중복이 없는가

1.1 중복이 없는가

문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

• set 자료구조를 사용하는 경우

  #include <iostream>
  #include <set>
  #include <string.h>
  
  using namespace std;
  
  int main()
  {
      set<char> s;
      pair<set<char>::iterator, bool> pr;
      char *str = "combana";
      size_t len = strlen(str);
  
      for (int i = 0; i < len; i++) {
          pr = s.insert(str[i]);
          if (!pr.second)
              cout << "문자열에 중복된 문자가 있습니다." << endl;
      }    
  }

  • 문자열로부터 한글자씩 뽑아서 s컨테이너에 넣는다. pr은 삽입한 원소를 가리키는 반복자와 성공 여부의 bool인 pair객체이다.

 

• 자료구조를 사용하지 않는 경우

  1. 새로운 배열 arr[26]을 선언한다. (26 : 알파벳 개수)
     각 문자열을 하나씩 접근하며 'a'를 빼고, 뺀 결과 값(=ret)을 새로운 배열 arr 의 인덱스로 참조하여 해당 인덱스를 true로 만든다. 만일 'b'라는 문자열에 접근한 경우 'b' - 'a'를 하면 1이 나온다. 이 숫자 인덱스로 사용해 arr[1]을 true로 만든다. b라는 문자가 나오고 다시 b문자가 나오면 이미 b에 해당하는 arr 배열의 방이 true로 되어있기 때문에 if 문에서 걸린다. printf를 하고나서 break를 통해 for문을 탈출하게 된다.

     • 수정 전(이 코드는 문자 a~z만을 커버한다)

     #include <stdio.h>
     
     #define N 26
     using namespace std;
     
     int main()
     {
         char str[N] = "combana";
         bool arr[N];
         int ret;
     
         for (int i = 0; i < N; i++) {
             ret = str[i] - 'a';
             if (arr[ret]){
                 printf("문자열에 중복된 문자가 있습니다.\n");
                 break;
             }
             arr[ret] = true;
         }
     }

     • 수정 후(이 코드는 아스키 코드 전부를 커버한다)

     #include <stdio.h>
     #include <string.h>
     
     #define N 128
     using namespace std;
     
     int main()
     {
         char str[N] = ".,!@@^&*a";
         bool arr[N] = {0,};
         size_t len = strlen(str);
         int ret;
     
         for (int i = 0; i < len; i++) {
             ret = str[i];
             if (arr[ret]){
                 printf("문자열에 중복된 문자가 있습니다.\n");
                 break;
             }
             arr[ret] = true;
         }
     }

2. 비트 벡터를 사용하는 경우
   비트 연산을 이용하여 중복을 체크한다. a라는 문자가 처음 나온다. 이 때 is_duplicated는 ...0000 0001으로 셋팅된다. 그러다 맨 마지막 a가 나왔을 때 is_duplicated와 (1<<ret))을 AND으로 계산하면 1이상의 숫자가 리턴된다. 이 말은 이미 a라는 문자가 앞에 나왔다는 얘기다. (1<<ret는 ...0000 0001이다)

   #include <stdio.h>
   
   #define N 128
   using namespace std;
   
   int main()
   {
       char str[N] = "area";
       int is_duplicated = 0;
       int ret;
   
       for (int i = 0; i < N; i++) {
           ret = str[i] - 'a';
           if ( (is_duplicated & (1<<ret)) > 0){
               printf("문자열에 중복된 문자가 있습니다.\n");
               break;
           }
           is_duplicated |= (1<<ret);
       }
   }

 

생각하지 못한 것

1. 문자의 구성이 알파벳이라는 제한 없음(아스키 코드 or 유니코드)
2. 대소문자 구분에 대한 얘기 없음
3. 정렬에 대해 생각해보지 못했음
4. 아스키 코드 총 128개인데 int는 32bits 라서 32개 문자만 중복 검사 가능...