[프로그래머스] 두 큐 합 같게 만들기 C++ (Lv.2)

 

 

 

 

 

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

프로그래머스

 

이번 문제는 2022 KAKAO TECH INTERNSHIP 문제였습니다.

글쓴이는 투 포인터를 사용하여 풀이했습니다. 🙂

 

 

 

 

 

📝 문제 풀이

1. 두 큐의 모든 원소를 담을 v 벡터 선언

2. v 벡터에서 가리킬 queue1, queue2의 각 시작 지점과 끝 지점 선언 (queue1의 시작 지점: s1, queue1의 끝 지점: e1) 

3. queue1, queue2의 각 모든 원소의 합을 담을 변수는 long long 타입으로 선언 (산술 오버플로우 발생 가능성)

4. sum1과 sum2를 비교하면서 원소를 더하거나 빼 나가기 ⭐️

5. answer <= size*2인 동안에 두 큐의 합이 같으면 answer 반환

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    vector<int> v;
    
    int s1 = 0;
    int e1 = queue1.size() - 1;
    int s2 = queue1.size();
    int e2 = queue1.size()*2 - 1;
    
    int size = queue1.size() * 2;
    long long sum1 = 0, sum2 = 0;
        
    for (int q1: queue1) {
        sum1 += q1;
        v.push_back(q1);
    }
    
    for (int q2: queue2) {
        sum2 += q2;
        v.push_back(q2);
    }

    // 위치가 원래대로 돌아오면 각 큐의 원소 합을 같게 만들 수 없음
    while (answer <= size * 2) {
        if (sum1 < sum2) {
            sum1 += v[(++e1) % size];
            sum2 -= v[(s2++) % size];
        } else if (sum1 > sum2) {
            sum1 -= v[(s1++) % size];
            sum2 += v[(++e2) % size];
        } else return answer; // 두 큐의 합이 같으면 answer 반환
        
        answer++;
    }
    
    return -1;
}

 

프로그래머스 - 결과 화면