2022 카카오인턴십:[Two pointer] 두 큐의 합 같게만들기

문제

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

프로그래머스

풀이

제약조건

• q1,q2 길이 ≤ 30만
  • O(n^2)의 알고리즘은 시간 초과임을 의미
  • O(10^8) 이하의 알고리즘 채택 필요
    • → O(nlogn),O(n)
• q1,q2 의 원소 ≤ 10^9
  • int자료형은 일반적으로 2^31 = 2*10^9 까지 표현 가능 (int: 4byte)
  • q1,q2의 요소가 int임을 의미

문제유형

• 투포인터 + 그리디
  • 큐는 눈속임 →큐를 합쳐서 투 포인터 로 접근
  • 두 큐 각각의 합을 고려하지 말고 하나의 큐의 합만을 초점에 맞춰 생각
  • 그리디: 각 큐의 합을 target을 중심으로 비교해서 pop,insert를 해주는 로직만으로 최소 해가 구해짐.

코드

        

          

            

            

            

          
          
PYTHON
          
        
      def solution(queue1, queue2):
    q = queue1 + queue2
    target = sum(q) // 2

    i, j = 0, len(queue1)-1
    curr = sum(queue1) # 초기 합 
    count = 0

    while i < len(q) and j < len(q):        
        if curr == target:
            return count

        elif curr < target and j < len(q)-1:
            j += 1
            curr += q[j]  # j포인터를 먼저 증가 시키고 값을 추가해야함
 
        else: # i,j포인터가 while 탈출 조건을 이곳에서 만족( 꼭 else로 분기처리해주기 )
            curr -= q[i]  # i포인터의 값을 먼저 빼고 포인터를 증가시켜야함
            i += 1

        count += 1

    return -1