C# 뒤에 있는 큰 수 찾기 - Stack / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/154539

 

 

나의 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] numbers) 
    {
        // 스택에 넣으면서 top보다 큰 수가 온 경우 pop을 반복하고, 현재 숫자를 pop된 index에 넣어준다.
        int[] answer = new int[numbers.Length];
        var stack = new Stack<Item>();
        for(int i = 0; i < numbers.Length; ++i)
        {
            while(stack.Count > 0 && numbers[i] > stack.Peek().value)
            {
                Item top = stack.Pop();
                answer[top.index] = numbers[i];
            }
            
            stack.Push(new Item(i, numbers[i]));
        }
        
        // 남은 item들은 자신보다 큰 수가 뒤에 오지 않는다.
        while(stack.Count > 0)
        {
            Item top = stack.Pop();
            answer[top.index] = - 1;
        }
        
        return answer;
    }
    
    public class Item
    {
        public int index;
        public int value;
        
        public Item(int index, int value)
        {
            this.index = index;
            this.value = value;
        }
    }
}

'뒤에 있는 숫자' 라는 말이 나오자마 스택문제구나 싶었다.

2레벨 치고 푸는데 3분도안걸린듯. 

 

다른사람 코드

public class Solution {
    public int[] solution(int[] numbers) 
    {
        int[] answer = new int[numbers.Length];
        var s = new System.Collections.Generic.Stack<int>();
        for (int i = 0; i < numbers.Length; i++) 
        {
            int n = numbers[i];
            answer[i] = -1;
            while (s.Count > 0) 
            {
                if (numbers[s.Peek()] < n) 
                {
                    answer[s.Peek()] = n;
                    s.Pop();
                }
                else 
                {
                    break;
                }
            }
            s.Push(i);
        }
        return answer;
    }
}

스택에 숫자를 넣는게 아니라 index를 넣어서 풀었기 때문에 별도로 구조체나 클래스를 만들 필요가 없었다.

참고할만한 풀이법.