프로그래머스 64065 - 튜플

https://school.programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

1. 문제

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

 

2. 문제풀이 포인트

1. { } 또한 문자열인데 이 안에서 있는 숫자 집합들을 어떻게 추출할 것인가

2. 숫자 집합의 길이순대로 정렬해야한다.

3. s의 길이는 5 이상 1,000,000 이하 이기 때문에, 시간복잡도를 생각해야한다.

 

3. 첫번째 코드

def solution(s):
    data = s[2:-2].split("},{") #튜플 분리하기
    data = sorted(data, key= lambda x: len(x))
    answer = []
    for item in data:
        item = list(map(int, item.split(",")))
        for value in item:
            if value not in answer:
                answer.append(value)
    return answer

✔️앞에 두글자, 뒤에 두글자를 슬라이스하고 가운데 "},{"를 기준으로 분리한다.

{{4,2,3},{3},{2,3,4,1},{2,3}}  -> ['3', '2,3', '4,2,3', '2,3,4,1']

✔️data원소들을 원소들의 길이에 따라 정렬한다.

✔️answer리스트에 value가 존재하는지 확인하고 존재하지 않으면 추가한다.

여기서 시간복잡도가 증가한다.

왜냐하면, 리스트의 in 연산은 평균적으로 O(n) 시간이 걸리기때문이다.

set()의 in과  add연산은 평균적으로 O(1) 시간이 걸리니 set을 사용하여 코드를 수정해보자.

 

4. 두번째 코드

def solution(s):
    data = s[2:-2].split("},{") #튜플 분리하기
    data = sorted(data, key= lambda x: len(x)) #정렬
    seen = set() #중복검사용
    answer = []
    for item in data:
        numbers = map(int, item.split(","))
        for n in numbers:
            if n not in seen:
                seen.add(n) #answer에 추가된 숫자인지 확인용
                answer.append(n)
    return answer

✔️정렬하는 것 까지는 코드가 위와 동일하다.

seen = set() 코드를 추가했다.

✔️리스트를 만드는 대신에 map 객체를 반환하여 메모리 사용을 줄였다.

✔️if n not in seen으로 먼저 seen에 숫자가 있는지 확인했다.

 

5. 테스트 결과

1) 첫번째 코드

 

2) 두번째 코드

 

전반적으로 두번재 코드의 시간이 더 적게 소요된걸 알 수 있다.