[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋’ค์— ์žˆ๋Š” ํฐ ์ˆ˜ ์ฐพ๊ธฐ - ์Šคํƒ

2024. 8. 20. 15:44ยท๐Ÿ’ป Algorithms/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[ ๋ฌธ์ œ๋งํฌ ]

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

 

๐Ÿšฉ ์กฐ๊ฑด

  1. ์ •์ˆ˜๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฐฐ์—ด numbers
  2. ๋ฐฐ์—ด์˜ ๊ฐ ์›์†Œ๋“ค์— ๋Œ€ํ•ด ์ž์‹ ๋ณด๋‹ค ๋’ค์— ์žˆ๋Š” ์ˆซ์ž ์ค‘์—์„œ ์ž์‹ ๋ณด๋‹ค ํฌ๋ฉด์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์ด ์žˆ๋Š” ์ˆ˜๋ฅผ ๋’ท ํฐ์ˆ˜๋ผ๊ณ  ํ•จ
  3. ๋ชจ๋“  ์›์†Œ์— ๋Œ€ํ•œ ๋’ท ํฐ์ˆ˜๋“ค์„ ์ฐจ๋ก€๋กœ ๋‹ด์€ ๋ฐฐ์—ด์„ returnํ•ด๋ผ. ๋’ท ํฐ์ˆ˜ ์—†์œผ๋ฉด -1 ๋‹ด์•„๋ผ.

 

 

๐Ÿšฉ ์ ‘๊ทผ

์ด๊ฑธ ์Šคํƒ์„ ์ด์šฉํ•ด์„œ ํ’€์–ด์•ผ ํ•œ๋‹ค๋Š” ๊ฑธ ๋– ์˜ฌ๋ฆฌ๊ธฐ๊ฐ€ ์‰ฝ์ง€ ์•Š๋‹ค..

 

 

๐Ÿšฉ ์‹œํ–‰์ฐฉ์˜ค

์ฒ˜์Œ์—๋Š” 2์ค‘ for๋ฌธ์œผ๋กœ ๊ตฌํ˜„ํ–ˆ๋‹ค. ๋‹น์—ฐํ•˜๊ฒŒ๋„ ๋งˆ์ง€๋ง‰ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค 4๊ฐœ์—์„œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค.

 

์‹œ๊ฐ„ ์ดˆ๊ณผ์˜ ์›์ธ์ด ์ด๋ฏธ ์‚ดํŽด๋ดค๋˜ ๊ฑธ ๋ฐ˜์˜์„ ๋ชปํ•˜๊ณ  ๋‹ค์‹œ ๋˜ ์‚ดํŽด๋ณด๊ธฐ ๋•Œ๋ฌธ์ด๋ผ๊ณ  ์ƒ๊ฐํ•ด์„œ ๋ฐฐ์—ด์˜ ๋’ค์—์„œ๋ถ€ํ„ฐ ๋ด์•ผํ•  ๊ฒƒ ๊ฐ™๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค. 

์—ด์‹ฌํžˆ ๊ณ ๋ฏผํ•ด์„œ ๋ญ”๊ฐ€ ๊ทธ๋Ÿด๋“ฏํ•œ ์•„์ด๋””์–ด๋ฅผ ๋– ์˜ฌ๋ ธ๋‹ค. numbers[i]๊ฐ€ numbers[i+1]๋ณด๋‹ค ํฌ๋ฉด answer[i+1]๊ณผ ๋น„๊ตํ•ด์„œ ๊ทธ๊ฒƒ๋ณด๋‹ค๋„ ํฌ๋ฉด -1, ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด numbers[i+1], numbers[i]๊ฐ€ numbers[i+1]๋ณด๋‹ค ์ž‘์œผ๋ฉด numbers[i]๋ฅผ ๋‹ด์ž..

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    for(int i=0; i<numbers.size(); i++){
        answer.push_back(-1);
    }
    
    for(int i=numbers.size()-2; i>=0; i--){
        if(numbers[i]>=numbers[i+1]){
            if(numbers[i]>=answer[i+1]){
                answer[i]=-1;
                for(int j=i+1; j<numbers.size()-1; j++){
                    if(numbers[i]<answer[j]){
                        answer[i]=answer[j];
                        break;
                    }
                }
            }
            else
                answer[i]=answer[i+1];
        }else{
            answer[i]=numbers[i+1];
        }
    }
    
    return answer;
}

์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ํ…Œ์ผ€ 2๊ฐœ๊ฐ€ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ์•„๋งˆ๋„ ์ € ๋‚ด๋ถ€ for๋ฌธ ๋•Œ๋ฌธ์ผ ๊ฒƒ์ด๋‹ค.

 

์‹œ๊ฐ„์ดˆ๊ณผ ์—†์ด ๊ตฌํ˜„ํ•˜๋ ค๋ฉด ์Šคํƒ์„ ํ™œ์šฉํ•ด์•ผ ํ•œ๋‹ค.

for๋ฌธ์„ ํ†ตํ•ด numbers๋ฅผ ๋’ค์—์„œ๋ถ€ํ„ฐ ๊ฑฐ๊พธ๋กœ ํƒ์ƒ‰ํ•˜๋ฉฐ, numbers[i]์— ๋Œ€ํ•ด

  • ์Šคํƒ์ด ๋น„์–ด์žˆ์œผ๋ฉด answer[i]=-1, numbers[i]๋ฅผ ์Šคํƒ์— push
  • ์Šคํƒ์˜ top๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด ์Šคํƒ์˜ top์ด numbers[i]๋ณด๋‹ค ํด๋•Œ๊นŒ์ง€ pop
    • ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ์ˆ˜๊ฐ€ ๋‚˜์˜ค๋ฉด answer[i]=์Šคํƒ์˜ top, numbers[i]๋ฅผ ์Šคํƒ์— push
  • ์Šคํƒ์˜ top๋ณด๋‹ค ์ž‘์œผ๋ฉด answer[i]=์Šคํƒ์˜ top, numbers[i]๋ฅผ ์Šคํƒ์— push

 

 

๐Ÿ’ป ์ฝ”๋“œ (C++)

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    for(int i=0; i<numbers.size(); i++){
        answer.push_back(-1);
    }
    
    stack<int> stack;
    for(int i=numbers.size()-1; i>=0; i--){
        if(stack.empty())
            stack.push(numbers[i]);
        else{
            if(numbers[i]>=stack.top()){
                while(!stack.empty() && numbers[i]>=stack.top()){
                    stack.pop();
                }
                if(!stack.empty()) answer[i] = stack.top();
                stack.push(numbers[i]);
            }   
            else{
                answer[i] = stack.top();
                stack.push(numbers[i]);
            }
        }
    }
    return answer;
}

STL์˜ stack ์ด์šฉํ•˜๋ฉด top(), pop() ์‚ฌ์šฉ ๊ฐ€๋Šฅ

'๐Ÿ’ป Algorithms > ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ตœ๋Œ“๊ฐ’๊ณผ ์ตœ์†Ÿ๊ฐ’ - ๋ฌธ์ž์—ด ์ฒ˜๋ฆฌ?  (1) 2024.09.20
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋‹ฌ๋ฆฌ๊ธฐ ๊ฒฝ์ฃผ - ํ•ด์‹œ  (0) 2024.09.20
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋งˆ๋ฒ•์˜ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ - ์ˆ˜ํ•™  (0) 2024.08.23
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋‘ ์› ์‚ฌ์ด์˜ ์ •์ˆ˜ ์Œ - ์ˆ˜ํ•™  (0) 2024.08.17
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์—ฐ์†๋œ ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ํ•ฉ - ํˆฌ ํฌ์ธํ„ฐ  (0) 2024.08.14
'๐Ÿ’ป Algorithms/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋‹ฌ๋ฆฌ๊ธฐ ๊ฒฝ์ฃผ - ํ•ด์‹œ
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋งˆ๋ฒ•์˜ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ - ์ˆ˜ํ•™
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋‘ ์› ์‚ฌ์ด์˜ ์ •์ˆ˜ ์Œ - ์ˆ˜ํ•™
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์—ฐ์†๋œ ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ํ•ฉ - ํˆฌ ํฌ์ธํ„ฐ
์ ๋„
์ ๋„
  • ์ ๋„
    ๋„์ 
    ์ ๋„
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (30)
      • ๐Ÿ’ป Algorithms (28)
        • ๋ฐฑ์ค€ (22)
        • ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค (6)
      • ๐Ÿ”Ž Deep Learning (0)
      • ๐Ÿ’ฅ ํŠธ๋Ÿฌ๋ธ”์ŠˆํŒ… (1)
      • ๐Ÿ•น Unity (1)
      • ๐Ÿฅ” ์ž‰ํ…… (0)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

    • ํ™ˆ
    • ํƒœ๊ทธ
    • ๋ฐฉ๋ช…๋ก
  • ๋งํฌ

    • Blog
    • Github
    • Velog
  • ๊ณต์ง€์‚ฌํ•ญ

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.0
์ ๋„
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋’ค์— ์žˆ๋Š” ํฐ ์ˆ˜ ์ฐพ๊ธฐ - ์Šคํƒ
์ƒ๋‹จ์œผ๋กœ

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