Problem

---

문제 설명

1. 최댓값을 기준으로 2개의 배열로 나누고
2. 첫 번째 배열은 오름차순, 두 번째 배열은 내림차순으로 정렬되어 있는지 확인한다.

필요한 함수

	Python	C++	C
최댓값 탐색	var = max( list )	#include < algorithm > int var = *max_element( L, R );
특정 값의 인덱스 찾기	var = list.index( val )	#include < algorithm > int var = max_element( L, R ) - L;
정렬	list.sort() var = sorted( list )	#include < algorithm > sort( L, R );
총합	var = sum( list )	#include < numeric > int var = accumulate( L, R );

Submitted Code

---

Python

N = int(input())
bigger = True
bottom = 0
answer = 0

for top in map(int, input().split()):	
	if not bigger and top > bottom:
		answer = 0
		break
	else:
		if bigger and top < bottom:
			bigger = False
		answer += top
		bottom = top
print(answer)

C++

#include <iostream>
#include <array>          // array
#include <algorithm>      // sort, max_element
#include <numeric>        // accumulate

using namespace std;

bool desc(int a, int b){  // 내림차순으로 정렬하기 위한 사용자 조건
	return a > b;
}

int main() {
	int T;
	cin >> T;
	
    // 배열 입력
	array<int, 1000> arr;
	array<int, 1000> duplicate;
	for (int i = 0; i < T; i++){
		cin >> arr[i];
		duplicate[i] = arr[i];
	}
	
    // 최댓값 인덱스 탐색
	int max_idx = max_element(arr.begin(), arr.begin() + T) - arr.begin();
	
    // 최댓값을 기준으로 오름차순, 내림차순 정렬
	sort(duplicate.begin(), duplicate.begin() + max_idx);
	sort(duplicate.begin() + max_idx + 1, duplicate.begin() + T, desc);
	
    // 원본 배열과 순서 비교
	bool good_hamburger = true;
	for (int i = 0; i < T; i++){
		if (arr[i] != duplicate[i]){
			good_hamburger = false;
			break;
		}
	}
	
    // 순서가 올바르면 총합을, 아니면 0을 출력
	if (good_hamburger)
		cout << accumulate(arr.begin(), arr.begin() + T, 0);
	else
		cout << 0;
	
	return 0;
}

Code Review

---

Python

해설

- 정수 배열이 주어졌을 때, 가장 큰 값을 기준으로 왼쪽과 오른쪽을 분리한다.
- 분리된 왼쪽 배열은 오름차순으로 정렬, 오른쪽 배열은 내림차순으로 정렬한다.
- 분리된 2개의 배열을 합친 뒤, 기존 배열과 동일한 지 비교한다.

만약에 위의 방법에서 2개의 배열이 동일하다면, 이 배열은 완벽한 햄버거라고 할 수 있습니다.
다르다면, 어딘가 문제가 있는 햄버거라는 의미가 됩니다.

해설 시간복잡도 계산

1. 최대값 탐색 - O(n)
2. 배열 분리 - O(n)
3. 정렬 - O(nlogn)
4. 리스트 비교 - O(n)

제출 코드와의 비교

제출 코드가 O(n)으로 빠르긴 하지만, if문 조건이 한 번에 이해될 것 같지 않다.

C++

해설

• 최댓값을 기준으로 첫 번째 배열과 두 번째 배열을 별도로 확인

int ok = 1;

// 앞에 있는 원소들이 오름차순을 만족하는지 확인
for (int i = maxIndex - 1; i > 0; --i) {
    if (K[i] > K[i + 1]) ok = 0;
}

// 뒤에 있는 원소들이 내림차순을 만족하는지 확인
for (int i = maxIndex + 1; i <= N; ++i) {
    if (K[i - 1] < K[i]) ok = 0;
}

1. ios::sync_with_stdio(0); cin.tie(0);

2. for문에서 ++i로 사용

3. 코드 작성 스타일
   - for문이나 if문 내부 코드가 1줄이면 (아래로 내리지 않고) 옆에 이어서 작성
   - 변수명은 Camel case로 작명
      (참고. Google C++ Style Guide에서는
         1) 클래스와 함수는 camelCase
         2) 변수나 클래스의 필드 이름들은 snake_case
         3) enum 필드의 경우 KEBAB_CASE
      로 정의)

4. if-else문은 삼항 연산자로 축약해서 사용

해설 시간복잡도 계산

1. 최대값 탐색 - O(n)
2. 조건 만족 확인 - O(n)

제출 코드와의 비교

Python 코드에서 사용한 방법과 시간복잡도는 O(n)으로 같지만, 해설의 코드가 더 이해하기 쉬워 보인다.

Challenge Review

---

C/C++ 코드는 템플릿, STL를 익히려고 해당 기능을 모두 사용하는 코드로 작성했다.

Reference

---

• 구름톤 챌린지 언어별 문제 해설 - Python, C++