[Day4] goorm level 구름톤 챌린지_완벽한 햄버거 만들기

문제 4. 완벽한 햄버거 만들기

정의

재료 개수를 N, 햄버거의 맛을 res로 정수형 변수로 정의했다. 각 재료의 맛의 정도를 담을 정수형 배열 K를 크기 1000을 주고 정의했다. 마지막으로 가장 높은 재료임을 표시하는 bool 타입 변수 top을 정의했다.

 

고민

테스트케이스에서 애매하게 몇 가지 경우가 에러가 나서 그것 때문에 시간이 오래 걸렸다..두 가지 방식을 생각했었고, 그 중 한 가지 방식으로만 풀어보았다. 첫 번째로 생각한 방식은 K[i]를 입력받을 때 가장 큰 값과 그 때의 인덱스 i를 각각 top, top_index 이런 식으로 저장한 후에 그 가장 큰 값 기준으로 왼쪽 부분 배열과 오른쪽 부분 배열로 쪼개어 각각 오름차순과 내림차순인지를 검사하고 맞으면 정답 출력, 아니라면 0을 출력하는 방식이었다. 이런 방식을 생각하면서 가장 먼저 든 생각은 이렇게 푼다면 풀리긴 하겠지만 더 간단한 방법이 있지 않을까 하는 생각이었고 사실 귀찮은 것도 있었다. 굳이 배열을 쪼개서 두 배열을 만들고 하는 것 보다, K[i]를 입력받는 반복문 안에서 한번에 끝내버리자 하는 생각으로 다시 생각한 방법이 두 번째 방법이다. 사실 이 문제를 보면서 2차 그래프가 생각이 났다. 쭉 상향하다가 한 번 내려오고 그대로 하향하거나 아예 하향하지 않으면 된다. 문제를 헷갈려서 무조건 마지막에는 줄어야 하는 것으로 이해했었는데 그게 아니었다. 가장 높은 재료를 기준으로 위랑 아래로 갈 수록 재료의 맛의 정도가 감소하거나 같아야 한다고 나와있는데 가장 높은 재료가 마지막 재료라면, 감소할 필요가 없다. 

#include <stdio.h>
int main() {
	int N=0;
	int res=0;
	int K[1000];
	int top=0;
	
	scanf("%d", &N);

	for(int i=0; i<N; i++){
		scanf("%d", &K[i]);
		res+=K[i];
		

		
		if(i>0 && K[i-1]-K[i]>0)
			top++;
	}
	
	if(top>1)
		printf("0");
	else
		printf("%d", res);
	
	return 0;
}

가장 먼저 짰던 코드는 이것이었고, 문제가 많았다. 분명 통과하는 테스트케이스가 있었지만 그렇지 않은 케이스도 많았다. for 문 내부 if문을 보면 top은 0으로 시작하여 k[i-1]이 k[i]보다 클 때 즉, 지금 재료가 이전 재료보다 작을 때 하나 증가한다. 이후 for문을 나오면 top이 1보다 큰 경우는 정상적이지 않은 경우로 분류하는데 결론은 하향했을 경우 top을 증가시키는 것이고 1회 초과로 하향했을 경우를 정상적이지 않은 경우로 분류했다. 그런데 한 번 하향하고 나서 다시 상향하는 경우를 찾아야지, 하향하는 경우만 계산한다고 해서 절대 문제가 풀리지 않아야 하는데 이상하게 23개의 테스트케이스 중 꽤 여러 케이스에서 PASS가 떠서 근접한 줄로 알고 본질적인 고민을 하지 않고 런타임, 코드 효율 등에만 신경을 쓰느라 시간을 오래 썼다. 직접 테스트케이스를 만들어서 테스트 하면서 진짜 문제가 무엇인지 알게 되었다. top을 정수가 아닌 bool형 변수로 바꿔서 처음 하향했을 때 true로 변경하고, 조건문을 한 번 더 써서 top이 true일 때(하향을 한 번이라도 한 경우) 상향을 한다면 0을 출력하고 종료시키는 코드로 수정했다. 다 쓰고 나서 반복문에 조건문이 2개 껴 있는 모습을 보니 더 효율적인 방법이 있을 것 같았지만 내 머리로는 생각나지 않아 여기서 멈췄다.

 

풀이

#include <stdio.h>
#include <stdbool.h>
int main() {
	int N, res=0;
	int K[1000];
	bool top= false;
	
	scanf("%d", &N);
	
	for(int i=0; i<N; i++){
		scanf("%d", &K[i]);
		res+=K[i];

		if(i>0 && K[i-1]-K[i]>0)
			top=true;
		
		if(top && K[i-1]-K[i]<0)
		{
			printf("0");
			return 0;
		}
	}
	
	printf("%d", res);
	return 0;
}

C언어

#include <iostream>
using namespace std;
int main() {
	int N, res=0;
	int K[1000];
	bool top= false;
	
	cin >> N;
	
	for(int i=0; i<N; i++){
		cin >> K[i];
		res+=K[i];
		
		if(i>0 && K[i-1]-K[i]>0)
			top=true;
		
		if(top && K[i-1]-K[i]<0)
		{
			cout << 0;
			return 0;
		}
	}
	
	cout << res;
	return 0;
}

C++