프로그래머스 두 큐 합 같게 만들기 by Python

주어진 조건

• 길이가 같은 두 개의 큐
  -> 여기서 큐(queue)란? FIFO(First in First out)의 형태를 가지고 있는 자료구조
  -> 따라서 list 형태를 가진 파이썬의 자료형에서 append 함수를 사용하기는 용이하나 pop 함수를 사용하기는 어려움.
  -> 사용하기 어려운 이유 - pop 함수 또한 마지막 index의 값을 제거하기 때문에

• 각 큐의 합이 같아지게 만들어야 함.

• 왼쪽에서 pop되고, 오른쪽으로 insert되는 형태를 띔.

예시 문제 해결 방식

• 두 큐에 담긴 총합을 먼저 확인함.
• 총합을 확인한 뒤 값을 옮겨서 두 큐의 합을 같아지도록 함.

내가 생각한 문제 해결 방안

• 예시 문제 해결 방식과 같이 두 큐에 담긴 총합을 먼저 구하고자 함.
• 그 후 하나의 list를 만들어주려고 함. 즉, 두 큐를 합침.
• 두 큐를 합친 다음, list에서 가장 큰 수를 탐색한 뒤, 그 숫자를 중심으로 분할할 큐의 size를 키워가면서 문제의 정답에 맞는 큐의 일부분을 탐색하고자 함.

내가 생각한 문제 해결 방안의 문제점

• 일단 단순히 보이는 것만으로도 탐색 시간이 너무 길어 보임. 예를 들어서 1개짜리의 size를 탐색하고, 2개짜리의 size를 탐색하고 하다 보면 최악의 경우 2n-1개까지 size를 탐색해야 할 수도 있음.
• 두 큐를 합친 다음에 어떻게 큐를 나눌지 생각한다면, 적절한 큐를 찾고난 뒤 원본 큐에서 어떻게 그것들을 탐색할지에 대한 방법 또 정해져있지 않으며, 탐색 시간도 많이 걸릴 것으로 예상됨.

타인이 생각한 문제 해결 방식

• 단순하게 말하면 pop과 insert를 한 번씩 하면서 다시 확인해보는 방식
  link : https://dev-dain.tistory.com/228