[백준] 17298 오큰수
[백준] 17298 오큰수
문제 링크: https://www.acmicpc.net/problem/17298
문제
입출력
문제 접근
stack 문제이다.
현재 숫자보다 오른쪽에 있는 숫자중 크고 가장 왼쪽에 있는 숫자를 찾는 문제이다. stack으로 조건문 몇개만 넣어주면 되는 문제이다.
일단 자신보다 오른쪽에 있는 숫자들을 비교해야되기 때문에, 배열 끝에서 앞으로 가는 방향으로 구현하였다. 현재 배열의 값과 stack에 가장 top에 있는 숫자를 비교한다. 해당 숫자는 뒤에서 부터 넣기 때문에, 자신의 기준에서 가장 왼쪽에 있는 숫자부터 top에서 bottom으로 저장된다. top에 있는 숫자가 자신보다 크다면,해당 숫자를 값을 저장하고, 자신을 stack에 넣어준다.
만약 작다면, 해당 숫자를 stack에서 pop해준다. 어차피 자신보다 작고 오른쪽에 있기 때문에, 앞에 숫자들에 대해 풀 때, 고려대상이 되지 않는다.
라인 인턴 코테에서 stack문제를 못풀고, 반성하기위해 비슷한 문제들을 풀고 있다.
코드 구현(c++)
#include <iostream>
#include <vector>
using namespace std;
int nums[1000001];
int input[1000001];
vector<int> v;
int N;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
int temp;
for(int i = 0 ; i < N ; i++){
cin >> temp;
input[i] = temp;
}
for(int i = N - 1 ; i >= 0 ; i--){
if(i == N-1){
nums[i] = -1;
v.push_back(input[i]);
}
while(v.size()){
if(v.back() > input[i]){
nums[i] = v.back();
break;
}
else v.pop_back();
}
if(v.size() == 0){
nums[i] = -1;
}
v.push_back(input[i]);
}
for(int i = 0 ; i < N ; i++){
cout << nums[i] << " ";
}
cout << "\n";
}
Author And Source
이 문제에 관하여([백준] 17298 오큰수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-17298-오큰수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)