알고리즘/programmers

[Programmers] 뒤에 있는 큰 수 찾기

꾸준함. 2023. 1. 28. 10:30

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/154539

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

스택 자료구조를 활용하여 풀면 쉽게 풀리는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 우선, answer를 주어진 numbers의 size 크기로 설정하고 모두 -1로 초기화해 줍니다.

2. pair<int, int>형 stack을 선언해 줍니다.

3. 스택이 비어있지 않은 경우 스택의 top에 있는 숫자와 현재 숫자를 비교합니다. 현재 숫자가 더 클 경우 문제에서 주어진 조건인 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 충족하므로 answer[top에 위치한 숫자의 인덱스] = 현재 숫자로 설정해 준 뒤 스택을 pop 합니다.

3.1 스택이 비어있거나 스택의 다음 top의 숫자가 현재 숫자 이상일 경우 조건 미충족이므로 4번 과정으로 넘어갑니다.

4. 스택에 { 현재 숫자, 인덱스 }를 넣어줍니다.

5. 3 ~ 4번 과정을 numbers 내 모든 숫자에 대해 진행해 준 뒤 answer를 반환합니다.


 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형