[알고리즘][스택] 17608번 막대기 | baekjoon 문제 풀이

https://www.acmicpc.net/problem/17608

17608번: 막대기

 

 

 

 

풀이

배열로도 풀고 스택으로도 풀었다. 풀이 방법 자체는 유사하고, 단순하게 비교하여 값을 갱신해주는 문제였다!

 

[배열]

#include <iostream>
using namespace std;

int arr[100000];

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int count = 1;
	int maxLength = arr[N - 1];

	for (int i = N - 2; i >= 0; i--) { // 배열 뒷 순서부터 가야함! / arr[N-1]은 제외.
		if (arr[i] > maxLength) {
			maxLength = arr[i];
			count++;
		}
	}
	cout << count;
}

 

 

[스택]

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

stack<int> st;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int s;
		cin >> s;
		st.push(s);
	}

	int count = 1;
	int maxLength = st.top();
	st.pop();

	for (int i = 0; i < (N - 1); i++) {
		if (st.top() > maxLength) {
			maxLength = st.top();
			count++;
		}
		st.pop();
	}
	cout << count;
}

 

배열이 조금 더 빨랐다