문제8 - 튜플 (Python)

프로그래머스

 

중괄호로 표현된 집합 기호 문자열을 파싱하여 원래의 튜플 순서를 찾아내는 문제입니다. 집합의 원소 개수가 적은 것부터 순차적으로 확인하며 새롭게 등장하는 숫자를 정답 배열에 추가하는 로직이 핵심입니다.

---

1.  나의 풀이 (Modular Approach)

최종적으로 개선된 코드입니다. 딕셔너리를 활용하여 중복 검사 속도를 최적화했으며, 파이썬의 map과 lambda를 활용하여 전처리를 수행했습니다.

def solution(s):
    # 1. 문자열 전처리: {{, }} 제거 후 },{ 기준으로 분리하여 리스트 생성
    strs_lists = list(map(lambda x: x.split(','), s[2:-2].split('},{')))
    
    # 2. 집합의 길이를 기준으로 오름차순 정렬
    strs_lists.sort(key=len)
    
    # 3. 딕셔너리를 사용하여 중복 검사 최적화 및 순서 기록
    answer = dict()
    for strs in strs_lists:
        for c in strs:
            # 리스트 탐색(O(n)) 대신 딕셔너리 탐색(O(1)) 수행
            if c not in answer:
                answer[c] = 1
                break

    # 4. 결과 반환: 키값을 정수형으로 변환
    return list(map(int, answer))

---

2. 오늘 배운 점 및 복기 노트

자료구조 선택에 따른 성능 최적화 초기에는 리스트를 사용하여 이전 집합과 현재 집합을 비교하는 방식을 사용했습니다. 하지만 이 방식은 데이터의 크기가 커질수록 탐색 효율이 떨어지는 문제가 있었습니다.

[개선 전 코드]

def solution(s):
    strs_lists = list(map(lambda x: x.split(','), s[2:-2].split('},{')))
    strs_lists.sort(key=len)
    answer = [int(strs_lists[0][0])]
    
    if len(strs_lists) == 1:
        return answer

    for i in range(1, len(strs_lists)):
        for c in strs_lists[i]:
            # 이전 리스트(strs_lists[i-1])를 매번 탐색하므로 시간 복잡도 증가
            if c not in strs_lists[i - 1]:
                answer.append(int(c))
                break

    return answer

 

리스트 탐색의 한계와 복기

위의 개선 전 코드에서는 c not in strs_lists[i - 1] 연산을 수행합니다. 이는 단순히 바로 이전 단계의 리스트만 확인하는 로직입니다. 문제의 특성상 바로 이전 집합과 비교해도 답을 구할 수는 있으나, 근본적으로 '이미 확인한 원소인가'를 판별하는 데 있어 리스트 탐색은 $O(n)$의 시간이 소요됩니다.

 

딕셔너리를 활용한 탐색 시간 단축

개선 후 코드에서는 answer를 딕셔너리로 선언했습니다. 딕셔너리의 키(Key) 존재 여부를 확인하는 것은 해시 테이블을 이용하기 때문에 $O(1)$의 시간이 소요됩니다. 데이터가 백만 개에 달하는 테스트 케이스에서 실행 시간을 약 10배 이상 단축할 수 있음을 확인했습니다.

형변환 시점 최적화 (Lazy Evaluation)

개선 전 코드와 교재의 코드 일부는 반복문 내부에서 매번 int() 형변환을 수행합니다. 이는 튜플의 길이를 $N$이라 할 때 약 $O(N^2)$ 번의 형변환을 야기합니다. 저는 중복 검사 시에는 문자열 상태를 유지하고, 최종 결과 반환 시에만 map(int, answer)를 사용하여 형변환 횟수를 $O(N)$으로 줄였습니다.

반복문 내 break 활용

각 집합에서 새롭게 추가된 원소는 단 하나입니다. 새로운 원소를 찾아 딕셔너리에 삽입한 즉시 break를 호출함으로써, 이미 확인된 나머지 원소들을 다시 검사하는 불필요한 루프를 차단했습니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

시간 복잡도 최적화: 리스트 vs 딕셔너리
배열(List)에서 in 연산을 통해 중복 여부를 검사하면 모든 인덱스를 순회하므로 $O(n)$의 시간이 소요됩니다. 반면 딕셔너리(Dictionary)는 해시 테이블을 기반으로 동작하여 $O(1)$의 시간 복잡도로 키의 존재 여부를 확인할 수 있습니다. 데이터의 양이 늘어날수록 탐색 효율에서 큰 성능 격차가 발생함을 확인했습니다.

문자열 파싱의 직관적인 접근
중괄호가 중첩된 복잡한 형태의 문자열을 다룰 때, 이를 문법적으로 해석하려 하기보다 s[2:-2].split('},{')와 같이 슬라이싱과 구분자를 활용해 데이터 본체만 빠르게 추출하는 전략이 유효합니다. 이는 정규표현식 없이도 파이썬의 기본 함수만으로 구현 난이도를 획기적으로 낮추는 방법입니다.

자료형의 특성을 활용한 배열 생성 및 최적화
교재에서는 딕셔너리를 리스트 생성자의 인자로 넣을 때( list(dict) ) 키값들이 순서대로 추출되는 특성을 활용합니다. 이 기법은 별도의 반복문이나 keys() 메서드 호출 없이도 딕셔너리에 저장된 순서대로 키값들을 배열로 변환할 수 있게 해줍니다.

저는 여기서 더 나아가, 반복문 내부에서 매번 발생하던 정수 형변환(int()) 작업을 최종 반환 시점으로 미루어 list(map(int, answer)) 형태로 구현했습니다. 이를 통해 교재에서 제시한 자료형 활용 팁을 유지하면서도 실제 연산 횟수를 획기적으로 줄여 성능을 극대화했습니다.