알고리즘 스터디

Google Kickstart Round C 첫번째 문제인 Record Breaker입니다

총 N일동안 테마파크를 열고, i번째 날짜의 방문자 수는 Vi입니다.

Record breaking은 이전의 방문자 최대치보다 크고, 그 다음날 보다 방문자가 많아야 합니다.

여기서 Record breaking 날짜 수를 구하는 문제입니다.

 

C++를 사용한 제 풀이입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stack>

using namespace std;

int n;

void solve() {
	cin >> n;
	int result = 0, t = -1;
	vector<int> a(n, 0);

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

	for (int i = 0; i < n; ++i) {
		if (t < a[i] && (i + 1 == n || a[i] > a[i + 1])) 
			++result;
		if (t < a[i])
			t = a[i];
	}

	cout << result << "\n";
	return;
}

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

	int t;
	cin >> t;
	for (int i = 1; i <= t; ++i) {
		cout << "Case #" << i << ": ";
		solve();
	}
}

간단하게 과거의 최대치를 t에 계속 저장하고, 다음날보다 많으면 result를 증가하는 식으로 풀었습니다.

사실 영어 해석을 잘못해서 한 30분 날리고, Limits를 제대로 안봐서 t=0으로 시작했더니 WA가 자꾸 떠서

또 30분정도 날렸네요.. 1시간 좀 넘게 걸린 것 같네요 ㅠ