23.02.10 파이썬 코딩 퀴즈#146 두 큐 합 같게 만들기 (프로그래머스 스쿨)

이번 문제는 두 큐 합 같게 만들기 문제이다.

전달받은 길이가 같은 두 개의 큐에서 하나의 원소를 추출해 다른 배열에 집어넣는 작업을 통해 두 큐의 합을 같게 만드려고 한다. pop 과 insert 로 정의하며, pop 은 언제나 첫번째 원소를 추출하고, insert 는 마지막 자리에 삽입한다.

위 예시처럼 작업을 진행하게 되는데, 이때 필요한 작업의 최소 횟수를 구해야 한다.

또한 어떤 방법으로도 합을 같게 만들 수 없는 경우라면 -1을 반환하면 된다.

첫번째 작성한 코드이다.

일단 원소의 길이가 30만개 이고, 원소는 10^9 이다... 단순 반복문을 활용하는 것만으로는 시간적으로 무리일 것 같다.

역시나 4번 테케 이후로는 모두 시간초과로 뜬다. 아무래도 while문도 문제가 있어 보이고, 특히 combinations()를 이용한 조합 가능한 경우의 수를 찾는게 시간을 많이 잡아 먹는것 같다.

그렇게 작성한 두 번째 코드,

combinations()는 삭제해 버렸고, 조합 불가 판단 기준을 pop() insert() 실행 후에 처음과 같아지는 경우로 변경 하였다.

하지만 이 역시도 일부 케이스에서 시간 초과 이다. 왜인지 deque 로 풀이해도 조건 범위가 너무 넓어서 해당 방법을 아닌것 같다.

그렇게 만들어진 최종 코드.

1. 전체합 보다는 절반의 합이 더 중요하다.

2. 배열을 하나만 가지고 사용한다.

3. 전체 리스트에서 값을 찾아 연산에 사용한다. i, j 는 각 배열의 index 를 뜻한다.

 

하나의 배열의 합을 가지고 연산을 시작하며, 특별히 배열을 삭제, 삽입이 일어나지 않기 때문에 속도가 굉장히 빠르다. 또한 i 와 j값이 모두 전체 배열의 마지막까지 도달하였고, 현재 합계가 목표 합계과 같지 않을 경우 미리 준비된 answer -1를 반환하여 종료된다.