python 코딩테스트 - 2022 카카오 인턴 기출 2번

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

프로그래머스

 

처음 든 생각

- 대놓고 큐 쓰라고 줬고 popleft랑 append를 쓰면 되겠다. 이 함수들은 시간복잡도 O(1)이니깐

- 서로 대소 비교를 하면서 큰 놈에서 작은 놈으로 하나씩 옮겨가주면서 같은지 아닌지 계속 확인하면 되겠다.

 

나의 답

from collections import deque
def solution(queue1, queue2):
    q1 = deque(queue1)
    q2 = deque(queue2)
    s1 = sum(q1)
    s2 = sum(q2)
    if (s1 + s2) % 2 == 1:
        return -1
    
    for i in range(4 * len(q1)):    
        if s1 == s2:
            return i
        elif s1 > s2:
            tmp = q1.popleft()
            s1 -= tmp
            q2.append(tmp)
            s2 += tmp
        else:
            tmp = q2.popleft()
            s2 -= tmp
            q1.append(tmp)
            s1 += tmp
          
    return -1

 

 

먼저 deque을 불러와서 큐로 만들어준 다음, 처음 합을 구해준다.

 

만약 두 큐의 합이 홀수일 경우 반으로 나누면 소수가 되므로 절대 합을 같게 할 수 없어 -1을 리턴한다.

 

그 다음 반복문이 핵심인데 (여기서 틀렸었다)

전체 길이의 하나의 큐의 길이의 4배 만큼 반복문을 설정한다.

이렇게 하는 이유는 먼저 시간 복잡도를 O(n^2)을 넘어가지 않게 하기 위함이고 그렇다면 반복문의 최대횟수는 큐의 값들이 서로의 큐를 방문하고 다시 돌아오는 데까지 4n번이기 때문이다. 아래 그림을 보면 이해가 빠르다.

그 다음 반복문을 range로 돌게 된다. 원소가 pop, append가 되면 i는 자동으로 1씩 증가하기 때문에 굳이 다른 변수를 선언하지 않고 바로 처리가 가능하고 처음에 같은 답이 나와도 0으로 바로 처리가 가능할 수 있게 range를 사용하였다.

 

반복문을 돌면서 대소 비교를 하고 큰 놈은 popleft 후 합에서 그 크기만큼 감소하고 작은 놈은 append 하고 그 크기만큼 증가시키면 된다.

 

반복문을 다 돌았는데 답이 없으면 -1을 리턴한다.

---

이 문제는 단순한 큐 문제인 것 같았지만 의외의 난관 + 새로 배울 점이 많았던 문제였다.

 

1. sum의 시간 복잡도는 O(n)이다. 

처음에 이 문제를 풀 때 반복문 안에서 합을 계속해서 또 계산하는 과정을 위해 sum을 활용했다. 하지만 시간 초과가 났었는데 그 이유는 알고보면 간단했다. 반복문을 도는데 그 안에서 O(n)인 함수가 또 실행되니 결국 O(n^2)형태였던 것이다. 문제의 조건에 나와있다시피 큐의 최대 길이는 300,000인데 O(n^2)가 되게 되면 10억회의 연산을 하므로 시간초과가 날 수 밖에 없었다. 원소의 개수가 크게 변동이 없을 때는 처음 합에서 단순 연산을 통해서 값을 계산해주는 것이 시간 복잡도 측면에서 훨씬 이득이다. 

 

2.  반복문을 쓸 때 최대 범위를 알면 for문을 쓰자

이 문제를 처음 풀 때 while로 반복문을 구성했다. 전체의 절반 만큼 해당하는 합을 될 때까지 while문을 도는 방식이었다. 물론 이 방식이 틀린 건 아니지만 시간 복잡도에서 확신을 가지기 어려웠다. 최대 동작 횟수를 위와 같이 파악할 수 있는 문제에서는 반복문의 제약조건을 확실하게 걸어야 시간 복잡도가 훨씬 잘 보이고 더 나아가 for 문을 사용하기 때문에 인덱스나 값을 활용하기에 훨씬 용이했다.