[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ํƒ๋ฐฐ ์ƒ์ž(C++)

2023. 6. 19. 13:57ยท๐Ÿ–ฅ๏ธ Study Note/Coding Test

๋ฌธ์ œ

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

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr

์ฒซ๋ฒˆ์งธ ํ’€์ด

์ฒซ๋ฒˆ์งธ๋Š” ๊ทธ๋ฆฌ๋””๋กœ ํ’€์—ˆ๋Š”๋ฐ vector.erase()๋ฅผ ๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ์‚ฌ์šฉํ•ด์•ผ ํ•ด์„œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚ฌ๋‹ค.

list๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ erase ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ค„์ธ๋‹ค๊ณ  ํ•ด๋„, list๋Š” index๋ฅผ ์ด์šฉํ•œ ๋žœ๋ค ์•ก์„ธ์Šค๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ฝ”๋“œ๊ฐ€ ๋ณต์žกํ•ด์ง€๊ณ  ์›ํ•˜๋Š” ์ธ๋ฑ์Šค์— ์ ‘๊ทผํ•˜๊ธฐ๊นŒ์ง€ ์‹œ๊ฐ„์ด ์˜ค๋ž˜๊ฑธ๋ฆฐ๋‹ค.

๊ฒŒ๋‹ค๊ฐ€ ์ƒ๊ฐํ•˜๊ธฐ๋„ ํž˜๋“  ํ’€์ด์ด๋‹ค.

ํ‹€๋ฆฐ ํ’€์ด์ด๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ„๋‹จํ•˜๊ฒŒ๋งŒ ์„ค๋ช…ํ•˜๋ฉด,

ํ˜„์žฌ ๋ฐ•์Šค๊ฐ€ ์ˆœ์„œ์— ๋งž๋Š” ๋ฐ•์Šค๋ผ๋ฉด boxs์—์„œ ์‚ญ์ œํ•œ๋‹ค. ์•„๋‹ˆ๋ผ๋ฉด ๋‹ค์Œ ๋ฐ•์Šค๋ฅผ ๊ฐ€๋ฆฌํ‚จ๋‹ค.

๋งŒ์•ฝ ์ด์ „ ๋ฐ•์Šค๊ฐ€ ๋‹ค์Œ ์ˆœ์„œ์˜ ๋ฐ•์Šค๋ผ๋ฉด ์ด์ „ ๋ฐ•์Šค๋ฅผ ๊ฐ€๋ฆฌํ‚จ๋‹ค.

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    vector<int> boxs(order);
    sort(boxs.begin(), boxs.end());

    int box_idx = order[0]-1;
    int order_idx = 0;

    while (!boxs.empty())
    {
        if (box_idx == boxs.size())
            break;

        if (boxs[box_idx] == order[order_idx])
        {
            boxs.erase(boxs.begin() + box_idx);
            ++order_idx;
            ++answer;
        }
        else
            ++box_idx;

        if (box_idx - 1 >= 0 && boxs[box_idx - 1] == order[order_idx])
        {
            --box_idx;
        }
    }

    return answer;
}

๋‘๋ฒˆ์งธ ํ’€์ด

๋‘๋ฒˆ์งธ ํ’€์ด๋Š” ์Šคํƒ์„ ์ด์šฉํ–ˆ๋‹ค.

sub ์ปจ๋ฒ ์ด์–ด๋ฅผ stack์œผ๋กœ ์„ค์ •ํ•˜๊ณ , ๋ฐ•์Šค๋ฅผ ํ•˜๋‚˜์”ฉ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ์— ๋„ฃ๋Š”๋‹ค.

๋งŒ์•ฝ ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋„ฃ์€ ๋ฐ•์Šค๊ฐ€ ํ˜„์žฌ ์ˆœ์„œ์— ๋งž๋Š” ๋ฐ•์Šค๋ผ๋ฉด ์ปจ๋ฒ ์ด์–ด์—์„œ ๊บผ๋‚ด๊ณ  ๋‹ค์Œ ์ˆœ์„œ์˜ ๋ฐ•์Šค๋ฅผ ์ฐพ๋Š”๋‹ค.

๋งŒ์•ฝ ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋„ฃ์€ ๋ฐ•์Šค์— ์ˆœ์„œ์— ๋งž์ง€ ์•Š๋Š” ๋ฐ•์Šค๋ผ๋ฉด ์ปจ๋ฒ ์ด์–ด ๋ฐธํŠธ์— ๋ฐ•์Šค๋ฅผ ๋„ฃ๊ณ  ํ˜„์žฌ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•œ๋‹ค.

#include <vector>
#include <stack>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    stack<int> sub;

    // ์ฒซ๋ฒˆ์งธ ๋ฐ•์Šค ๋„ฃ๊ธฐ
    int num = 1;
    sub.push(num);

    for (int i = 0; i < order.size(); ++i)
    {
        // sub ์ปจํ…Œ์ด๋„ˆ์˜ ๊ฐ€์žฅ ๋‚˜์ค‘์— ๋“ค์–ด์˜จ ๋ฐ•์Šค๊ฐ€ ์ˆœ์„œ์— ๋งž๋Š” ๋ฐ•์Šค๋ผ๋ฉด
        if (!sub.empty() && sub.top() == order[i])
        {
            // ์ปจํ…Œ์ด๋„ˆ์—์„œ ๋ฐ•์Šค ๋นผ๊ธฐ
            sub.pop();
            // ์ •๋‹ต ๊ฐœ์ˆ˜ ์ถ”๊ฐ€
            ++answer;
        }

        // ์ˆœ์„œ์— ๋งž๋Š” ๋ฐ•์Šค๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด
        else
        {
            // ๋ฐ•์Šค์˜ ์ˆ˜ ์ดˆ๊ณผ์‹œ ๋” ์ด์ƒ ์ปจํ…Œ์ด๋„ˆ์— ๋ฐ•์Šค ์ถ”๊ฐ€ ์•ˆํ•œ๋‹ค
            if (num >= order.size()) break;

            // ์ปจํ…Œ์ด๋„ˆ์— ๋ฐ•์Šค ์ถ”๊ฐ€
            ++num;
            sub.push(num);

            // ๋ฐ•์Šค ์ˆœ์„œ ์œ ์ง€
            --i;
        }
    }

    return answer;
}

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

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

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

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