구름톤 챌린지 1주 차 학습 일기 - 4

구름톤 챌린지란?

구름 이라는 곳에서 문제 풀이 챌린지(구름톤 챌린지)를 한다고 해서 참여 중이다. 이벤트 기간 동안 문제가 꾸준이 올라오며, 주에 2회씩 (혹은 그 이상) 챌린지 문제들에 대해 풀이가 가능한 문제들을 풀이해보고, 후기를 남겨보려고 한다.

• 문제 푸는 곳: https://level.goorm.io/l/challenge/goormthon-challenge
• 학습 일기 작성 가이드: https://goorm.notion.site/5ad9e8eef00f4c19b083572c2000d7f8
• 풀이 사용 컨테이너(구름 컨테이너): https://goor.me/8jsC9vbx5TCeaCcRA

문제 풀이

• 문제 제목: 완벽한 햄버거 만들기
• 문제 링크: https://level.goorm.io/exam/195686/%EC%99%84%EB%B2%BD%ED%95%9C-%ED%96%84%EB%B2%84%EA%B1%B0-%EB%A7%8C%EB%93%A4%EA%B8%B0/quiz/1

풀이 접근

이 문제의 경우 사람이 완벽한 햄버거 를 판정한다면 어떻게 할 수 있을지 생각해보면 쉽다. 우선, 최대값을 찾는다. 그리고, 최대값 좌/우측으로 그 값보다 같거나 작은 값이 계속해서 나와야 한다는 사실을 관찰할 수 있다.

즉, 투 포인터 를 사용하는 느낌으로 풀면 되는 문제이며, 시간복잡도는 $O(N)$이 된다. 아직 Python이 익숙하지 않기 때문에 이 문제는 기존처럼 C++로 풀이해보았다.

샘플 정답 코드

#include <bits/stdc++.h>
using namespace std;
int main() {
	int N; scanf("%d", &N);
	vector<int> A;
	int maxval = 0;
	int maxpos = -1;
	int sum = 0;
	for(int i = 0; i < N; ++i) {
		int tmp; scanf("%d", &tmp);
		A.push_back(tmp);
		sum += tmp;
		if (tmp > maxval) {
			maxpos = i;
			maxval = tmp;
		}
	}
	bool flag = true;
	for(int i = maxpos; i >= 1; --i) {
		if (A[i - 1] <= A[i]) continue;
		flag = false;
	}
	for(int i = maxpos; i < N - 1; ++i) {
		if (A[i] >= A[i + 1]) continue;
		flag = false;
	}
	if (flag) {
		printf("%d\n", sum);
	} else {
		printf("0\n");
	}
	return 0;
}