숫자로만 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 이때 동일한 문자 두 개로 이루어진 쌍(pair)을 하나 만들고, 나머지 문자들은 모두 같은 문자 세 개씩 묶인 삼중 그룹(triplet)으로 구성할 수 있는 배치가 존재하는지 확인해야 합니다.
문제 이해하기
예를 들어 입력이 s = "21133123"이라면 출력은 True가 됩니다. 숫자 '2'가 정확히 두 개 있어 "22"라는 쌍을 만들 수 있고, 남은 문자들은 "111"과 "333"이라는 두 개의 삼중 그룹으로 깔끔하게 나눌 수 있기 때문입니다.
핵심 아이디어는 다음과 같습니다. 어떤 문자든 한 종류를 골라 두 개를 제거했을 때, 모든 문자의 남은 개수가 3으로 나누어떨어지면 조건을 만족하는 배치가 가능합니다.
해결 접근 방식
다음 단계에 따라 문제를 해결할 수 있습니다:
d := 문자열 s에 등장하는 각 문자의 빈도수를 담은 사전(Counter)을 생성합니다.
d의 각 키 k에 대해 다음을 반복합니다:
d[k]에서 2를 빼서 해당 문자로 쌍을 만들어 봅니다.
d에 포함된 모든 i에 대해 d[i] mod 3이 0이면 True를 반환합니다.
조건을 만족하지 않으면 d[k]에 다시 2를 더해 원래 상태로 되돌립니다.
모든 경우를 확인해도 조건을 만족하지 않으면 False를 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
from collections import Counter
def solve(s):
d = Counter(s)
for k in d:
d[k] -= 2
if all(d[i] % 3 == 0 for i in d):
return True
d[k] += 2
return False
s = "21133123"
print(solve(s))입력
"21133123"
출력
True
복잡도 분석
이 알고리즘은 서로 다른 문자의 종류 수를 m이라 할 때, 각 문자마다 전체 카운터를 한 번씩 검사하므로 시간 복잡도는 O(m × n)입니다(n은 문자열 길이). 공간 복잡도는 빈도수 사전 저장에 필요한 O(m)입니다.