[Programmers] level2 - 두 큐 합 같게 만들기 (Python) : 2022 카카오 테크 인턴십

▶두 큐 합 같게 만들기 - 2022 카카오 테크 인턴십 (level 2)

▶문제

https://school.programmers.co.kr/learn/courses/30/lessons/118666?language=python3

프로그래머스

• 두 개의 숫자 리스트 (queue) 안의 숫자들 합이 같도록 만들기 (숫자 리스트 (queue) 2개)
• 두 리스트 합이 같도록 만드는데 드는 작업 횟수 반환
• 조건:
  • 작업 1회 = 한쪽 리스트 첫 번째 value를 pop 해서 다른 리스트 마지막 위치에 insert.
  • 두 리스트의 길이는 같다. (이거 모르고 초반에 코드를 이상하게 짰다. #문제를 잘 읽읍시다
  • 합이 같도록 분배가 안되면 -1을 return

 

 

▶제한사항

• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 109
• 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

728x90

▶입출력 예

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

두 큐에 담긴 모든 원소의 합은 20입니다. 따라서, 각 큐의 합을 10으로 만들어야 합니다.

queue2에서 1, 10을 순서대로 추출하여 queue1에 추가하고,

queue1에서 1, 2, 1, 2와 1(queue2으로부터 받은 원소)을 순서대로 추출하여 queue2에 추가합니다.

그 결과 queue1은 [10], queue2는 [1, 2, 1, 2, 1, 2, 1]가 되며, 각 큐의 원소 합은 10으로 같습니다.

이때 작업 횟수는 7회이며, 이보다 적은 횟수로 목표를 달성하는 방법은 없습니다.

따라서 7을 return 합니다.

 

입출력 예 #3

어떤 방법을 쓰더라도 각 큐의 원소 합을 같게 만들 수 없습니다. 따라서 -1을 return 합니다.

 

▶풀이

dqeue를 사용해서 popleft를 사용할 수 있게 queue를 새로 만들었다.

그다음에 for문을 이용해서 sum이 큰 쪽에서 하나씩 빼서 작은 쪽으로 넣어주었다.

 

여기서 한 가지 문제점이 발생하였는데, len(queue1) * 2만큼만 하면 될 거라고 생각했다.

왜냐면 저만큼 반복하고 나면 queue1, queue2가 바뀐 상태가 될 거라고 생각했고,

그 결과 testcase 1이 틀렸다고 나온다. (나머지는 통과)

 

그래서 나는 len(queue1) * 3을 하였고 그때는 정답이 나왔다.

그 부분에 대해서는 아직 해결하지 못했고, 좀 더 생각해봐야 할 거 같다.

from collections import deque

def solution(queue1, queue2):
    answer = 0
    a = deque(queue1)
    b = deque(queue2)
    sum_a = sum(a)
    sum_b = sum(b)
    for i in range(len(queue1) * 3):
        if sum_a == sum_b:
            return i
        elif sum_a > sum_b:
            num = a.popleft()
            b.append(num)
            sum_a -= num
            sum_b += num
        else:
            num = b.popleft()
            a.append(num)
            sum_a += num
            sum_b -= num
        
    return -1

이 문제 역시 효율성이 없기 때문에 간단하게 넘길 수 있는 문제이다.

만약에 효율성 테스트까지 있었다면 조금 더 고민해봐야 할 거 같다.

 

아, 이문제를 풀면서 한번 헤맸는데 for문 안에 sum함수를 사용했다.

sum함수의 시간 복잡도를 생각하지 않고 써서, 시간 초과된 testcase가 존재해서 틀렸다.

 

sum함수를 처음에만 쓰고, for문 안에는 popleft 한 값을 저장해 두고 그 값으로 +-하는 방식을 사용했다.

그렇게 하니까 통과되었다.