[구름톤 챌린지 1주 차 학습 일기] 4일차 미션 문제 4. 완벽한 햄버거 만들기 (java)

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

구름LEVEL

---

728x90

 

내 생각

정해코드를 보니까 ArrayList로 받아서 가장 큰 수를 기준으로 배열을 쪼개고 왼쪽은 오름차순 정렬, 오른쪽은 내림차순 정렬 후 배열을 다시 합치고 기존에 입력 받은 ArrayList와 순서가 똑같은지 확인한다.

하지만 최대값 찾는 시간(n) + 좌측 리스트와 우측 리스트 생성 시간 + Collections.sort(nlogn) + 새로운 리스트 또 생성 후 합치기 + 리스트 비교(n) 으로 시간 복잡도는 훨씬 안좋아보인다.

---

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		// 재료 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = arr[0]; // 답 
		boolean isForward = true; // 증가하는 중이면 true
		for(int i = 1; i < N; i++) {
			if(isForward) { // 전 재료까지 계속 증가 중이었다면
				if(arr[i - 1] > arr[i]) { // 이번에 감소하면
					isForward = false;
				}
			} else { // 전 재료가 감소 중이었다면
				if(arr[i - 1] < arr[i]) { // 다시 증가하면 안됨
					result = 0;
					break;
				}
			}
			result += arr[i]; // 이번 재료의 맛의 정도 더 해줌.
		}
		
		System.out.println(result);
	}
}