[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๊ณผ์ œ ์ง„ํ–‰ํ•˜๊ธฐ(C++)

2023. 6. 29. 18:59ยท๐Ÿ–ฅ๏ธ Study Note/Coding Test

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

๋ฌธ์ œ ์„ค๋ช…

๊ณผ์ œ๋ฅผ ๋ฐ›์€ ๋ฃจ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ˆœ์„œ๋Œ€๋กœ ๊ณผ์ œ๋ฅผ ํ•˜๋ ค๊ณ  ๊ณ„ํš์„ ์„ธ์› ์Šต๋‹ˆ๋‹ค.

  • ๊ณผ์ œ๋Š” ์‹œ์ž‘ํ•˜๊ธฐ๋กœ ํ•œ ์‹œ๊ฐ์ด ๋˜๋ฉด ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.
  • ์ƒˆ๋กœ์šด ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•  ์‹œ๊ฐ์ด ๋˜์—ˆ์„ ๋•Œ, ๊ธฐ์กด์— ์ง„ํ–‰ ์ค‘์ด๋˜ ๊ณผ์ œ๊ฐ€ ์žˆ๋‹ค๋ฉด ์ง„ํ–‰ ์ค‘์ด๋˜ ๊ณผ์ œ๋ฅผ ๋ฉˆ์ถ”๊ณ  ์ƒˆ๋กœ์šด ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.
  • ์ง„ํ–‰์ค‘์ด๋˜ ๊ณผ์ œ๋ฅผ ๋๋ƒˆ์„ ๋•Œ, ์ž ์‹œ ๋ฉˆ์ถ˜ ๊ณผ์ œ๊ฐ€ ์žˆ๋‹ค๋ฉด, ๋ฉˆ์ถฐ๋‘” ๊ณผ์ œ๋ฅผ ์ด์–ด์„œ ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค.
    • ๋งŒ์•ฝ, ๊ณผ์ œ๋ฅผ ๋๋‚ธ ์‹œ๊ฐ์— ์ƒˆ๋กœ ์‹œ์ž‘ํ•ด์•ผ ๋˜๋Š” ๊ณผ์ œ์™€ ์ž ์‹œ ๋ฉˆ์ถฐ๋‘” ๊ณผ์ œ๊ฐ€ ๋ชจ๋‘ ์žˆ๋‹ค๋ฉด, ์ƒˆ๋กœ ์‹œ์ž‘ํ•ด์•ผ ํ•˜๋Š” ๊ณผ์ œ๋ถ€ํ„ฐ ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค.
  • ๋ฉˆ์ถฐ๋‘” ๊ณผ์ œ๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ์ผ ๊ฒฝ์šฐ, ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋ฉˆ์ถ˜ ๊ณผ์ œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

๊ณผ์ œ ๊ณ„ํš์„ ๋‹ด์€ ์ด์ฐจ์› ๋ฌธ์ž์—ด ๋ฐฐ์—ด plans๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๊ณผ์ œ๋ฅผ ๋๋‚ธ ์ˆœ์„œ๋Œ€๋กœ ์ด๋ฆ„์„ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ

  • 3 ≤ plans์˜ ๊ธธ์ด ≤ 1,000
    • plans์˜ ์›์†Œ๋Š” [name, start, playtime]์˜ ๊ตฌ์กฐ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
      • name : ๊ณผ์ œ์˜ ์ด๋ฆ„์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
        • 2 ≤ name์˜ ๊ธธ์ด ≤ 10
        • name์€ ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
        • name์ด ์ค‘๋ณต๋˜๋Š” ์›์†Œ๋Š” ์—†์Šต๋‹ˆ๋‹ค.
      • start : ๊ณผ์ œ์˜ ์‹œ์ž‘ ์‹œ๊ฐ์„ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
        • "hh:mm"์˜ ํ˜•ํƒœ๋กœ "00:00" ~ "23:59" ์‚ฌ์ด์˜ ์‹œ๊ฐ„๊ฐ’๋งŒ ๋“ค์–ด๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.
        • ๋ชจ๋“  ๊ณผ์ œ์˜ ์‹œ์ž‘ ์‹œ๊ฐ์€ ๋‹ฌ๋ผ์„œ ๊ฒน์น  ์ผ์ด ์—†์Šต๋‹ˆ๋‹ค.
        • ๊ณผ์ œ๋Š” "00:00" ... "23:59" ์ˆœ์œผ๋กœ ์‹œ์ž‘ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ฆ‰, ์‹œ์™€ ๋ถ„์˜ ๊ฐ’์ด ์ž‘์„์ˆ˜๋ก ๋” ๋นจ๋ฆฌ ์‹œ์ž‘ํ•œ ๊ณผ์ œ์ž…๋‹ˆ๋‹ค.
      • playtime : ๊ณผ์ œ๋ฅผ ๋งˆ์น˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์˜๋ฏธํ•˜๋ฉฐ, ๋‹จ์œ„๋Š” ๋ถ„์ž…๋‹ˆ๋‹ค.
        • 1 ≤ playtime ≤ 100
        • playtime์€ 0์œผ๋กœ ์‹œ์ž‘ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
      • ๋ฐฐ์—ด์€ ์‹œ๊ฐ„์ˆœ์œผ๋กœ ์ •๋ ฌ๋˜์–ด ์žˆ์ง€ ์•Š์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์ง„ํ–‰์ค‘์ด๋˜ ๊ณผ์ œ๊ฐ€ ๋๋‚˜๋Š” ์‹œ๊ฐ๊ณผ ์ƒˆ๋กœ์šด ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•ด์•ผํ•˜๋Š” ์‹œ๊ฐ์ด ๊ฐ™์€ ๊ฒฝ์šฐ ์ง„ํ–‰์ค‘์ด๋˜ ๊ณผ์ œ๋Š” ๋๋‚œ ๊ฒƒ์œผ๋กœ ํŒ๋‹จํ•ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

plans  result
[["korean", "11:40", "30"], ["english", "12:10", "20"], ["math", "12:30", "40"]] ["korean", "english", "math"]
[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]] ["science", "history", "computer", "music"]
[["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]] ["bbb", "ccc", "aaa"]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

"korean", "english", "math"์ˆœ์œผ๋กœ ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. "korean" ๊ณผ์ œ๋ฅผ "11:40"์— ์‹œ์ž‘ํ•˜์—ฌ 30๋ถ„ ํ›„์ธ "12:10"์— ๋งˆ์น˜๊ณ , ์ฆ‰์‹œ "english" ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. 20๋ถ„ ํ›„์ธ "12:30"์— "english" ๊ณผ์ œ๋ฅผ ๋งˆ์น˜๊ณ , ์ฆ‰์‹œ "math" ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. 40๋ถ„ ํ›„์ธ "01:10"์— "math" ๊ณผ์ œ๋ฅผ ๋งˆ์นฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ "korean", "english", "math" ์ˆœ์œผ๋กœ ๊ณผ์ œ๋ฅผ ๋๋‚ด๋ฏ€๋กœ ์ฐจ๋ก€๋Œ€๋กœ ๋ฐฐ์—ด์— ๋‹ด์•„ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

"music", "computer", "science", "history" ์ˆœ์œผ๋กœ ๊ณผ์ œ๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

์‹œ๊ฐ  ์ง„ํ–‰ ์ค‘ ์ž ์‹œ ๋ฉˆ์ถ˜ ๊ณผ์ œ ์„ค๋ช…
"12:20" "music" [ ] "music"์„ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.
"12:30" "computer" ["music"] "music"์„ ์ž ์‹œ ๋ฉˆ์ถ”๊ณ (๋‚จ์€ ์‹œ๊ฐ„ 30๋ถ„) "computer"๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค
"12:40" "science" ["music", "computer"] "computer"๋ฅผ ์ž ์‹œ ๋ฉˆ์ถ”๊ณ (๋‚จ์€ ์‹œ๊ฐ„ 90๋ถ„) "science"๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค
"13:30" "computer" ["music"] "science"๋ฅผ ๋๋‚ด๊ณ  ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋ฉˆ์ถ˜ "computer"๋ฅผ ๋‹ค์‹œ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค
"14:00" "history" ["music", "computer"] "computer"๋ฅผ ์ž ์‹œ ๋ฉˆ์ถ”๊ณ (๋‚จ์€ ์‹œ๊ฐ„ 60๋ถ„) "history"๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค
"14:30" "computer" ["music"] "history"๋ฅผ ๋๋‚ด๊ณ  ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋ฉˆ์ถ˜ "computer"๋ฅผ ๋‹ค์‹œ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค"
"15:30" "music" [ ] "computer"๋ฅผ ๋๋‚ด๊ณ  ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋ฉˆ์ถ˜ "music"์„ ๋‹ค์‹œ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค"
"16:00" - [ ] "music"์„ ๋๋ƒ…๋‹ˆ๋‹ค

๋”ฐ๋ผ์„œ ["science", "history", "computer", "music"] ์ˆœ์„œ๋กœ ๊ณผ์ œ๋ฅผ ๋งˆ์นฉ๋‹ˆ๋‹ค.

 

๋‚ด ํ’€์ด

์ž ์‹œ ๋ฉˆ์ถฐ๋‘” ๊ณผ์ œ๋Š” ์ตœ๊ทผ์— ๋ฉˆ์ท„๋˜ ๊ณผ์ œ๋ถ€ํ„ฐ ๋‹ค์‹œ ์‹คํ–‰๋˜๊ธฐ ๋•Œ๋ฌธ์— stack์œผ๋กœ ๋ณด๊ด€ํ–ˆ๋‹ค.

๊ฐœ์ธ์ ์œผ๋กœ plans์˜ ์ธ๋ฑ์Šค๋ฅผ ์ดˆ๊ณผํ•˜์—ฌ ์ ‘๊ทผํ•˜์ง€ ์•Š๋„๋ก ์กฐ์‹ฌํ•˜๋ฉด์„œ ์˜ˆ์™ธ์ฒ˜๋ฆฌํ•˜๋Š”๊ฒŒ ์กฐ๊ธˆ ๊นŒ๋‹ค๋กœ์› ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>

using namespace std;

int TimeToInt(string t)
{
    return (60 * stoi(t.substr(0, 2))) + stoi(t.substr(3));
}

bool SortPlans(vector<string> v1, vector<string> v2)
{
    return  TimeToInt(v1[1]) < TimeToInt(v2[1]);
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    stack<pair<string, int>> paused_plans;
    
    sort(plans.begin(), plans.end(), SortPlans);
    
    int cur_time = TimeToInt(plans[0][1]);
    int next_time = TimeToInt(plans[1][1]);
    int cur_subject = 0;
    
    while(cur_subject < plans.size() || !paused_plans.empty())
    {
        // ๋ฉˆ์ถฐ๋’€๋˜ ๊ณผ์ œ ์ฒ˜๋ฆฌ
        if(!paused_plans.empty())
        {   
            // ๋งˆ์ง€๋ง‰ ์ˆœ์„œ ๊ณผ์ œ ์ฒ˜๋ฆฌ๊ฐ€ ๋๋‚ฌ๋‹ค๋ฉด
            if(cur_subject == plans.size())
            {
                answer.emplace_back(paused_plans.top().first);
                paused_plans.pop();
                continue;
            }
            
            // ํ˜„์žฌ ์‹œ๊ฐ„์ด ๋‹ค์Œ ๊ณผ์ œ ์‹คํ–‰ ์‹œ๊ฐ„๋ณด๋‹ค ์ž‘๋‹ค๋ฉด
            if(cur_time < next_time)
            {    
                int remain_time = paused_plans.top().second;
                int available_time = next_time - cur_time;
                
                // ๊ณผ์ œ ์ฒ˜๋ฆฌ ์™„๋ฃŒ
                if(remain_time <= available_time)
                {
                    answer.emplace_back(paused_plans.top().first);
                    paused_plans.pop();
                    cur_time += remain_time;
                }
                 
                // ๊ณผ์ œ ์ฒ˜๋ฆฌ ๋ฏธ์™„๋ฃŒ
                else
                {
                    paused_plans.top().second = remain_time - available_time;
                    cur_time = next_time;
                }
                
                continue;
            }
        }
        
        // ๋‹ค์Œ ๊ณผ์ œ ์ฒ˜๋ฆฌ
        cur_time =  TimeToInt(plans[cur_subject][1]) + stoi(plans[cur_subject][2]);
        next_time = cur_subject+1 >= plans.size() ? 1440 : TimeToInt(plans[cur_subject+1][1]);
        
        if(cur_time > next_time)
        {
            // ๊ณผ์ œ ๋ฉˆ์ถค
            paused_plans.push({plans[cur_subject][0], cur_time - next_time});
            cur_time = next_time;
        }
        else
        {
            // ๊ณผ์ œ ์™„๋ฃŒ
            answer.emplace_back(plans[cur_subject][0]);
        }
        
        ++cur_subject;
    }
    
    return answer;
}

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

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

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - N๊ฐœ์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(C++)  (0) 2023.07.03
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์ ํ”„์™€ ์ˆœ๊ฐ„ ์ด๋™(C++)  (0) 2023.06.30
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์˜ˆ์ƒ ๋Œ€์ง„ํ‘œ(C++)  (0) 2023.06.28
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ๊ด‘๋ฌผ ์บ๊ธฐ(C++)  (0) 2023.06.26
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ํ–‰๋ ฌ์˜ ๊ณฑ์…ˆ(C++)  (0) 2023.06.25
'๐Ÿ–ฅ๏ธ Study Note/Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - N๊ฐœ์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์ ํ”„์™€ ์ˆœ๊ฐ„ ์ด๋™(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์˜ˆ์ƒ ๋Œ€์ง„ํ‘œ(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++)
์ƒ๋‹จ์œผ๋กœ

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