[노씨데브 킬링캠프] 2주차 - 문제풀이: 두 큐 합 같게 만들기

과거 기록 (과거에 100/100)

'''
아
전체합 / 2 가 각 배열이 가져야하는 전체합임
전체합보다 크면 큰배열에서 빼서 작은배열로 넣음
어떤 경우에도 원소합이 같아질수 없는 경우는 전체합이 홀수인 경우
또는 절반한 것보다 더 큰 원소가 있는 경우

문제 -> 계속해서 합을 계산해야함, 시간복잡도?

for q1 길이 + q2 길이
    q1 합 + q2 합 -> 전체합 구하기
전체합/2 -> 각 q가 가져야될 합

while cnt <= q1길이+q2길이 && q1합 != q2합
    if q1 합 < 전체합/2:
        q1 에서 1개 pop & q2 에 insert
        q1합 뺀 원소만큼 --
    elif q1 합 > 전체합/2:
        q2 에서 1개 pop & q1 에 insert
        q2합 뺀 원소만큼 --

if cnt > q1길이+q2길이:
    print(-1)
else:
    print(cnt)
    
    
시
못해도 각 모든 원소를 한번씩은 옮겨봐야함
O(n) = 300,000 << 2억

자
q1 sum : int
q2 sum : int
target sum : int
cnt : int
'''
import collections

def solution(queue1, queue2):
    q1 = collections.deque(queue1)
    q2 = collections.deque(queue2)
    q1_sum = 0
    q2_sum = 0
    t_sum = 0
    cnt = 0
    
    q1_sum,q2_sum = sum(q1), sum(q2)
    if (q1_sum + q2_sum)%2:
        return -1
        
    t_sum = (q1_sum + q2_sum)//2
    
    queue3 = queue1 + queue2
    for i in range(len(queue3)):
        if t_sum < queue3[i]:
            return -1
    
    while cnt <= 2+len(q1)+len(q2) and q1_sum != q2_sum:
        if q1_sum > t_sum:
            a = q1.popleft()
            q2.append(a)
            cnt += 1
            q1_sum -= a
            q2_sum += a
        elif q1_sum < t_sum:
            a = q2.popleft()
            q1.append(a)
            cnt += 1
            q1_sum += a
            q2_sum -= a
    
    if cnt > 2+len(queue3):
        return -1
    
    return cnt

접근 방법 [필수 작성]

문제 조건 확인

• 길이가 같은 두 개의 큐
• 뽑고 넣고를 통해 두 큐 합이 같게 만들기
• 작업의 최소 횟수 구하기 → return
• pop+insert 쌍이 작업 1회
• 가능하게 하는 방법은 여러개일 수 있으나, 최소횟수를 찾는게 관건

(가능한 방법이 최대 2개일까? 그 이상일까?) → 풀이 끝나고 생각

제한 조건 확인

• 원소갯수가 30만개 인게 2개 → 60만 → O(n^2) 으로 풀면 안됨
• 파이썬이라 원소 크기는 신경쓸 필요가 없다.

(C++ 이나 자바 라면?) → 문제 끝나고 생각

아이디어

첫번째 아이디어

두 큐 전체 합 구한 후 절반값보다 큰큐에서 뽑아서 작은 큐에 넣고

다시 절반값과 비교해서 어디에서 뽑을지 결정

사실상 하나의 큐라고 봐도 무방

즉, 1번에서 먼저 뽑든 2번에서 먼저 뽑든 뭐에서 먼저 뽑든 순서가 뒤죽박죽될 일이 없음

[코너케이스]

절반 밑이라도 먼저 뽑아야하는 경우가 있는가?

→ 순서가 뒤죽박줄 될일이 없기 때문에 먼저 뽑아야할 필요가 없음

가능한 케이스가 없는 것은 어떻게 검증할 것인가?

→ 한쪽에서 다 뽑혀서 아무것도 없을 때는 만들 수 없는 경우임

→ 한쪽에서 모든 숫자를 다 빼는 경우는 없음. 즉, 양 길이의 합보다 많이 뺐다 넣었다 하는 경우는 없음

두번째 아이디어

사실상 하나의 큐라고 봐도 무방 → 이 아이디어에 착안

그래서 그냥 두 큐 중 하나의 큐는 반드시 이 안의 범위에 존재하게 되어있음. 그래서 투포인터로 풀이가능

투포인터를 시작위치와 끝위치로 정의해서 그 사이 값들을 합 했을때 절반과 같으면 그게 정답임.

초기 설정을 queue1 에 두고,

queue1 값이 target 보다 작으면 끝 포인터를 옮겨주고,

queue1 값이 target 보다 크면, 시작 포인터를 옮겨준다.

이때, 끝포인터가 전체 길이를 넘어서거나 (반대쪽 큐가 길이가 0)

작은 포인터가 끝포인터를 지나가면 (현재 큐가 길이가 0)

가능한 경우가 없는 것이고,

포인터가 한번 움직일때마다 count 가 1 증가한다.

시간복잡도

최대 2n

자료구조

코드 구현 [필수 작성]

1차 시도 → 시간초과

무언가 내가 알지 못하는 코너케이스가 있어서 무한루프를 도는 것 같다.

#1시 시작 -> 

from collections import deque
def solution(queue1, queue2):
    deque1 = deque(queue1)
    deque2 = deque(queue2)
    
    total_sum = sum(deque1) + sum(deque2)
    total_len = len(deque1) + len(deque2)
    count = 0
    
    #정수배열이기때문에 target 이 float 이면 만들 수가 없다
    if total_sum%2 == 1: 
        return -1
    
    target = total_sum//2
    #print(target)
    # while deque1:
    #     deque1.popleft()
    # print(bool(deque1))
    
    while deque1 and deque2:
        if count >= total_len:
            return -1
        if sum(deque1) == target:
            return count
        if sum(deque1) > target:
            curr = deque1.popleft()
            deque2.append(curr)
            count += 1
        elif sum(deque2) > target:
            curr = deque2.popleft()
            deque1.append(curr)
            count += 1
    
    #여기까지오면 두큐 중 한큐가 비어있는 상태
    return -1

2차 시도 → 투포인터로 구현 → 런타임 에러

어디선가 index out of range error 가 나는 것으로 추정

end += 1
curr_sum += total_deque[end]

end += 1 을 하고 나서 end index 를 참조해서 out of range

from collections import deque
def solution(queue1, queue2):
    total_queue = queue1+queue2
    total_deque = deque(total_queue)
    total_sum = sum(total_deque)
    target = total_sum//2
    count = 0
    start = 0
    end = len(queue1)-1
    curr_sum = 0
    
    if total_sum%2 == 1:
        return -1
    
    for i in range(start,end+1):
        curr_sum += total_deque[i]
    
    while start <= end and end < len(total_deque):
        if curr_sum > target:
            curr_sum -= total_deque[start]
            start += 1
            count += 1
        elif curr_sum < target:
            end += 1
            curr_sum += total_deque[end]
            count += 1
        else: #curr_sum == target
            return count
        
    return -1

3차 시도 → 100/100

from collections import deque
def solution(queue1, queue2):
    total_queue = queue1+queue2
    total_deque = deque(total_queue)
    total_sum = sum(total_deque)
    target = total_sum//2
    count = 0
    start = 0
    end = len(queue1)-1
    curr_sum = sum(queue1)
    
    if total_sum%2 == 1:
        return -1
    
    while start <= end and end < len(total_deque):
        #print(start,end)
        if start == 0 and end == len(total_deque)-1:
            return -1
        if curr_sum == target:
            return count
        elif curr_sum > target:
            curr_sum -= total_deque[start]
            start += 1
            count += 1
        elif curr_sum < target:
            end += 1
            if end >= len(total_deque):
                return -1
            curr_sum += total_deque[end]
            count += 1
#11번 28번 런타임 에러
    return -1

최종 최적화 코드

from collections import deque
def solution(queue1, queue2):
    total_queue = queue1+queue2
    total_deque = deque(total_queue)
    total_sum = sum(total_deque)
    target = total_sum//2
    count = 0
    start = 0
    end = len(queue1)-1
    curr_sum = sum(queue1)
    
    if total_sum%2 == 1:
        return -1
    
    while start <= end and end < len(total_deque)-1:
        if curr_sum == target:
            return count
        elif curr_sum > target:
            curr_sum -= total_deque[start]
            start += 1
            count += 1
        elif curr_sum < target:
            end += 1
            curr_sum += total_deque[end]
            count += 1
    
    if curr_sum == target:
        return count
        
    return -1

배우게 된 점 [ 필수 X ]

런타임 에러 해결법

알고리즘의 런타임 에러의 대부분은 index 참조와 관련해서 일어나는 것임. 따라서 index가 변화된 이후에 참조되는 부분을 집중적으로 조사하면 런타임 에러를 잡아낼 수 있을 것임.

질문 [ 필수 X ]

Q1 (자체해결)

아래 코드는 맨처음 데큐를 통한 구현을 할 때 작성했던 코드입니다.

그런데, while 문의 조건들을 뜯어보면,

제가 생각했을때는, 모든 조건을 탐색하게 만들었고, return 을 적절히 사용했기 때문에 무한루프에 빠질 가능성이 없는 반복문이라고 생각하는데 결과는 계속해서 시간초과가 나는 상황입니다. while 문을 주석처리했을때, 시간초과가 나지 않는걸로 보아서, while 문 때문에 시간초과가 나는것이 명확한데, while 문의 구조를 아무리 쳐다보아도 무한루프에 빠질 가능성이 있다고 생각되지 않습니다. 지피티에 물어보면 이상한 바보같은 답변만 주네요.

앗! → while 문 때문에 시간초과가 나는게 아닌, sum 함수때문에 시간초과가 나는 거였네요. sum 함수가 O(n) 의 시간복잡도를 가지는데,

while 문이 최대 4n번 반복되기 때문에 시간복잡도가 n^2 이 되는군요.

[기존코드]

from collections import deque
def solution(queue1, queue2):
    deque1 = deque(queue1)
    deque2 = deque(queue2)
    
    total_sum = sum(deque1) + sum(deque2)
    total_len = len(deque1) + len(deque2)
    count = 0
    
    #정수배열이기때문에 target 이 float 이면 만들 수가 없다
    if total_sum%2 == 1: 
        return -1
    
    target = total_sum//2
    #print(target)
    # while deque1:
    #     deque1.popleft()
    # print(bool(deque1))
    
    while deque1 and deque2:
        if count >= total_len:
            return -1
        if sum(deque1) == target:
            return count
        elif sum(deque1) > target:
            curr = deque1.popleft()
            deque2.append(curr)
            count += 1
        elif sum(deque1) < target:
            curr = deque2.popleft()
            deque1.append(curr)
            count += 1
    
    #여기까지오면 두큐 중 한큐가 비어있는 상태
    return -1

[수정코드]

#1시 시작 -> 

from collections import deque
def solution(queue1, queue2):
    deque1 = deque(queue1)
    deque2 = deque(queue2)

    total_len = len(deque1) + len(deque2)
    deque1_sum = sum(deque1)
    deque2_sum = sum(deque2)
    total_sum = deque1_sum + deque2_sum
    count = 0
    
    #정수배열이기때문에 target 이 float 이면 만들 수가 없다
    if total_sum%2 == 1: 
        return -1
    
    target = total_sum//2
    #print(target)
    # while deque1:
    #     deque1.popleft()
    # print(bool(deque1))
    
    while deque1 and deque2:
        if count > 4*total_len:
            return -1
        if deque1_sum == target:
            return count
        if deque1_sum > target:
            curr = deque1.popleft()
            deque1_sum -= curr
            deque2.append(curr)
            deque2_sum += curr
            count += 1
        elif deque1_sum < target:
            curr = deque2.popleft()
            deque2_sum -= curr
            deque1.append(curr)
            deque1_sum += curr
            count += 1
    
    #여기까지오면 두큐 중 한큐가 비어있는 상태
    return -1

Q2

항상 어려운 것이 샘플테스트케이스를 통과해도 실제테스트케이스에서 다 틀려서 완솔인줄 알았는데 부분점수밖에 못가져가서 코테 떨어지는 경우가 허다하다. 그래서 반드시 샘플테스크케이스를 다 통과하더라도 최종 제출 누르기전에 한번씩 더 생각하고 내는데도 불구하고 항상 다 통과를 못한다. 혹시 이런 경우에 대해서 코치님은 내가 완솔할 거라는것을 어떻게 검증하고 갈 수 있는지 사용하는 팁이 있으면 조언해주시면 감사드리겠습니다.

Q3

curr → (curr) 와 같이 양쪽 괄호를 감싸는 sublime 단축키가 있는지 궁금합니다. google 검색과 gpt 를 활용해 검색해봐도 있다고 하는건 써봐도 안되고, 지피티는 있다했다 없다했다 해서 진짜 없는건지 잘 모르겠습니다.

또 그 외 코드 작성시 코치님이 자주 쓰시는 단축키 팁이 있다면 추천해주시면 감사드리겠습니다. 저는 ctrl+d 를 활용하여 변수명을 바꿔야할때 한번에 바꾸거나 검색하는데 용이하게 사용하는 것 외엔 활용하는게 없는것 같습니다.

Q4

프로그래머스 환경에서 컴파일 에러가 아닌 런타임 에러날 때 print 등을 활용하거나 그 외에 디버깅 하는 방법이 궁금합니다. IDE 활용이 안되는 상황에서는 break point 를 걸어주는 디버깅이 불가능해서, 변수값 print 나 try-except 를 활용한 예외처리 사용도 어려운데, 코드가 너무 복잡하고 길어졌을때, 단순히 눈으로 보는 것 말고, 출력등을 통한 런타임에러를 잡는 방법이 있는지 궁금합니다.

프로그래머스 환경에서는 서버에서 코드 돌릴때 solution.py 밑에 있는 solution 함수를 찾아서 자동으로 돌리는 것으로 파악되어 아래와 같이 try-catch 문을 구성해보는 방향으로 런타임에러를 잡을 수 없을까 생각해보았는데, 더 생각해보니, 어떤 변수에서 에러가 발생했는지 특정해서 넘겨줄 수가 없으니, 결국, 그냥 solution 함수를 활용했을때랑 결국 똑같은 것 같습니다.

from collections import deque
def solution(queue1, queue2):
    try:
        return sol(queue1,queue2)
    except:
        print(f"An error occurred: {e}")

def sol(queue1, queue2):
    total_queue = queue1+queue2
    total_deque = deque(total_queue)
    total_sum = sum(total_deque)
    target = total_sum//2
    count = 0
    start = 0
    end = len(queue1)-1
    curr_sum = 0
    
    if total_sum%2 == 1:
        return -1
    
    for i in range(start,end+1):
        curr_sum += total_deque[i]
    
    while start <= end and end < len(total_deque):
        if curr_sum > target:
            curr_sum -= total_deque[start]
            start += 1
            count += 1
        elif curr_sum < target:
            end += 1
            curr_sum += total_deque[end]
            count += 1
        else: #curr_sum == target
            return count
        
    return -1

Q5

내 코드 100/100 정답 코드인데 반례가 있습니다.

q1 = [5, 1]

q2 = [1, 3]

return = 3

아래 코드 결과값 = -1

실제 예상 결과값 = 3

반례를 건의하는 방법이 있나요? 찾아보니 그냥 질문란에 올리는 방법이 다 인것 같아서 우선은 그냥 질문란에 올려놓은 상황입니다.

https://school.programmers.co.kr/questions/70758

from collections import deque
def solution(queue1, queue2):
    total_queue = queue1+queue2
    total_deque = deque(total_queue)
    total_sum = sum(total_deque)
    target = total_sum//2
    count = 0
    start = 0
    end = len(queue1)-1
    curr_sum = sum(queue1)
    
    if total_sum%2 == 1:
        return -1
    
    while start <= end and end < len(total_deque)-1:
        if curr_sum == target:
            return count
        elif curr_sum > target:
            curr_sum -= total_deque[start]
            start += 1
            count += 1
        elif curr_sum < target:
            end += 1
            curr_sum += total_deque[end]
            count += 1
        
    return -1

피드백 [ 코치 작성 ]

A1

말씀하신 것과 같이 sum 함수를 매 반복마다 수행하게 되어 시간 초과가 발생한 것입니다.

A2

경험밖에는 답이 없는 것 같습니다. 비슷한 문제 유형을 풀어보며 다양한 예외 케이스들을 접해야 해당 문제에서도 어떤 예외 케이스들이 발생할 수 있는지를 생각할 수 있습니다. 팁이라고 하기엔 애매하지만 코드를 테스트 해볼 때 악의적인 테스트 케이스들을 추가해 테스트 하는 것 또한 테스트에 도움이 될 것입니다.

A3

드래그, 더블클릭 또는 shift + 방향키를 통해 단어를 선택한 후 괄호를 입력하면 됩니다.
저의 경우 사용하는 단축기는 별로 없으며 그나마 자주 사용하는 단축키는 command+/ 로 한번에 주석처리를 하는 단축키입니다.

A4

저의 경우 눈으로 확인하기 어려워 디버깅을 해야할 경우 오류가 발생한 것으로 추정되는 부분을 주석처리하여 오류의 발생 여부를 파악하고 이를 통해 오류의 위치를 특정한 후 디버깅을 통해 해결합니다. 이 때 일반적으로 디버깅을 하는 경우 런타임 에러로 인해 print가 제대로 출력되지 않으니 반복문의 경우 반복 횟수를 제한해 출력하거나 오류의 위치를 더욱 세부적으로 특정해 해당 코드에서 발생 가능한 문제점들을 파악하여 해결합니다.

A5

사실상 작성하신 코드가 잘못된 것으로 우연히 제출시 테스트 케이스에 반례로 올려주신 것과 같은 케이스가 존재하지 않아 통과한 것으로 보입니다. 해당 코드의 문제점은 2차시도에서 겪으신 index out of range를 잘못 해결함으로써 발생한 문제입니다.

2차 시도에서 겪으신 것과 같이 end+=1 이후 total_deque[end]로 접근하는 과정에서 index out of range오류가 발생한 것입니다. 하지만 이를 반복문 조건에서 len(total_deque)-1을 통해 해결한다면 curr_sum += total_deque[end]를 통해 curr_sum이 수정이 된 후 while문의 조건을 벗어나 실질적인 탐색을 하지 못하기에 모든 가능성을 탐색할 수 없습니다. 해당 문제를 더욱 정확하게 수정하기 위해서는 반복문의 조건은 고정한 상태에서 end가 인덱스를 초과할 경우를 예외처리를 하거나 반복문의 조건을 수정하되 curr_sum이 수정된 이후에 target과 비교함을 통해 해결할 수 있습니다.