자바(Java)로 문자 스트림에서 반복되지 않는 첫 번째 문자 찾기

문자 스트림에서 반복되지 않는 첫 번째 문자를 찾는 것은 코딩 인터뷰나 실시간 데이터 처리에서 자주 만나는 대표적인 문제입니다. 아래의 자바 코드를 사용하면 문자열을 한 글자씩 처리하면서, 매 시점 기준 첫 번째 비반복 문자를 손쉽게 확인할 수 있습니다.

예제

import java.util.ArrayList;
import java.util.List;
public class Demo{
    final static int max_chars = 256;
    static void non_repeating_char(){
        List<Character> my_list = new ArrayList<Character>();
        boolean[] repeat = new boolean[max_chars];
        String my_str = "Thisisasample";
        for (int i = 0; i < my_str.length(); i++){
            char x = my_str.charAt(i);
            if (!repeat[x]){
                if (!(my_list.contains(x))){
                    my_list.add(x);
                }
                else{
                    my_list.remove((Character)x);
                    repeat[x] = true;
                }
            }
            if (my_list.size() != 0){
                System.out.print("The first non-repeating character of the string is ");
                System.out.println(my_list.get(0));
            }
        }
    }
    public static void main(String[] args){
        non_repeating_char();
    }
}

출력 결과

The first non-repeating character of the string is T
The first non-repeating character of the string is T
The first non-repeating character of the string is T
...
(문자열의 길이인 13번 반복 출력)

코드 설명

Demo 클래스에는 non_repeating_char라는 이름의 함수가 정의되어 있습니다. 함수 내부에서는 먼저 리스트(my_list)를 생성하고, 분석 대상이 되는 문자열("Thisisasample")을 정의합니다.

이후 문자열을 처음부터 끝까지 순회하면서 각 문자를 하나씩 검사합니다. 특정 문자가 이미 반복된 적이 있는지 여부는 Boolean 배열인 repeat에 저장되는데, 반복된 문자는 true, 반복되지 않은 문자는 false로 기록됩니다.

리스트에는 현재까지 단 한 번만 등장한 문자들이 입력 순서대로 보관됩니다. 어떤 문자가 두 번째로 등장하면 리스트에서 제거되고 repeat 배열에 반복 표시가 남습니다. 따라서 매 시점 리스트의 첫 번째 요소(my_list.get(0))가 바로 그 순간의 첫 번째 비반복 문자가 됩니다.

main 함수에서는 non_repeating_char()를 호출하여 결과를 콘솔에 출력합니다. 위 예제에서는 문자열의 길이가 13이므로 각 문자를 처리할 때마다 결과가 출력되며, 'T'는 끝까지 한 번만 등장하기 때문에 항상 'T'가 첫 번째 비반복 문자로 출력됩니다.

참고: 더 효율적인 접근 방법

위 코드는 contains와 remove 연산 때문에 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있습니다. 문자열이 길다면 LinkedHashMap<Character, Integer>로 문자별 등장 횟수를 세거나, LinkedHashSet과 반복 문자 집합을 함께 사용하면 문자당 O(1)에 가까운 성능으로 개선할 수 있습니다.