코딩테스트: zip() 활용 (04.06)

문제 1: 완주하지 못한 선수 찾기

문제 내용

문제 이해: 두개의 리스트가 주어지고 각 리스트에는 중복된 값이 들어있을 수 있다. 한쪽이 반드시 다른 한 쪽 보다 원소 갯수가 한개 많으며 그 한개 더 많은 원소를 알아내야 한다.

 

시도 1: 딕셔너리와 setdefault 이용해 집계

def solution(participant, completion):
    p_dict={}
    for p in participant: # 각 참가자들을 이름별로 집계
        p_dict.setdefault(p,0)
        p_dict[p]+=1
    for c in completion: # 완주한 사람의 이름의 집계횟수를 1 줄임
        p_dict[c] -=1
        if p_dict[c]==0: # 해당 이름의 모든 참가자가 완주했으면 아예 딕셔너리에서 꺼낸다
            p_dict.pop(c)
    return list(p_dict.keys())[0] # 하나남은 키-밸류 쌍의 키 반환

위 방식은 별개의 for문을 두번 돌리므로 O(n)의 시간복잡도를 가진다.

 

시도 2: 정렬과 zip사용

다른 사람의 답변을 보고 이 문제를 다음과 같이 접근할 수 있음을 알게 되었다.

1. 두 리스트의 원소는 하나만 빼면 똑같다.

2. 원소인 문자열들은 사전순으로 정렬 가능하다.

3. 따라서 둘을 정렬시키면, 딱 한군데 달라지는 지점이 생기거나, 더 짧은 리스트가 끝날 때 까지 같다.

4. 전자의 경우엔 달라진 지점의 참가자가 낙오자이다. 후자의 경우엔 가장 뒤의 참가자가 낙오자이다.

 

이를 코드로 구현하면 다음과 같다.

def solution(ps,cs):
    ps.sort()  # 정렬
    cs.sort()  # 정렬
    for p,c in zip(ps,cs):
        if p !=c:  # 다르면 참가자 반환
            return p
    return ps[-1]  # 마지막 참가자 반환

zip()

zip(a,b)은 두 리스트나 튜플의 같은 인덱스 상의 원소를 묶어주는 역할을 한다. 

zip([1,2,3],[4,5]) # (1,4),(2,5)

이를 이용해 for문을 각각 두번 돌려야 하거나 enumerate로 index를 이용해 접근하는 대신 더 편리하게 반복문을 작성할 수 있다.

 

해결: 어느것이 더 나은가?

시간복잡도 측면에서는 정렬을 하지 않고 접근하는 방식이 더 빠르다. 정렬의 시간 복잡도가 O(nlogn)이기 때문이다. 실제로 실행시간도 아래가 더 느리다.

그러나 정렬을 사용하는 방식은 transform-and-conquer 방식의 대표적인 예인 '정렬 처리 후 풀이' 방식이므로 나름의 가치가 있다.

 

문제 2. 행렬의 곱셈

문제내용

문제 이해: 두개의 이차원배열이 주어진다. 행렬 곱은 다음 사진과 같이 진행한다.

새로운 행렬의 크기는 M*N이고, i행 j열 원소의 값은 행렬1의 i 번째 행과 행렬2의 j 번째 열의 각 원소들을 곱한 것의 총합이다.

즉 문제의 핵심은 행의 배열로 이루어진 arr2에서 어떻게 열에 해당하는 배열을 뽑아낼 것이느냐이다.

해결: arr2를 풀어헤쳐서 나머지 연산과 몫 연산으로 열 형성하기

생각해낸 방법은 다음과 같다.

1. arr2의 행길이, 열길이를 잰뒤 1차원 배열로 만든다.

2. 같은 열에 위치한 원소의 1차원 배열에서의 인덱스 값은 행길이 만큼의 차이를 두고 떨어져 있다.

3. 따라서 적절한 인덱싱을 통해 열을 뽑아낼 수 있다.

이를 코드로 구현한 결과는 다음과 같다.

def solution(arr1, arr2):
    r1 = len(arr1)
    # c1 = len(arr1[0]) # 곱셈이 가능한 경우만 입력되므로 c1==r2
    r2 = len(arr2)
    c2 = len(arr2[0])
    arr2 = [arr2[i//c2][i % c2] for i in range(r2*c2)] # 1차원으로 풀어헤치기
    arr3 = []
    row = []
    for i in range(r1):
        row1 = arr1[i]
        for j in range(c2):
            row2 = arr2[j::c2] # arr2의 열 뽑아내기
            row.append(sum([x*y for x, y in zip(row1, row2)]))  # 곱의 합의 리스트 -> 열
        arr3.append(row) # 열 추가
        row = [] # 열 초기화

    return arr3

이 코드는 정답코드이긴했으나 for문의 사용이 많아 조금 아쉬웠다.

해결2:  zip의 또다른 활용

아래 코드는 다른 사람의 정답코드를 보고 참고하여 재구성한 코드이다.

def solution(arr1, arr2):
    arr3=[]
    for row in arr1: # arr1 로 부터 행 가져온다
        row3=[]
        for col in zip(*arr2): # zip과 언패킹을 이용해 arr2로부터 열 뽑아온다
            row3.append(sum([x*y for x,y in zip(row,col)])) # 곱의 합
        arr3.append(row3)
        
    return arr3

arr2는 행의 리스트이다. 이를 언패킹하여 zip에 인자로 넣으면 zip은 각 행의 같은 인덱스의 요소끼리 묶어 내보낼 것이다. 그러면 그것은 arr2의 열을 의미한다.

 

배운점

zip의 기능 및 활용

레퍼런스

https://www.daleseo.com/python-zip/

파이썬의 zip() 내장 함수로 데이터 엮기