[알고리즘] 중복된 문자 찾기

문제 : 주어진 문자열에서 중복된 문자가 있으면 false를 반환하고, 중복된 문자가 없으면 true를 반환하도록 하여라.

 

예) str = "Hello"

결과 : false

이유 : 'l'은 두번 중복된다.

 

예) "Monday"

결과 : true

이유 : M o n d a y 모두 중복되는 문자가 하나도 없다.

 

단, 추가적인 자료구조는 사용할 수 없음. (HashTable, ArrayList, StringBuilder)

 

사실 여기서 HashSet(중복을 허용하지 않음)을 쓰면 간단히 해결될 문제이다. 하지만 문제에서 추가적인 자료구조는 사용하지 말라고 했으므로 다른 방법을 생각해 보자.

 

boolean isUnique(String str) {

	boolean[] char_set = new boolean[128];
    for (int i = 0; i < str.length(); i++) {
    int val = str.chatAt(i);
    if(char_set[val]) { //문자가 이미 등장했다면 true, 아니면 false
    	return false;
        }
        char_set[val] = true;
      }
     return true;
   }

 

차례대로 살펴보자. 

 

1. 먼저, boolean타입의 배열을 선언해 준다. boolean[] char_set = new boolean[128];에서 모든 요소는 기본적으로 false로 초기화된다. Java에서 boolean 배열을 생성할 때 모든 값은 자동으로 false로 초기화된다.

2. for문을 사용하여 문자열을 맨 앞부터 차례대로 순회한다.

3. int val = str.charAt(i)는 문자의 아스키 값을 반환 할 것이다. 각 문자는 고유한 아스키 값을 가지고 있다.

4. 배열을 확인한 후, true(즉, 이미 등장했던 문자라면) false를 반환하고, 아니면 char_set[val] = true;를 통해 등장한 문자열이라고 마킹 해 준다.

 

Hello를 예로 들어보자. 각 문자의 아스키 코드값은 다음과 같다.

 

'H': 72
'e': 101
'l': 108
'l': 108
'o': 111

 

그렇다면 맨 위의 H부터, val에는 72라는 정수(아스키 값)이 담길것이고, 우리가 처음 선언했던 boolean 타입 배열의 72번째 칸을 보면 초기에는 false일 것이다. 그러므로 if문을 빠져나가 char_set[72] = true;로 마킹을 해 준다.

 

...

 

이제 Hello의 첫번째 l을 보자. l의 아스키값은 108이므로 배열의 108번째 인덱스를 true로 바꿔준다. 하지만 두번째 l에서의 if문은 true를 반환 할 것이다. 이미 l이 등장했고(108번째 인덱스는 이미 true로 마킹 되어있음), if문이 true이므로 false를 반환하게 된다.

 

실제 코테에 비하면 말도 안되는 수준의 쉬운 알고리즘이였다. 하지만 자바에서 손뗀지 오래된 나로썬 boolean 타입의 배열을 초기화 할때 false로 초기화 된다는걸 다시 기억해 냈다. 이게 알고리즘 공부의 필요성일까... 급할수록 돌아가란 말이 있다. 이정도면 분명 Easy수준의 문제이지만 내가 boolean배열이 모두 false로 초기화 되는것을 몰랐다면 brute force를 이용해 O(n^2)가 나왔을것이다(모든 문자를 일일히 다른 문자와 비교).

 

+ 파이썬에서는 리스트 선언시에 자료형을 명시해줄 필요가 없다. 만약 파이썬 리스트에서 초기 배열의 값을 모두 False로 지정하고자 한다면 

 

char_set = [False] * 128

이렇게 쓸 수 있다.