문제 개요
문자열 s와 하나의 문자 c가 주어졌을 때, s에 등장하는 모든 문자 c가 서로 붙어서(연속적으로) 나타나는지 확인해야 합니다. 특히 문자 c가 문자열에 아예 존재하지 않는 경우에도 true를 반환해야 한다는 점에 유의하세요.
예를 들어 입력이 s = "bbbbaaaaaaaccddd", c = 'a'라면, 문자 'a'는 한 덩어리로만 등장하기 때문에 출력은 True가 됩니다. 반대로 "aabaa"처럼 같은 문자가 여러 구간에 나누어 등장한다면 False를 반환해야 합니다.
해결 접근 방식
이 문제는 불리언 플래그 하나와 인덱스를 활용한 선형 탐색으로 간단히 해결할 수 있습니다. 사용되는 핵심 변수는 다음과 같습니다.
- flag: 문자 c의 첫 번째 연속 구간을 이미 지났는지 여부를 저장합니다.
- index: 현재 검사 중인 문자의 위치입니다.
- n: 문자열의 전체 길이입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- flag를 False로, index를 0으로 초기화하고, n을 문자열 길이로 설정합니다.
- index가 n보다 작은 동안 다음을 반복합니다.
- 현재 문자가 c와 같다면 — flag가 이미 True인 경우 두 번째 그룹이 발견된 것이므로 즉시 False를 반환합니다. 그렇지 않다면 c가 연속되는 구간을 모두 건너뛴 후 flag를 True로 설정합니다.
- 현재 문자가 c와 다르다면 index를 1 증가시킵니다.
- 반복이 정상적으로 끝나면 True를 반환합니다.
Python 구현 예제
def solve(string, c):
flag = False
index = 0
n = len(string)
while index < n:
if string[index] == c:
if flag == True:
return False
while index < n and string[index] == c:
index += 1
flag = True
else:
index += 1
return True
s = "bbbbaaaaaaaccddd"
c = 'a'
print(solve(s, c))입력 및 실행 결과
입력:
"bbbbaaaaaaaccddd", 'a'
출력:
True
동작 원리 살펴보기
예제 문자열 "bbbbaaaaaaaccddd"를 처음부터 훑어가면, 인덱스 4에서 처음으로 'a'를 만납니다. 이때 flag가 False이므로 'a'가 연속되는 구간(인덱스 4~10)을 모두 건너뛴 뒤 flag를 True로 변경합니다. 이후 문자열이 끝날 때까지 다시 'a'를 만나지 않으므로 최종적으로 True가 반환됩니다. 만약 문자열 중간에 또 다른 'a' 그룹이 존재했다면, flag가 이미 True인 상태에서 해당 문자를 발견하는 순간 False를 반환하게 됩니다.
시간 및 공간 복잡도
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 따라서 매우 긴 문자열에 대해서도 효율적으로 동작합니다.