프로그래머스 Lv.2 | Python | 튜플

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다. (a1, a2, a3, ..., an) 튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}
예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}{{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}} 는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 조건

• s의 길이는 5 이상 1,000,000 이하입니다.숫자가 0으로 시작하는 경우는 없습니다.s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.

---

3. 접근 기준

이 문제는 문자열 파싱도 필요하지만, 핵심은 집합 크기 순서대로 보면 새로운 숫자가 하나씩 추가된다는 점이다.

예:

{2}
{2,1}
{2,1,3}
{2,1,3,4}

 

여기서 새로 등장하는 숫자만 보면:

2 → 1 → 3 → 4

 

 

• 집합 크기 기준 정렬
• 이전에 없던 숫자 찾기

이 흐름으로 접근하면 된다.

---

4. 사용한 패턴 / 알고리즘

문자열 처리

• 문자열 슬라이싱
• split 활용

정렬

• 집합 길이 기준 정렬

중복 제거

• 이미 등장한 숫자인지 확인

---

5. 핵심 아이디어

핵심은 집합을 길이 순으로 정렬하는 것이다.

길이 1 → 길이 2 → 길이 3 ...

 

이 순서대로 보면, 각 집합에는 이전 집합에 없던 숫자가 정확히 하나씩 추가된다.

따라서:

• 작은 집합부터 순회
• 처음 등장한 숫자를 answer에 추가

하면 튜플 순서를 만들 수 있다.

---

6. 풀이 코드

def solution(s):
    answer = []

    # 바깥 "{{" 와 "}}" 제거
    s = s[2:-2]

    # "},{" 기준으로 집합 분리
    s = s.split('},{')

    # 집합 길이 기준 정렬
    # 작은 집합부터 확인하기 위함
    s.sort(key=lambda x: len(x))

    seen = set()  # 이미 등장한 숫자 저장

    # 각 집합 순회
    for i in range(len(s)):

        # 문자열 숫자를 정수 리스트로 변환
        a = list(map(int, s[i].split(',')))

        for j in a:

            # 처음 등장한 숫자라면 추가
            if j not in seen:
                answer.append(j)
                seen.add(j)

    return answer

 

if j not in answer만 사용해도 정답은 맞게 나온다.
다만 리스트의 in 연산은 처음부터 끝까지 직접 확인해야 해서 시간 복잡도가 O(N)이다.

반면 set은 해시 기반 자료구조라서:

j in seen

 

연산을 평균 O(1)에 처리할 수 있다. 즉, 데이터가 많아질수록 차이가 커진다.

예를 들어:

if j not in answer:

 

는 answer 길이가 길어질수록 매번 전체를 확인해야 하지만,

if j not in seen:

 

은 거의 바로 찾을 수 있다. 그래서 실제 코딩테스트에서는:

• 순서 저장 → list
• 빠른 중복 확인 → set

이 두 개를 같이 사용하는 패턴이 자주 나온다.

---

7. 핵심 로직 요약

이 문제의 핵심은 집합 크기 순으로 정렬했을 때 새로운 숫자가 하나씩 추가된다는 점이다.

• 문자열을 집합 단위로 분리한다.
• 집합 길이 기준으로 정렬한다.
• 작은 집합부터 순회한다.
• 이전에 없던 숫자만 answer에 추가한다.

결국, “문자열 파싱 + 길이 기준 정렬 + 새로운 값 찾기” 이 흐름이 핵심이다.

---

8. 정리

 

처음 보면 문자열이 너무 복잡해서 파싱 문제처럼 느껴진다.

근데 실제 핵심은 문자열 처리보다도 이 부분이었다.

집합 크기가 커질 때마다 숫자가 하나씩 추가된다

 

이 패턴을 발견하면 문제 흐름이 갑자기 단순해진다.

또 하나 느낀 점은:

• if j not in answer 대신 set을 쓰는 게 훨씬 효율적이라는 점

리스트에서 in은 매번 처음부터 탐색하지만, set은 해시 기반이라 훨씬 빠르게 확인할 수 있다.

결국 이 문제는 문자열 처리 문제라기보다, 데이터 구조의 특징을 발견하는 문제에 가까웠다.