튜플 · Hong-Iron

문제 보기 · Level 2 · 2019 카카오 개발자 겨울 인턴십 · 정답률 66% · 푼 사람 28,836명 (2026-09-30 기준)¹

문제

중복 없는 튜플 (a1, …, an)을 {{a1}, {a1, a2}, …, {a1, …, an}} 꼴의 집합들로 나타낸 문자열 s가 주어진다. 바깥 집합과 안쪽 집합 모두 원소 순서가 섞여 있을 수 있다. 원래 튜플을 배열로 돌려준다.

s 길이 5~1,000,000
원소는 1~100,000인 자연수
튜플 길이 1~500

풀이

막히면 한 단계씩 펼친다.

필요한 개념

문자열 파싱과 정규 표현식: 중괄호 문자열을 수 묶음들로 나누기
정렬과 정렬 기준: 묶음을 크기 순으로 세우기(key=len)
집합: 크기 순으로 세우면 앞 묶음이 뒤 묶음의 부분집합이 되고, 이웃한 두 묶음의 차집합은 원소 하나다

1단계 · 작은 예로 손으로 풀기

"{{2,1},{2},{2,1,3}}"

묶음을 꺼낸다: {2, 1}, {2}, {2, 1, 3}
크기 순으로 세운다: {2}, {2, 1}, {2, 1, 3}
앞 묶음에 없던 새 원소를 차례로 적는다: 2 → 1 → 3

답은 [2, 1, 3]이다. 크기가 하나씩 커지는 묶음마다 새 원소가 정확히 하나 늘기 때문이다.

2단계 · 가장 단순한 방법과 그 속도

튜플 길이가 최대 500이라 묶음은 500개, 원소는 모두 1 + 2 + … + 500 = 500 × 501 ÷ 2 = 125,250개다(1부터 n까지의 합은 n(n + 1)/2, 수열과 합의 기호). 이것들을 한 번씩 보는 것은 가볍다. 문자열 길이가 100만이라 문자열을 여러 번 훑는 방식만 피하면 된다.

3단계 · 핵심 아이디어

방법이 둘 있다.

크기 순: 묶음을 크기 순으로 세우고, 처음 보는 원소를 차례로 모은다.
등장 횟수: 첫 원소 a1은 모든 묶음(n개)에 들어 있고, a2는 n − 1개, …, an은 1개에 들어 있다. 그래서 수마다 등장 횟수를 세어 많이 나온 순으로 세우면 그것이 튜플이다. 괄호 모양을 신경 쓸 필요도 없이 숫자만 뽑아 세면 된다.

4단계 · 코드 흐름

크기 순 방법:

맨 앞 {{와 맨 뒤 }}를 떼고, },{로 잘라 묶음 문자열들을 얻는다.
묶음마다 ,로 잘라 정수 리스트로 만든다.
길이 순으로 정렬한다.
묶음을 차례로 보며 처음 보는 원소를 답에 넣는다(본 원소는 집합에 기억).

5단계 · 파이썬 코드

def solution(s):
    groups = s[2:-2].split("},{")                    # "2,1" "2" "2,1,3"
    groups = sorted((list(map(int, g.split(","))) for g in groups), key=len)
    answer, seen = [], set()
    for g in groups:
        for x in g:
            if x not in seen:
                seen.add(x)
                answer.append(x)
    return answer

s[2:-2]: 앞 두 글자 {{와 뒤 두 글자 }}를 뗀다.
split("},{"): 묶음 사이의 },{를 기준으로 자른다.
sorted(..., key=len): 길이(원소 개수)가 짧은 묶음부터 세운다.

등장 횟수 방법은 두 줄이다.

import re
from collections import Counter

def solution(s):
    count = Counter(re.findall(r"\d+", s))          # 숫자 덩어리마다 몇 번 나왔나
    return [int(x) for x, _ in count.most_common()]  # 많이 나온 순

most_common()은 (값, 개수)를 개수가 많은 순으로 돌려준다. 이 문제에서는 개수가 서로 다 달라서 순서가 하나로 정해진다.

6단계 · 실행 추적

"{{4,2,3},{3},{2,3,4,1},{2,3}}" (크기 순 방법)

크기 순 묶음	처음 보는 원소	답
[3]	3	[3]
[2, 3]	2	[3, 2]
[4, 2, 3]	4	[3, 2, 4]
[2, 3, 4, 1]	1	[3, 2, 4, 1]

등장 횟수로 보면 3이 4번, 2가 3번, 4가 2번, 1이 1번이라 결과가 같다.

7단계 · 복잡도와 흔한 실수

문자열 길이 L을 한 번 자르고, 원소 E개(최대 125,250)를 한 번씩 보니 \(O(L + E)\)다. 묶음 정렬은 500개라 무시할 만하다.

처음부터 ,로 잘라 묶음 경계를 잃는다.
원소를 글자 그대로 두고 비교하다 "20"과 "2"를 헷갈린다. 정수로 바꾸거나 숫자 덩어리 전체(\d+)로 센다.
각 묶음 안의 순서가 튜플 순서라고 믿는다. 문제는 안쪽 순서도 섞여 있다고 했다.

검증: 문제의 예시 5개를 통과했고, 무작위 튜플 2,000개를 문제 규칙대로 섞은 문자열로 바꿔 두 풀이 모두 원래 튜플을 되찾는 것을 확인했다 — 06_pg64065_p1.py

프로그래머스 스쿨, “튜플” (https://school.programmers.co.kr/learn/courses/30/lessons/64065), 2026-09-30 조회. ↩