[2023-01-18]

Start

Flags 문제

 

flag를 들고 산에 가서 peak에 flag를 꽂을건데 flag와 flag간에는 distance는 flag의 개수보다 크거나 같아야한다.

그래서 최고로 많이 들고 갈 수 있는 flag는 몇 개인 것인가..? 하는 부분인데..

 

flag를 적당히 들고가야지 안그러면 오히려 가지고 간 것보다 더 적게 꽂고 올 수 있고

flag를 조금 들고 가면 더 꽂을 수 있는데 더 못 꽂고 올 수 있다..

 

최대 입력값이 400,000이라서 peak는 단일 for문으로 찾을 수 있을 것 같다.

 

문제는 flag인데 peak는 400,000일 경우 최악의 경우 199,999개가 나오고 약 200,000개라고 쳤을 때 flag의 개수를 구하기 위해 이중 for문을 돌릴 경우 400억 가까이..? 나올 것 같다..

 

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        int size = A.length;
        boolean isPeak = false;
        Map<Integer, Integer> map= new HashMap<>();
        for(int i = 0; i < size-1; i++) {
            if (isPeak) {
                if (A[i] > A[i+1]) {
                    map.put(i, A[i]);
                    isPeak = false;
                }
            } else {
                if (A[i] < A[i+1]) {
                    isPeak = true;
                }
            }
        }
        
        
        for(int i = 1, m_size = map.size(); i <= m_size; i++) {
            
        }

        return 0;
    }
}