문자열 문제를 보다 보면 단순히 중복이 있는지만 확인하는 것이 아니라, 순서까지 함께 고려해야 하는 문제가 자주 나옵니다.

이번 글에서는 문자열을 왼쪽에서 오른쪽으로 읽어 가면서, 가장 먼저 다시 등장하는 문자를 찾는 문제를 정리해보겠습니다.

이 문제는 어렵지 않지만, 문자를 이미 본 적이 있는지 빠르게 확인해야 하므로 Set(셋) 자료구조를 연습하기에 좋습니다.

문제

문자열 s가 주어질 때, 왼쪽에서 오른쪽으로 읽어 가며 처음으로 다시 등장한 문자를 반환하는 함수를 작성해보겠습니다.

어떤 문자가 한 번 나온 뒤 나중에 또 나왔을 때, 그 순간 가장 먼저 재등장한 문자를 정답으로 반환하면 됩니다.

만약 끝까지 봐도 다시 등장한 문자가 없다면 None을 반환하면 됩니다.

함수 형식은 아래와 같습니다.

first_repeated_char(s)
  • s: 문자열
  • 반환값: 가장 먼저 다시 등장한 문자 또는 None

예시 1

입력: "abca"
출력: "a"

설명:

  • a를 처음 봅니다
  • b를 처음 봅니다
  • c를 처음 봅니다
  • 다시 a가 나옵니다

따라서 정답은 "a"입니다.

예시 2

입력: "abccba"
출력: "c"

설명:

  • a 처음 등장
  • b 처음 등장
  • c 처음 등장
  • 다음 c가 나오는 순간, 처음으로 “다시 등장한 문자”가 생깁니다

그래서 정답은 "c"입니다.

예시 3

입력: "abcd"
출력: None

설명:

  • 어떤 문자도 다시 나오지 않았으므로 None

처음 떠오르는 생각

이 문제의 핵심은 단순합니다.

문자를 하나씩 보면서:

  1. 처음 보는 문자라면 저장합니다
  2. 이미 저장된 문자라면 바로 반환합니다

즉, 이 문자를 전에 본 적 있는지를 빠르게 확인할 수 있어야 합니다.

여기서 Set이 잘 맞습니다.

핵심 아이디어

리스트에 저장해도 되지만, 리스트에서 어떤 값이 있는지 확인하려면 매번 처음부터 찾아야 할 수 있습니다.

반면 Set은 보통 값이 있는지 빠르게 확인할 수 있습니다.

이 문제는 문자열을 한 번만 훑으면서, 현재 문자가 이미 등장했는지만 확인하면 되기 때문에 Set을 쓰면 아주 깔끔하게 풀립니다.

예를 들어 "abccba"를 보면:

  • a → 처음 봄 → seen에 추가
  • b → 처음 봄 → seen에 추가
  • c → 처음 봄 → seen에 추가
  • c → 이미 있음 → 바로 "c" 반환

즉, 처음부터 끝까지 전부 다 셀 필요도 없습니다. 처음으로 다시 나온 순간 바로 끝낼 수 있습니다.

코드

def first_repeated_char(s):
    seen = set()

    for ch in s:
        if ch in seen:
            return ch
        seen.add(ch)

    return None

코드 해설

1) 이미 본 문자를 저장할 공간 만들기

seen = set()

set()은 중복 없이 값을 저장하는 자료구조입니다.

여기에는 지금까지 본 문자들을 넣어둘 겁니다.

2) 문자열을 왼쪽부터 하나씩 확인하기

for ch in s:

문자를 순서대로 확인해야 하므로 앞에서부터 차례대로 순회합니다.

3) 이미 본 문자라면 바로 반환하기

if ch in seen:
    return ch

이 문장이 핵심입니다.

현재 문자가 이미 seen 안에 있다면, 그 문자는 처음으로 다시 등장한 문자이므로 바로 반환하면 됩니다.

4) 처음 보는 문자라면 저장하기

seen.add(ch)

아직 못 본 문자라면 seen에 추가합니다.

5) 끝까지 못 찾았다면 None 반환하기

return None

반복문이 끝날 때까지 중복 문자를 못 찾았다면 다시 등장한 문자가 없는 것이므로 None을 반환합니다.

실행 예시

입력:

"abca"

초기 상태:

seen = {}

문자 하나씩 확인해보겠습니다.

a

  • 아직 없음
  • seen = {a}

b

  • 아직 없음
  • seen = {a, b}

c

  • 아직 없음
  • seen = {a, b, c}

a

  • 이미 있음
  • 바로 "a" 반환

정답은 "a"입니다.

복잡도

문자열 길이를 N이라고 하면:

  • 시간 복잡도: O(N)
  • 공간 복잡도: O(N)

문자열을 한 번만 순회하므로 시간은 O(N)입니다.

정리

이 문제는 단순히 “중복 문자가 있는가”를 묻는 문제가 아니라, 가장 먼저 다시 등장한 문자를 찾는 문제입니다.

즉 개수보다 순서가 더 중요합니다.

핵심은 한 줄로 정리할 수 있습니다.

문자를 왼쪽부터 보면서, 이미 본 문자라면 바로 반환한다.

즉:

  • 순서대로 확인하고
  • 본 적 있는지 저장하고
  • 다시 나오면 바로 끝냅니다

이 흐름만 이해하면 쉽게 풀 수 있습니다.

이 글의 문제 상황과 예시는 학습용으로 직접 재구성한 내용입니다.