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

2022 KAKAO BLIND RECRUITMENT

• Lv 2. 두 큐 합 같게 만들기 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/118667

Code

from collections import deque

def solution(queue1, queue2):
    answer = 0

    q_1 = deque(queue1)
    q_2 = deque(queue2)

    s_1 = sum(queue1)
    s_2 = sum(queue2)

    check_odd = (s_1 + s_2) % 2
    if (check_odd != 0):  # 각 큐가 만들어야 하는 합이 소수인 경우는 불가능
        return -1

    limit = len(queue1) * 3     # 최대 연산 횟수 (시간복잡도를 위한 조건)
    while (s_1 != s_2):
        if (len(q_1) == 0 or len(q_2) == 0):
            return -1
        if(answer >= limit):
            return -1

        if(s_1 > s_2):
            pop_num = q_1.popleft()
            q_2.append(pop_num)

            s_2 += pop_num
            s_1 -= pop_num

            answer += 1
        elif(s_1 < s_2):
            pop_num = q_2.popleft()
            q_1.append(pop_num)

            s_1 += pop_num
            s_2 -= pop_num

            answer += 1

    return answer

풀이 및 해설

• 아이디어 떠올리는 시간보다 시간 초과를 해결하는 시간이 더 길었던 문제 . . . 근데 카카오 기출은 다 이런 느낌이다 뭔가
• 작동 방식 :
  두 큐가 주어졌을 때, 각 큐의 총 합을 계속 비교하면서 둘 중 합이 큰 큐에서 pop → 다른 큐에 append → answer에 1 더해주기
  - 두 큐의 합이 동일해지면 탈출 (while문 조건)
  - 합이 맞춰지지 않아서 더이상 pop할 요소가 없다면 → return -1
  - 최대 연산 횟수를 넘었을때까지 합이 맞춰지지 않는다면 → return -1
• 시간 초과를 막기위해 sum()을 사용하지 않았다.
• ⭐️ 최대 연산 횟수가 큐 길이 * 3인 이유
  • 한 큐에서 맨 끝 요소 1개 빼고 다 pop 되어서 다른 큐에 append 된 다음
    → 다른 큐에서도 맨 끝 요소 1개 빼고 다 pop 되어서 다른 큐에 append 될 때

    해당 과정에서 수행되는 연산 횟수는 `큐 길이 * 3`번 이다.
    
    - ex) 길이가 3인 큐 두개
        1. abc
        def
        2. abcd
        ef
        3. abcde
        f
        4. bcde
        fa
        5. cde
        fab
        6. de
        fabc
        7. e
        fabcd
        8. bc
        defa
        9. c
        defab

  • 참고 : https://school.programmers.co.kr/questions/41370
• ⭐️ deque() 으로 변환해서 popleft()로 원소를 빼주어야한다 !!!!
  • 리스트로 pop()이 아닌 pop(0)을 수행하면 O(n)의 시간복잡도를 가지게 된다.
  • 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)이 나온다.
  • 참고 : https://wellsw.tistory.com/122

What I learned

• 참고한 테스트케이스

  if __name__ == '__main__':
      print(solution([1,4], [4,8]))       # -1
      print(solution([2,4,6], [1,3,5]))   # -1
      print(solution([1,1], [1,5]))       # -1
      print(solution([8,8], [2,8]))       # -1