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

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

프로그래머스

 

접근방법

1. 문제 이해하기

 

크기가 같은 두개의 큐가 존재합니다.

하나의 큐에서 추출(POP)하고 그 추출된 수를 다른 큐에 삽입(insert)하는 과정은 1회입니다.

위의 과정을 반복하여 두 큐의 각 원소의 합을 같게 하는 최소의 경우를 구하는 것 입니다.

 

총 원소의 수 합 구하기 => 각 큐의 원소의 합을 절반으로 나눌 수 있으면 됩니다.

 

target을 구했습니다. target은 두 큐의 총원소의 합을 절반으로 나눈 값입니다.

 

그리고 해당 q1 ,q2에서 target이 되려면 필요한 값을 구합니다.

 

 

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    cnt = 0
    answer = -1
    
    max_cnt = len(queue1) + len(queue2)
    target = (sum(q1) + sum(q2)) // 2
    while cnt < max_cnt:
        cnt += 1
        if len(q1) == 0 or len(q2) == 0:
            return -1
        if sum(q1) == target and sum(q2) == target:
            return cnt - 1
        
        # 현재 상태에서 target으로 얼마나 필요한 지 구한다
        need_q1 = target - sum(q1) 
        need_q2 = target - sum(q2) 
        
        if need_q1 > need_q2:
            cur_pop = q2.popleft()
            q1.append(cur_pop)
        else:
            cur_pop = q1.popleft()
            q2.append(cur_pop)
            
    return -1

 

 

시간초과 + corner case에서 에러가 발생하였습니다.

 

그래서 visited_states 를 추가하고 체크하는 코드를 추가하였습니다

 

from collections import deque

def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    cnt = 0
    answer = -1
    
    max_cnt = len(queue1) + len(queue2)
    target = (sum(q1) + sum(q2)) // 2
    
    visited_states = set()
    
    while cnt < max_cnt:
        cnt += 1
        if len(q1) == 0 or len(q2) == 0:
            return -1
        if sum(q1) == target and sum(q2) == target:
            return cnt - 1
        
        # 현재 상태에서 target으로 얼마나 필요한 지 구한다
        need_q1 = target - sum(q1) 
        need_q2 = target - sum(q2) 
        
        if need_q1 > need_q2:
            cur_pop = q2.popleft()
            q1.append(cur_pop)
        else:
            cur_pop = q1.popleft()
            q2.append(cur_pop)
        
        current_state = (tuple(q1), tuple(q2))
        if current_state in visited_states:
            return -1
        visited_states.add(current_state)
            
    return -1

 

여전히 시간초과발생

아예 안되는 경우에 -1을 return 그리고 같은 경우에는 0을 return , 그리고 max_count를 설정

 

코드구현

from collections import deque

def solution(queue1, queue2):
    # q1, q2, 각각의 합 설정
    q1 = deque(queue1)
    q2 = deque(queue2)
    s1 = sum(q1)
    s2 = sum(q2)
    
    # count , max_count 설정
    count , max_count = 0, len(q1) * 3
    
    # s1하고 s2가 같으면 0을 return(바꿀 필요가 없다)
    if s1 == s2:
        return 0
    # 두 수의 합이 홀수이면 똫같은 두 값을 구할 수 없다
    elif (s1 + s2) % 2 == 1:
        return -1
    
    while True:
        if s1 > s2:
            tmp = q1.popleft()
            q2.append(tmp)
            s1 -= tmp
            s2 += tmp
            count += 1
        elif s2 > s1:
            tmp = q2.popleft()
            q1.append(tmp)
            s1 += tmp
            s2 -= tmp
            count += 1
        else:
            break
        
        if count == max_count:
            return -1
        
    return count
            
            
    return -1