[2022 kakao tech intership / 프로그래머스] 118667번 : 두 큐 합 같게 만들기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/118667

 

 

부족했던 부분 

1. queue에 deque() 설정 안한 것 (시간초과 발생)

2. sum을 반복문마다 설정한 것 (시간초과 발생)

3. -1이 출력되는 경우에 대해 파악이 잘 되지 않았다 (11번, 28번 테스트에서 틀림)

 

참고한 블로그

 

- 정답 풀이 :

queue의 합만 기록하면 되고, 둘의 합이 같을 때니까 sum(queue1)만 가지고 진행하면 된다. (one == half 일 때, one == two 니까) 

따라서 굳이 queue2 가지고 연산할 필요가 없고, queue1가지고만 진행하면 된다 

from collections import deque
def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    one = sum(queue1)
    half = (one + sum(queue2)) // 2
    
    answer = 0 
    while queue1 and queue2:                       
        if one == half:
            return answer
        if one > half:
            one -= queue1.popleft()
        elif one < half:    
            x = queue2.popleft()
            queue1.append(x)
            one += int(x)
        answer += 1
        
    return -1

 

- 시도한 풀이 1:

63퍼센트에서 틀렸다 

 

틀린 이유

1. queue문제는 무조건 deque() 이용해서 풀어야한다

2. sum은 반복문 바깥에서 한번만 해야한다. 

-> 1, 2번 안 해서 시간초과 오류가 떴다 

def solution(queue1, queue2):    
    count = sum(queue1)* 2 - 1
    half = (sum(queue1) + sum(queue2)) / 2
    
    answer = 0 
    while True:
        one = sum(queue1)
        two = sum(queue2)
        if count == 0 and one != half:
            answer = -1
            break           
        if one == half:
            break
        if one > two:
            queue2.append(queue1.pop(0))
        elif one < two:
             queue1.append(queue2.pop(0))
        count -= 1
        answer += 1
        
    return answer

 

- 시도한 풀이 2 :

위 풀이에서 deque로 바꿔주고 sum을 한번하고 one, two에 연산하는 걸 추가했고, 93.3에서 틀렸다. 테스트 11, 28에서 시간초과가 났다 

정답 풀이와 비교해보면 queue1,2의 합을 이용하는 것과 queue2까지 사용해서 시간초과가 난 것 같기도 하다,,, (사실 잘 모르겠다)

 

예제를 통해서 -1이 출력되는 경우는 2 * half -1 까지 돌았는데도 두 큐의 합이 같지 않은 경우라고 생각해서 

count를 이용했지만 11번, 28번에서 계속 에러가 났다 

from collections import deque
def solution(queue1, queue2):
    queue1, queue2 = deque(queue1), deque(queue2)
    one, two = sum(queue1), sum(queue2)
    count = sum(queue1)* 2 - 1
    half = (sum(queue1) + sum(queue2)) / 2
    
    answer = 0 
    while True:        
        if count == 0 and one != half:
            answer = -1
            break           
        if one == half:
            break
        if one > two:
            x = queue1.popleft()
            two += x
            one -= x
            queue2.append(x)
        elif one < two:
            x = queue2.popleft()
            one += x
            two -= x            
            queue1.append(x)
        count -= 1
        answer += 1
        
    return answer