2019 카카오 개발자 겨울 인턴십 풀이

Level 1 - 크레인 인형뽑기 게임 풀이
Level 2 - 튜플 풀이
Level 3 - 불량 사용자 풀이
Level 4 - 호텔 방 배정 풀이
Level 3 - 징검다리 건너기 풀이

프로그래머스 - 튜플 링크
(2022.11.01 기준 Level 2)

문제

특정 튜플을 표현하는 집합이 담긴 문자열 s가 있을 때, s가 표현하는 튜플 반환

알고리즘

집합을 직접 올바르게 나눠 집합의 원소의 개수로 하여금 오름차순으로 정렬하여 표현하는 튜플을 찾아야 한다.

풀이

s는 {{a1},{a1,a2},{a1,a2,a3},...,{a1,a2,a3,a4,...,an}} 같은 형식이다.
그렇다면 일단 맨 앞과 뒤에 '{{'와 '}}를 제거해야 한다. 그리고 각 집합 사이에 있는 '},}'를 기준으로 나눠줘야 한다.

튜플이 (a1, a2, a3) 이라면 집합은 {{a1}, {a1, a2}, {a1, a2, a3}} 과 같이 주어진다. 하지만 집합 안 순서는 바뀔 수 있으므로 {{a2, a3, a1}, {a1}, {a2, a1}} 과 같이 주어질 수도 있다.
하지만 바뀌지 않는 사실이 있다.
원소의 개수가 오름차순이 되게 정렬하고 순서대로 살펴보면 나타난 적이 없는 원소가 하나씩 생긴다. 그 원소들의 순서가 바로 튜플의 순서가 되는 것이다.

이를 직접 구현하면 된다.

코드

def solution(s):
    appear = [False] * 200001 # 각 원소가 나타난 적이 있는지 판별
    answer = []

    # 맨 앞과 뒤에 '{{'와 '}}'를 제거 후, '},{' 를 기준으로 나누고
    # 나눈 각 집합을 ','로 나누어 리스트로 만들어준다.
    # 그리고 만들어진 리스트들을 원소의 개수로 정렬한다.
    for lst in sorted(map(lambda x: x.split(','), s[2:-2].split('},{')), key = lambda x: len(x)):
        for n in lst: # 나타난 적이 없는 원소를 찾을 때까지 리스트를 훑는다.
            n = int(n)
            if not appear[n]:
                appear[n] = True
                answer.append(n)
                break

    return answer

여담

다른 사람들의 풀이를 보고 알았던 점. 각 원소를 나타난 총 횟수가 내림차순이 되게 정렬하면 바로 튜플의 순서.
이걸 알아차리지 못했다니.. 관찰력이 좀 더 필요한 것 같다.