Java에서 문자열 안에 가장 먼저 반복해서 등장하는 문자를 찾으려면 HashSet을 활용하는 것이 가장 효율적입니다. HashSet은 중복 저장을 허용하지 않으며, 특정 요소의 존재 여부를 평균 O(1) 시간에 확인할 수 있기 때문에 이 문제에 매우 적합합니다.
예제 코드
import java.util.*;
public class Demo{
static char repeat_first(char my_str[]){
HashSet<Character> my_hash = new HashSet<>();
for (int i=0; i<=my_str.length-1; i++){
char c = my_str[i];
if (my_hash.contains(c))
return c;
else
my_hash.add(c);
}
return '\0';
}
public static void main (String[] args){
String my_str = "thisisasampleonlysample";
char[] my_arr = my_str.toCharArray();
System.out.println("The first repeating character in the string is :");
System.out.println(repeat_first(my_arr));
}
}
실행 결과
The first repeating character in the string is : i
코드 동작 원리
Demo 클래스에는 repeat_first라는 정적 메서드가 정의되어 있으며, 이 메서드는 문자 배열을 매개변수로 받습니다. 메서드 내부에서는 새로운 HashSet 객체를 생성한 뒤, 문자열을 처음부터 끝까지 한 글자씩 순회하면서 해당 문자가 이미 집합에 존재하는지 검사합니다.
이미 존재한다면 그 문자가 곧 가장 먼저 반복된 문자이므로 즉시 반환하고, 존재하지 않는다면 집합에 추가합니다. 이렇게 하면 어떤 문자가 두 번째로 등장하는 순간 바로 반환되기 때문에, 문자열에서 가장 먼저 중복된 문자를 정확하게 찾아낼 수 있습니다.
main 메서드에서는 예제 문자열을 정의하고, toCharArray() 메서드를 사용해 이를 문자 배열로 변환합니다. 이후 변환된 배열을 인자로 repeat_first 메서드를 호출하고, 그 결과를 콘솔에 출력합니다.
시간 복잡도
HashSet의 삽입과 조회 연산은 평균적으로 O(1)이므로, 전체 알고리즘의 시간 복잡도는 문자열 길이를 n이라 할 때 O(n)입니다. 공간 복잡도 역시 최악의 경우 모든 문자를 저장해야 하므로 O(n)입니다. 이중 반복문으로 모든 문자 쌍을 비교하는 O(n²) 방식보다 훨씬 빠릅니다.
응용: 첫 번째 반복 단어 찾기
동일한 원리는 단어 단위에도 그대로 적용할 수 있습니다. 문자열을 공백 기준으로 분리한 뒤 HashSet<String>에 담으면, 가장 먼저 반복되는 단어를 찾을 수 있습니다.
static String repeatFirstWord(String str){
HashSet<String> set = new HashSet<>();
for (String w : str.split("\\s+")){
if (!set.add(w)) return w;
}
return null;
}
set.add()는 이미 값이 존재하면 false를 반환하므로, 위 코드처럼 반환값을 활용하면 조건 검사와 추가 작업을 한 줄로 처리할 수 있습니다.