[프로그래머스]튜플

[60] 튜플

책 구매하기

문제 정보

• 분류: 정렬
• 정답률: 56%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 파싱, 집합 크기, 정렬, 문자열 처리
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/64065

문제를 읽을 때 체크할 포인트

튜플 규칙을 그대로 보면 길이가 1인 집합부터 차례로 새 원소 하나씩 추가되는 구조다. 그래서 집합 문자열들을 길이순으로 정렬하고, 아직 못 본 숫자를 하나씩 뽑으면 된다.

정렬 문제는 손이 바빠지기 전에 비교 기준부터 정리하는 게 먼저다. 어떤 값을 기준으로 한 번만 정렬하면 그다음 오히려 짧아지는 경우가 많다.

풀이 흐름

1. 문자열에서 바깥 괄호를 제거하고 집합 단위로 나눈다.
2. 집합 문자열을 길이순으로 정렬한다.
3. 작은 집합부터 보며 아직 answer에 없는 숫자를 추가한다.

구현할 때 놓치기 쉬운 부분

집합처럼 보일 수 있지만 실제로는 등장 횟수 정보가 중요하다. 원소가 몇 번째로 많이 등장했는지를 기준으로 튜플 길이를 복원해야 한다.

파이썬 정답 코드

def solution(s):
  # 문자열에서 바깥 괄호를 제거하고 집합 단위로 나눈다.
  parts = s[2:-2].split("},{")
  groups = [list(map(int, part.split(","))) for part in parts]
  groups.sort(key=len)

  seen = set()
  answer = []
  # 집합 문자열을 길이순으로 정렬한다.
  for group in groups:
    # 작은 집합부터 보며 아직 answer에 없는 숫자를 추가한다.
    for num in group:
      if num not in seen:
        seen.add(num)
        answer.append(num)

  return answer

시간 복잡도

N은 파싱한 집합 문자열 개수이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.