[프로그래머스] 튜플 (파이썬)

 

코딩테스트 연습 - 튜플

 

 

 

 

 

Input : 숫자와 '{', '}', ',' 로만 이루어져 있는 문자열 (예시 : "{{2},{2,1},{2,1,3},{2,1,3,4}}")

 

수행 작업 : 특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 제출

Output : 숫자 원소들로 구성된 1차원 리스트

 

 

수행 과정

입력 : {{1,2,3},{2,1},{1,2,4,3},{2}}

{{1,2,3},{2,1},{1,2,4,3},{2}} → answer : [2]

{{1,2,3},{2,1},{1,2,4,3},{2}} → answer : [2, 1]

{{1,2,3},{2,1},{1,2,4,3},{2}} → answer : [2, 1, 3]

{{1,2,3},{2,1},{1,2,4,3},{2}} → answer : [2, 1, 3, 4]

 

 

 

[첫번째 아이디어]

 

- 집합 원소의 개수를 key, 집합 원소들을 value로 하는 dict 자료형으로 변환
- 원소의 개수가 적은 순서대로 읽어서 answer 리스트에 없는 숫자를 append

 

코드

효율성 테스트

from collections import defaultdict def solution(s):     s = s.replace('{', '')     split = list(s.split('}'))[0:-2]     tuple_dict = defaultdict()     answer = []     for _tuple in split:         tuple_values = _tuple.split(',')         if tuple_values[0] == '':             tuple_values.pop(0)         tuple_dict[len(tuple_values)] = list(map(int, tuple_values))     for i in range(len(tuple_dict)):         for num in tuple_dict[i+1]:             if num not in answer:                 answer.append(num)                 continue     return answer

 

비효율 요소

dicionary 자료형으로 입력값을 재저장하여 메모리의 낭비 발생

너무 많은 반복문이 존재함

 

 

 

[두번째 아이디어]

 

- dict 자료형 대신 원소의 개수를 key로 하여 리스트 자체를 정렬함

 

코드	효율성 테스트
def solution(s):     answer = []     s = s[2:-2].replace(',{', '')     _tuple = sorted(s.split('}'), key=len, reverse=True)     while _tuple:         tuple_values = list(map(int, _tuple.pop().split(',')))         for num in tuple_values:             if num not in answer:                 answer.append(num)                 continue     return answer

 

변경 결과

메모리의 사용량이 최대 70%로 감소함

속도가 약간 느려짐

 

비효율 요소

2중 반복과 not in 연산자의 사용으로 여전히 너무 많은 반복이 수행됨

 

 

 

[세번째 아이디어]

 

- 리스트를 set 자료형으로 변경하여 차집합을 구하면 while문의 각 반복에서 하나의 원소만 남게 될 것

 

코드	효율성 테스트
def solution(s):     answer = []     s = s[2:-2].replace(',{', '')     _tuple = sorted(s.split('}'), key=len, reverse=True)     while _tuple:         tuple_values = list(map(int, _tuple.pop().split(',')))         this = set(tuple_values).difference(set(answer))         answer += (list(this)) return answer

 

변경 결과

속도가 대폭 증가하여 기존 코드의 10% 정도의 시간만을 사용함

두 개의 리스트를 비교하여 차이를 구하는 문제에서는 set 자료형으로 변경 후 차집합 연산을 수행하는 것이 해답일 수 있겠음