백준 17298번 오큰수 / 인덱스와 값의 비교 유의해야

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int resarr[1000000];
stack <int> st;

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> resarr[i];
	vector <int> vec(N, -1);
	for (int i = 0; i < N;i++)
	{
		while (!st.empty() && resarr[st.top()] < resarr[i])
		{
			vec[st.top()] = resarr[i];
			st.pop();
		}
		st.push(i);
	}
	for (int i = 0; i < N; i++)
		cout << vec[i] << " ";
	cout << "\n";
	
}

굳이 벡터를 써야 했나? 싶은 코드 

-1로 초기화하는 것은 중요함 

vector < int> vec(N, -1)은 vec을 N칸 만큼을 확보하고 -1로 초기화한다는 뜻 

 

stack에는 index를 넣는다. 인덱스를 차례대로 넣으면서 가장 위에 있는 것이 먼저 인덱스 값이 바뀌도록 한다. 

현재 i가 위치해 있는 값보다 stack에서 아직 초기화되지 못한 가장 최근 인덱스의 값이 더 작다면 

이는 첫번째 조건인 가장 왼쪽의 가장 큰 수를 찾은 것이므로 

vec의 알맞는 인덱스 위치에 현재 i가 위치한 값으로 초기화하고 

그 스택에서 방금 비교한 인덱스는 pop시켜 치우도록 한다. 

 

 

예를 들어 5 2 7 일 경우이며 5 와 2 의 인덱스가 스택에 있는 상태일때 

현재 인덱스가 7을 가리키고 있고 스택의 가장 위엔 2의 인덱스가 있다. 

2는 7보다 작으므로 while조건에 해당해 vec의 2 위치는 7로 초기화되고 2의 인덱스는 아웃!

계속 while문을 돌려 5는 7보다 작으므로 vec의 5 위치는 7로 초기화되고 5의 인덱스는 아웃!

그러면 스택에는 아무것도 없는 empty 상태이므로 while문을 빠져나간다. 

따라서 7 7 그리고 초기화되지못한 -1이 이어져  7 7 -1이 답이다.  

 

만약 3 5 2 7 일 경우이고 3이 스택에 있는 상태일때 

현재 인덱스는 5를 가리키고 스택 가장 위에 3이 있다. 

3은 5보다 작으므로 while조건에 해당, vec의 3 위치는 5로 초기화되고 3의 인덱스 아웃! 

스택은 엠티이므로 아까 5 2 7 을 반복 

이번에 프린트하면 

5 7 7 -1 이 프린트된다. 

 

다음예를 들어보면 9 5 4 8 이 있다. 

9 5 4 8 의 경우 스택에는 차례대로 9, 5, 4의 인덱스가 들어간다. 왜냐하면 현재 인덱스가 스택의 가장 위에 있는 인덱스를 초기화시키지 못했기 때문. (9 > 5 ) ( 5 > 4)

현재 인덱스가 8을 가리키게 되면 8은 스택의 가장 위에 있는 4보다 크다. 따라서 4의 인덱스는 8로 초기화되고 4 아웃

스택의 가장 위는 이제 5를 가리킨다. 5 역시 8이 더 크므로 5의 인덱스는 8로 초기화 5 아웃

스택의 가장 위는 마지막으로 9를 가리킨다. 9는 8보다 크지 못하므로 초기화되지 못하고 -1로 유지된다. 

whie문의 '<'조건을 충족못해 빠져나가자 인덱스를 다 돌았으므로 끝 

이를 프린트하면 -1 8 8 -1 로 초기화되지 못한 인덱스는 -1로 그대로 잘 나옴을 확인할 수 있다. 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<map>

using namespace std;


int N;
stack<pair<int,int>> s;		//값, index
int answer[1000001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	//answer초기화
	for (int n = 0; n < N; n++) answer[n] = -1;
	int tmp;
	for (int n = 0; n < N; n++) {
		cin >> tmp;
		while (!s.empty() && s.top().first < tmp)
        {
			answer[s.top().second] = tmp;
			s.pop();
		}
		s.push({ tmp,n });
	}
	for (int i = 0; i < N; i++) {
		cout << answer[i] << " ";
	}
}

 다른 사람의 좋은 코드