[Python] 프로그래머스 lv2 - 두 큐 합 같게 만들기

[Python] 프로그래머스 lv2 - 두 큐 합 같게 만들기

 

코딩테스트 연습 - 두 큐 합 같게 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

문제의 설명

여기서 2번의 과정을 구현해야겠다고 생각을 했다.

1. 두 큐의 합을 구하면서 비교
2. 비교 후 합의 값이 큰 큐에서 pop(0)하여 다른 큐에 append 해주는 방식을 채택
   1. 해당 과정당 cnt의 증가로 과정을 체크
3. 반환 값의 경우 큐의 합들이 동일하면 cnt 반환, 값이 틀리면 -1 반환
   
   1. 처음 1번의 과정을 진행하기 전 두 개의 큐의 합이 홀수이면 절대 같아질 수 없으므로 바로 -1을 반환하는 코드 추가

 

 

 

 

 코드 작성 및 과정

 

• 초기 작성 코드

def solution(queue1, queue2):
    answer = -1
    cnt =0
    for i in range(len(queue1)+len(queue2)):
        if sum(queue1) > sum(queue2):
            queue2.append(queue1.pop(0))
            cnt+=1
        elif sum(queue1) < sum(queue2):
            queue1.append(queue2.pop(0))
            cnt+=1
        else:
            break
    if sum(queue1) == sum (queue2):
        return cnt
    else:
        return answer

 

for 구문 내에서 지속적인 sum의 호출로 인해 대량의 시간초과 발생 및 테스트 케이스 1번의 실패 발생

 

• sum 메서드를 호출하는 부분을 개선 (대다수의 시간초과 부분 해결)
• 큐의 길이를 좀 더 초과해서 반복문을 돌리면 나아지지 않을까 싶어서 반복문의 횟수를 증가 (테스트케이스 1번 해결) 

def solution(queue1, queue2):
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    cnt = 0
    
    for i in range((len(queue1) + len(queue2)*2)):
        if sum1 > sum2:
            moved_item = queue1.pop(0)
            queue2.append(moved_item)
            sum1 -= moved_item
            sum2 += moved_item
            cnt += 1
        elif sum1 < sum2:
            moved_item = queue2.pop(0)
            queue1.append(moved_item)
            sum1 += moved_item
            sum2 -= moved_item
            cnt += 1
        else:
            break

    if sum1 == sum2:
        return cnt
    else:
        return -1

 

• 초기에 큐의 합을 판별하는 코드 삽입

if (sum1 + sum2)%2==1:
    return -1

 

해당 과정을 통해 코드를 개선해 나갔지만 마지막 테스트 케이스 22,23,24의 경우 통과를 하지 못했다. 질문하기 란을 살펴보았다. 하나의 답변에서 자료구조를 큐를 쓰는 것이 아닌 deque를 사용하는 것을 발견하였고 주어진 queue1,2를 deque로 바꿔서 접근하였다. deque를 사용하여 풀이를 진행하면 시간초과가 해결돼서 통과가 되었다.

from collections import deque
def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    cnt = 0
    
    for i in range((len(queue1) + len(queue2)*2)):
        if sum1 > sum2:
            moved_item = queue1.popleft()
            queue2.append(moved_item)
            sum1 -= moved_item
            sum2 += moved_item
            cnt += 1
        elif sum1 < sum2:
            moved_item = queue2.popleft()
            queue1.append(moved_item)
            sum1 += moved_item
            sum2 -= moved_item
            cnt += 1
        else:
            break

    if sum1 == sum2:
        return cnt
    else:
        return -1

 

• 차이점 
  • 기본적으로 주어지는 queue의 경우 리스트를 사용하여 구현이 되어있다. 
  • list의 경우에서 pop()은 맨 마지막의 원소를 빼는 것이기에 pop(0)를 통해 접근하였다. 이때의 시간복잡도는 O(n)이기에 해당 과정에서 리스트 내부의 데이터가 많아지면 많아질수록 많은 시간이 소모되었다고 볼 수 있다.
  • deque의 경우 링크드 리스트로 구현된 형태이다. 그렇기에 popleft()를 통해 O(1)의 시간복잡도를 가지고 해당 연산을 처리할 수 있게 된다. 그렇기에 해당 과정에서의 시간복잡도가 줄어들어서 문제가 해결이 된 것으로 보인다
• 생각할 점
  • 지금까지 문제를 풀이할 때 우선 구현이 되는지 안되는지만 생각을 하며 문제를 풀었다. 문제를 풀면서 상황에 맞는 자료구조를 쓰는것이 중요하다고 들어오긴 했지만 이번에 경험을 통해 배운 만큼 확 와닿았던 적은 없는 것 같다. 
  • 문제를 풀 때 해당 문제의 풀이코드를 어떻게 구성할까도 중요하지만 풀이 때 사용하는 자료구조를 무엇을 사용할지 생각하는 시간도 필요하다고 생각이 들었다.