[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๋‘ ํ ํ•ฉ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๊ธฐ(C++)

2023. 7. 4. 11:25ยท๐Ÿ–ฅ๏ธ Study Note/Coding Test

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

๋ฌธ์ œ ์„ค๋ช…

๊ธธ์ด๊ฐ€ ๊ฐ™์€ ๋‘ ๊ฐœ์˜ ํ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ํ•˜๋‚˜์˜ ํ๋ฅผ ๊ณจ๋ผ ์›์†Œ๋ฅผ ์ถ”์ถœ(pop)ํ•˜๊ณ , ์ถ”์ถœ๋œ ์›์†Œ๋ฅผ ๋‹ค๋ฅธ ํ์— ์ง‘์–ด๋„ฃ๋Š”(insert) ์ž‘์—…์„ ํ†ตํ•ด ๊ฐ ํ์˜ ์›์†Œ ํ•ฉ์ด ๊ฐ™๋„๋ก ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ํ•„์š”ํ•œ ์ž‘์—…์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. ํ•œ ๋ฒˆ์˜ pop๊ณผ ํ•œ ๋ฒˆ์˜ insert๋ฅผ ํ•ฉ์ณ์„œ ์ž‘์—…์„ 1ํšŒ ์ˆ˜ํ–‰ํ•œ ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผํ•ฉ๋‹ˆ๋‹ค.

ํ๋Š” ๋จผ์ € ์ง‘์–ด๋„ฃ์€ ์›์†Œ๊ฐ€ ๋จผ์ € ๋‚˜์˜ค๋Š” ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ์—์„œ๋Š” ํ๋ฅผ ๋ฐฐ์—ด๋กœ ํ‘œํ˜„ํ•˜๋ฉฐ, ์›์†Œ๊ฐ€ ๋ฐฐ์—ด ์•ž์ชฝ์— ์žˆ์„์ˆ˜๋ก ๋จผ์ € ์ง‘์–ด๋„ฃ์€ ์›์†Œ์ž„์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, pop์„ ํ•˜๋ฉด ๋ฐฐ์—ด์˜ ์ฒซ ๋ฒˆ์งธ ์›์†Œ๊ฐ€ ์ถ”์ถœ๋˜๋ฉฐ, insert๋ฅผ ํ•˜๋ฉด ๋ฐฐ์—ด์˜ ๋์— ์›์†Œ๊ฐ€ ์ถ”๊ฐ€๋ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ํ [1, 2, 3, 4]๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, pop์„ ํ•˜๋ฉด ๋งจ ์•ž์— ์žˆ๋Š” ์›์†Œ 1์ด ์ถ”์ถœ๋˜์–ด [2, 3, 4]๊ฐ€ ๋˜๋ฉฐ, ์ด์–ด์„œ 5๋ฅผ insertํ•˜๋ฉด [2, 3, 4, 5]๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

๋‹ค์Œ์€ ๋‘ ํ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์˜ˆ์‹œ์ž…๋‹ˆ๋‹ค.

queue1 = [3, 2, 7, 2] queue2 = [4, 6, 5, 1]

๋‘ ํ์— ๋‹ด๊ธด ๋ชจ๋“  ์›์†Œ์˜ ํ•ฉ์€ 30์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, ๊ฐ ํ์˜ ํ•ฉ์„ 15๋กœ ๋งŒ๋“ค์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ๋‹ค์Œ๊ณผ ๊ฐ™์ด 2๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์Šต๋‹ˆ๋‹ค.

  1. queue2์˜ 4, 6, 5๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ถ”์ถœํ•˜์—ฌ queue1์— ์ถ”๊ฐ€ํ•œ ๋’ค, queue1์˜ 3, 2, 7, 2๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ถ”์ถœํ•˜์—ฌ queue2์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ๊ฒฐ๊ณผ queue1์€ [4, 6, 5], queue2๋Š” [1, 3, 2, 7, 2]๊ฐ€ ๋˜๋ฉฐ, ๊ฐ ํ์˜ ์›์†Œ ํ•ฉ์€ 15๋กœ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ์ž‘์—…์„ 7๋ฒˆ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค.
  2. queue1์—์„œ 3์„ ์ถ”์ถœํ•˜์—ฌ queue2์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  queue2์—์„œ 4๋ฅผ ์ถ”์ถœํ•˜์—ฌ queue1์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ๊ฒฐ๊ณผ queue1์€ [2, 7, 2, 4], queue2๋Š” [6, 5, 1, 3]๊ฐ€ ๋˜๋ฉฐ, ๊ฐ ํ์˜ ์›์†Œ ํ•ฉ์€ 15๋กœ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ์ž‘์—…์„ 2๋ฒˆ๋งŒ ์ˆ˜ํ–‰ํ•˜๋ฉฐ, ์ด๋ณด๋‹ค ์ ์€ ํšŸ์ˆ˜๋กœ ๋ชฉํ‘œ๋ฅผ ๋‹ฌ์„ฑํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ ๊ฐ ํ์˜ ์›์†Œ ํ•ฉ์„ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ž‘์—…์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋Š” 2์ž…๋‹ˆ๋‹ค.

๊ธธ์ด๊ฐ€ ๊ฐ™์€ ๋‘ ๊ฐœ์˜ ํ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ ๋ฐฐ์—ด queue1, queue2๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฐ ํ์˜ ์›์†Œ ํ•ฉ์„ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ž‘์—…์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. ๋‹จ, ์–ด๋–ค ๋ฐฉ๋ฒ•์œผ๋กœ๋„ ๊ฐ ํ์˜ ์›์†Œ ํ•ฉ์„ ๊ฐ™๊ฒŒ ๋งŒ๋“ค ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ, -1์„ return ํ•ด์ฃผ์„ธ์š”.

๋‚ด ํ’€์ด

ํ๋ฅผ ๋งŒ๋“ค์–ด์„œ vector์˜ ๊ฐ’์„ ํ์— ๋„ฃ์–ด์„œ ํ’€์–ด๋„ ๋˜๊ณ ,

๊ทธ๊ฒƒ๋„ ๊ท€์ฐฎ์œผ๋ฉด ํฌ์ธํ„ฐ๋ฅผ ๋งŒ๋“ค์–ด์„œ ํฌ์ธํ„ฐ๋ฅผ ํ•˜๋‚˜์”ฉ ์ด๋™์‹œํ‚ค๋ฉด์„œ,

๋‘ ํ ์ค‘์— ์ด ํ•ฉ์ด ๋” ํฐ ํ์˜ ํฌ์ธํ„ฐ๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ฐ’์„ ์ „๋‹ฌํ•˜๋Š” ์‹์œผ๋กœ ๊ตฌํ˜„ํ•ด๋„ ๋œ๋‹ค.

๋‚˜๋Š” ํฌ์ธํ„ฐ ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•ด๋ดค๋‹ค.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = 0;
    vector<int>::iterator iter1 = queue1.begin(), iter2 = queue2.begin();
    long long total = 0, q1_sum = 0, q2_sum = 0;
    
    for(int i = 0; i < queue1.size(); i++)
    {
        q1_sum += queue1[i];
        q2_sum += queue2[i];
    }
    total = q1_sum + q2_sum;
    
    // ๋‘ ํ์˜ ๋ฐ์ดํ„ฐ ์ด ํ•ฉ์ด ํ™€์ˆ˜๋ฉด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค. 
    if(total % 2 == 1)
    {
        answer = -1;
        return answer;
    }
    
    while(true)
    {
        if(q1_sum == q2_sum)
            break;
        
        // iter ์ค‘ ํ•˜๋‚˜๋ผ๋„ ์ƒ๋Œ€ ํ์˜ ๋์— ๋„๋‹ฌํ–ˆ์„ ๊ฒฝ์šฐ ->  ํƒ์ƒ‰ ์™„๋ฃŒ
        if(iter1 == queue2.end() || iter2 == queue1.end())
        {
            answer = -1;
            break;
        }

        if(q1_sum > q2_sum)
        {
            // q1์—์„œ q2๋กœ ๊ฐ’ ์ „๋‹ฌ
            int data = *iter1;
            q1_sum -= data;
            q2_sum += data;
            
            ++iter1;
            
            // iter1๊ฐ€ queue1 ๋์— ๋„๋‹ฌํ•˜๋ฉด queue2 ์‹œ์ž‘์ ์„ ๊ฐ€๋ฆฌํ‚จ๋‹ค
            if(iter1 == queue1.end())
                iter1 = queue2.begin();
        }
        else
        {
            // q2์—์„œ q1์œผ๋กœ ๊ฐ’ ์ „๋‹ฌ
            int data = *iter2;
            q1_sum += data;
            q2_sum -= data;
            
            ++iter2;
            
            // iter2๊ฐ€ queue2 ๋์— ๋„๋‹ฌํ•˜๋ฉด queue1 ์‹œ์ž‘์ ์„ ๊ฐ€๋ฆฌํ‚จ๋‹ค
            if(iter2 == queue2.end())
                iter2 = queue1.begin();
        }
        
        ++answer;
    }
    
    return answer;
}
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'๐Ÿ–ฅ๏ธ Study Note > Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๋งˆ๋ฒ•์˜ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ(C++)  (0) 2023.07.11
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๋ฐฐ๋‹ฌ(C++)  (0) 2023.07.10
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - N๊ฐœ์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(C++)  (0) 2023.07.03
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์ ํ”„์™€ ์ˆœ๊ฐ„ ์ด๋™(C++)  (0) 2023.06.30
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๊ณผ์ œ ์ง„ํ–‰ํ•˜๊ธฐ(C++)  (0) 2023.06.29
'๐Ÿ–ฅ๏ธ Study Note/Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๋งˆ๋ฒ•์˜ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๋ฐฐ๋‹ฌ(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - N๊ฐœ์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์ ํ”„์™€ ์ˆœ๊ฐ„ ์ด๋™(C++)
Beankong_
Beankong_
์ฃผ๋‹ˆ์–ด ํด๋ผ์ด์–ธํŠธ ํ”„๋กœ๊ทธ๋ž˜๋จธ ๊ณต๋ถ€ ๊ธฐ๋ก
  • Beankong_
    Beankong's Devlog
    Beankong_
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (146)
      • โ›… Daily (0)
      • ๐Ÿ–ฅ๏ธ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • ๐Ÿงญ Devlog (8)
        • ์˜ค๋‹ต๋…ธํŠธ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
Beankong_
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๋‘ ํ ํ•ฉ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๊ธฐ(C++)
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”