[프로그래머스 코딩 테스트] 두 큐 합 같게 만들기 - KAKAO TECH INTERNSHIP

두 큐 합 같게 만들기

문제 설명

귀찮으니 간단하게만 설명하자면...  두 개의 숫자 리스트가 들어오는데, 그 숫자 리스트들의 각 합이 동일할 때까지 리스트 왼쪽 끝에서 pop, 오른쪽 끝에서 insert 하는 코드를 작성하고 최소 횟수가 몇 번인지 출력하면 된다.문제점은 몇 번을 반복한다 해도 두 큐의 합이 동일해질 리 없는 조건들도 고려해야 하고, 시간 제한이 있는 문제기 때문에 코드를 정말 몇 번 고쳤는지 모르겠다.... 덕분에 Big-O(빅오)에 대해 한 번 더 공부할 수 있어서 좋았다.

 

---

 

문제 풀이

내가 작성한 코드 1

from collections import deque

def solution(queue1, queue2):
    answer = 0
    nums_list = queue1 + queue2
    q1 = deque(queue1)
    q2 = deque(queue2)
    if max(nums_list) > (sum(nums_list)//2) or sum(nums_list)%2 == 1:
        return -1
    while sum(q1) != sum(q2):
        if sum(q1) > sum(q2):
            q2.insert(-1, q1[0])
            q1.pop()
            answer += 1
        else:
            q1.insert(-1, q2[0])
            q2.pop()
            answer += 1
    return answer

가장 먼저 deque를 사용하지 않고 list의 pop, insert를 사용해서 해 봤는데, 이 방식은 아마 문제를 받자마자 가장 많이들 떠올릴 방법일 것 같다. 당연히 list 형태 그대로의 방식을 사용하면 O(n)의 시간이 들어서 시간 초과로 문제 풀이를 넘어서지 못한다.

그래서 찾아보니 deque를 사용하면 pop와 insert 형식들이 O(1)의 시간만 든다는 것을 알아내어 위의 코드를 작성해 실행해 봤더니, 테스트 케이스는 전부 통과했지만 최종 제출에서 수많은 시간 초과를 마주하게 된다.

deque로 바꿨는데도 왜 시간 초과가 떴을까 싶어 또 찾아보니 sum이랑 max 함수 또한 O(n)의 시간이 걸린다는 걸 알게 되었다.  그래서 초반에 변수로 저장해 두고 사용해 보기로 했다.

 

내가 작성한 코드 2

from collections import deque

def solution(queue1, queue2):
    answer = 0
    nums_list = max(queue1 + queue2)
    first1 = deque(queue1)
    count = 0
    q1 = deque(queue1)
    q2 = deque(queue2)
    sum_q1 = sum(q1)
    sum_q2 = sum(q2)
    if nums_list > ((sum_q1 + sum_q2)//2) or (sum_q1 + sum_q2)%2 == 1:
        return -1
    while sum_q1 != sum_q2:
        if sum_q1 > sum_q2:
            q2.append(q1[0])
            sum_q2 += q1[0]
            sum_q1 -= q1[0]
            q1.popleft()
            answer += 1
        else:
            q1.append(q2[0])
            sum_q1 += q2[0]
            sum_q2 -= q2[0]
            q2.popleft()
            answer += 1
        if q1 == first1:
            count += 1
        if count == 1:
            return -1
    return answer

시간 복잡도가 높은 sum과 max를 변수에 저장하고 매번 sum을 하는 대신 그 변수에 값을 더하고 빼고는 방식으로 바꿨다. 하지만 그럼에도 최종 제출 때 두 개의 케이스에 시간 초과가 떠서 고민해 본 결과, if문에서 거르지 못한, 아무리 pop, insert를 한다고 해도 값이 같아지지 않는 경우가 존재할 것 같다는 생각에 반복하다 다시 원래의 리스트로 돌아오는 경우에 -1을 return 해 주는 코드를 추가했더니 이젠 딱 한 개의 케이스만이 시간 초과가 뜬다....

이 방식 말고 다른 방식으로 해당 경우를 걸러낼 수 있는 방식을 생각해 봐야 할 것 같다.

 

내가 작성한 코드 3

from collections import deque
import time

def solution(queue1, queue2):
    answer = 0
    nums_list = max(queue1 + queue2)
    q1 = deque(queue1)
    q2 = deque(queue2)
    sum_q1 = sum(q1)
    sum_q2 = sum(q2)
    if nums_list > ((sum_q1 + sum_q2)//2) or (sum_q1 + sum_q2)%2 == 1:
        return -1
    first_time = time.time()
    while sum_q1 != sum_q2:
        if sum_q1 > sum_q2:
            q2.append(q1[0])
            sum_q2 += q1[0]
            sum_q1 -= q1[0]
            q1.popleft()
            answer += 1
        else:
            q1.append(q2[0])
            sum_q1 += q2[0]
            sum_q2 -= q2[0]
            q2.popleft()
            answer += 1
        now_time = time.time()
        if now_time - first_time > 1:
            return -1
    return answer

결국 끝까지 같아질 수 없는 두 큐를 무한 교환하는 문제를 소요 시간 단위로 잘라내어 정리하는 방식을 썼더니 통과할 수 있었다. 코드가 좀 긴 것 같지만... 다른 사람들의 풀이를 보니까 줄여서 쓸 수 있다고 해도 시간 복잡도에 큰 영향이 안 가는 것 같기도 하고, 발상의 전환보다는 시간 복잡도가 큰 목표인 것 같아서 여기서 마무리.

 

---

 

 

이 문제를 통해 배울 수 있었던 점

1.  List 내의 함수들은 O(n)이라는 시간 복잡도를 가진다.

sum, max와 같은 함수들은 list 내 모든 수를 훑어야 하므로 O(n)의 시간 복잡도를 가진다.

 

2. deque 내의 함수들은 대체로 O(1)이라는 시간 복잡도를 가진다.

 

 

시간 복잡도 표 출처: https://wellsw.tistory.com/122