[Lv2] 튜플(python)

1. 문제

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

코딩테스트 연습 - 튜플

 

2. 구현 과정

1) 문제 내 정의 정리

  * 튜플 - 어떤 순서를 따르는 요소들의 모임

           - 중복 원소 가능

           - 요소끼리의 순서 존재

           - 원소 개수는 유한

  * {}로 표현할 수 있는 집합 - 중복 원소가 없는 튜플의 원소들을 이용하여 {a1}, {a1,a2}, {a1,a2,a3..} 등으로 표현하는 집합

 2) 출력 값 : 특정 튜플을 표현하는 집합이 담긴 s가 주어질 때,  s가 표현하는 튜플 

 

 /*** 처음 시간초과 났던 방식 ***/

 3) 알 수 있는 정보 : 집합 내에 i개가 있는 집합은 a1~ai까지의 집합이다. 

             -> 튜플은 "순서가 있는 집합"이므로, 순서가 없는 집합 -> 순서가 있는 튜플로 변경해야 함

             -> i개가 있는 집합에만 있고, i-1개가 있는 집합엔 없는 숫자 = 튜플의 i번째 문자(순서가 고정됨)

             -> 중복 원소가 없는 원소들이므로, 튜플이 a1~an까지의 요소들의 모임이라면 a1은 {}집합들에서 n번 있을 것. a2는 n-1번... an은 1번 있을 것임

 

4) 구현 : 집합들에서 각 숫자가 몇 번 포함되어있는지를 세는 counting 배열을 만든 후, count 값이 n번인 숫자부터 내림차순으로 출력한다.

 

5) 위 방법의 문제 : 시간 초과. count값이 n번인 숫자, n-1번인 숫자,...,1번인 숫자를 구하는데 2중 for문이 필요하므로 시간 초과가 발생한다!!!! 만약 코딩테스트에서 이 문제를 만났다면 위 방식으로 구현까지 다 했다가 시간초과 나서 시간 낭비만 했을 것 같다ㅠㅠㅠ 

 

/**다시 푼 방법 */

3) 알 수 있는 부분 : i개가 있는 집합에만 있고, i-1개가 있는 집합엔 없는 숫자 = 튜플의 i번째 문자(순서가 고정됨).  

-> 집합들을 2차원 리스트로 받은 후, 집합의 길이를 기준으로 오름차순 정렬 ( 이렇게 되면 자연스럽게 {a1}, {a1,a2}, {a1,a2,a3}의 순서로 2차원 리스트가 정렬됨

-> i 번째 list와 i-1번재 list의 차집합은 항상 숫자 1개가 될 것이고, 그 숫자는 ai 

-> for문 i = 1~n-1범위를 돌면서 a1~an-1을 구하여 answer에 삽입

 

3. 실수한 것 & 새로 안 것

- 입력값 확인하기

    1) 배열인가, 문자열인가

    2) 배열이라면 2차원 배열인가 1차원 배열인가

    3) 입력 단위가 띄어쓰기인가 엔터인가

 -> 위 3개는 꼭 파악하고 넘어가기

 

- 문제보고 쉬워 보인다고 바로 코드 작성하려 하지 말고, 데이터의 범위를 생각해보자!!!!!!

 

- 파이썬에서 데이터 범위가 10만이 나오면 NlogN으로 풀어야 하므로 2충 for문을 쓰지 않아야 한다. 혹은 2중 for문이 아니더라도 데이터의 범위가 2000만이 넘으면 안된다!!

 

- 배열 슬라이싱 할 대, end값은 포함 안됨

 

- 두 리스트를 비교해서 차집합 구하는 법 

(array = 2차원 list ) 

  1)  list( set (arrayA) - set(arrayB) ) 

   #방법 1. i번째 list와 i-1번째 list값을 비교해서 없는 문자를 answer에 삽입
    for index in range(1, len(array)):
        before_set = array[index-1]
        current_set = array[index]
        answer.append( int(list(set(current_set) - set(before_set))[0]) )

 

  2) set 선언 후 비교

    #방법 2. 임시set을 만든 후, set에 없는 대상을 answer에 삽입
    mySet = set()
    for ith_list in array: 
        for x in ith_list:
            if x not in mySet: #직전 배열들엔 없었던 문자 x를 answer에 삽입 
                mySet.add(x) 
                answer.append(x)

 

 

4. 코드

1) 시간 초과

#시간 초과
def solution(s):
	answer = [] 
    
    # s의'{', '}' 입력 제거
    N = s.count("{") - 1 #집합 개수 = 튜플의 원소 개수
    for x in range(len(s)): 
  	  s = s.replace("{","") s = s.replace("}","")
      
    #,단위로 분할한 list 생성  
    numbers = list( map(int,s.split(',')) )
    num_cnt = {} #num_cnt : 각 배열의 인덱스 번호가 몇 번 있었는지 counting하는 배열
    for number in numbers: 
   		if number in num_cnt: 
   			num_cnt[number] += 1
   		else: num_cnt[number] = 0 
        
    #배열 값이 가장 큰 값에서부터 내림 차순으로 배열의 index를 찾아서 answer에 삽입
    answer_list = sorted(num_cnt.items(), key=lambda x: x[1], reverse = True)
    answer = list( value[0] for value in answer_list ) 
    return answer

2) 정답

def solution(s):
    answer = []
    
    s = s[2: -2] #의 양 끝 {{ , }} 삭제   
    num_set = [list(map(int, x.split(','))) for x in s.split('},{')] #'},{'으로 분할하여 각 집합들을 2차원 리스트에 저장 
    num_set.sort(key = lambda x : len(x))

    #방법 1. 맨 첫번째 값을 넣고, i번째 list와 i-1번째 list값을 비교해서 없는 문자를 answer에 삽입
    answer.append(num_set[0][0])
    
    for index in range(1, len(num_set)):
        before_set = num_set[index-1]
        current_set = num_set[index]
        answer.append( int(list(set(current_set) - set(before_set))[0]) )
    '''
    #방법 2. 임시set을 만든 후, set에 없는 대상을 answer에 삽입
    mySet = set()
    for i in num_set:
        for x in i:
            if x not in mySet: #직전 배열들엔 없었던 문자 x를 answer에 삽입 
                mySet.add(x) 
                answer.append(x)
    '''
                       
    return answer