문제

바이토닉 수열이란 수열이 증가했다가 감소하는 수열을 의미합니다.
예를 들어 1, 2, 3, 2, 1과 같이 증가했다가 감소하면 바이토닉 수열이라고 합니다.
하지만 1, 2, 3, 4, 5와 같이 증가만 하거나, 5, 4, 3, 2, 1처럼 감소만 하면 바이토닉 수열이라 하지않습니다.
또 1, 2, 2, 3, 2, 1처럼 같은 값이 이웃해도 바이토닉 수열이라 하지 않습니다.
매개변수 nums에 길이가 n인 수열이 주어지면 이 수열의 연속부분수열 중 가장 긴 바이토닉 수열을 찾아 그 길이를 반환하는 프로그램을 작성하세요.
만약 [1, 3, 2, 5, 7, 4, 2, 5, 1]수열이 주어지면 이 수열의 연속부분수열 중 가장 긴 바이토닉 수열은 [2, 5, 7, 4, 2]이고, 답은 5입니다.

입출력 예:

nums	answer
[1, 3, 2, 5, 7, 4, 2, 5, 1]	5
[1, 1, 2, 3, 5, 7, 4, 3, 1, 2]	8
[3, 2, 1, 3, 2, 4, 6, 7, 3, 1]	6
[1, 3, 1, 2, 1, 5, 3, 2, 1, 1]	5

제한사항:
• nums의 길이 3 <= n <= 10,000
• 배열 nums의 원소는 자연수입니다.

접근 방법

증가, 감소 flag를 각각 둬서 계산한다.

1. 이전 값 보다 현재 값이 클 때
   감소 flag가 false면 증가 flag를 true로 변경한다.
   감소 flag가 true면 현재 수열을 기록하고, 다시 각 flag를 false로 리셋시킨다.
   여기서 리셋은 현재 값이 더 크기 때문에 리셋하더라도 길이는 2로 시작한다.

2. 이전 값 보다 현재 값이 작을 때
   증가 flag가 true면 감소 flag를 true로 변경한다.
   증가 flag가 false면 각 flag를 false로 리셋시킨다.

3. 값이 같을 때
   무조건 각 flag를 false로 리셋시킨다.

풀이

class Solution {
    public int solution(int[] nums){
        int answer = 1;

        boolean incFlag = false;
        boolean decFlag = false;

        List<Integer> answerList = new ArrayList<>();

        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] < nums[i]) {
                //감소 flag가 false면 answer 증가 및 incFlag 변경
                if (!decFlag) {
                    incFlag = true;
                    answer++;
                }
                //감소 flag가 true라면 flag reset / 현재 값이 더 크기 때문에 길이는 2
                else {
                    incFlag = true;
                    decFlag = false;
                    answerList.add(answer);
                    answer = 2;
                }

            } else if (nums[i-1] > nums[i]) {
                //증가 flag가 true면 answer 증가 및 decFlag 변경
                if(incFlag) {
                    decFlag = true;
                    answer++;
                }
                //증가 flag가 false면 flag reset / 현재 값이 더 작기 때문에 길이는 1
                else {
                    incFlag = false;
                    decFlag = false;
                    answerList.add(answer);
                    answer = 1;
                }
            }
            // 값 같아도 리셋
            else {
                incFlag = false;
                decFlag = false;
                answerList.add(answer);
                answer = 1;
            }

            //마지막 인덱스라면 무조건 리스트에 기록
            if (i == nums.length - 1) {
                answerList.add(answer);
            }
        }

        return Collections.max(answerList);
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{1, 3, 2, 5, 7, 4, 2, 5, 1}));
        System.out.println(T.solution(new int[]{1, 1, 2, 3, 5, 7, 4, 3, 1, 2}));
        System.out.println(T.solution(new int[]{3, 2, 1, 3, 2, 4, 6, 7, 3, 1}));
        System.out.println(T.solution(new int[]{1, 3, 1, 2, 1, 5, 3, 2, 1, 1}));
        System.out.println(T.solution(new int[]{1, 2, 1, 2, 3, 2, 1}));
    }
}

다른 풀이

봉우리가 될 수 있는 지점의 인덱스를 저장해서 각 인덱스로부터 수열을 구하는 방식

class Solution {
    public int solution(int[] nums){
        int answer = 1;

        List<Integer> list = new ArrayList<>();
        // 봉우리가 될 수 있는 지점 찾기
        for (int i = 1; i < nums.length-1; i++) {
            if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) {
                list.add(i);
            }
        }

        // 봉우리의 길이 구하기
        for (Integer idx : list) {
            int len = 1;
            int incIdx = idx;
            int decIdx = idx;

            while (incIdx < nums.length-1) {
                if (nums[incIdx] > nums[incIdx+1]) {
                    len++;
                    incIdx++;
                } else {
                    break;
                }
            }

            while (decIdx > 0) {
                if (nums[decIdx] > nums[decIdx-1]) {
                    len++;
                    decIdx--;
                } else {
                    break;
                }
            }

            if (len > answer) answer = len;
        }

        return answer;
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{1, 3, 2, 5, 7, 4, 2, 5, 1}));
        System.out.println(T.solution(new int[]{1, 1, 2, 3, 5, 7, 4, 3, 1, 2}));
        System.out.println(T.solution(new int[]{3, 2, 1, 3, 2, 4, 6, 7, 3, 1}));
        System.out.println(T.solution(new int[]{1, 3, 1, 2, 1, 5, 3, 2, 1, 1}));
        System.out.println(T.solution(new int[]{1, 2, 1, 2, 3, 2, 1}));
    }
}