백준 2491 자바 - 수열 (BOJ 2491 JAVA)

문제 : boj2491

 

 

1.

  연속해서 커지는 경우(같은 것 포함)만 일단 생각해보자. 주어지는 N개의 숫자에 대해서, 숫자가 작아진 경우 카운팅을 1로 되돌려보자. 그럼 다음과 같이 증가(같은 것 포함)하는 경우에 대해 각 구간에서 얼마나 긴 길이를 가지는지 알 수 있다.

  

2.

  그럼 감소하는 경우도 마찬가지다. 값이 이전보다 커지는 경우 카운팅을 1로 되돌리면서 계속 세어나가면 된다. 이 문제의 경우엔 커지거나, 작아지는 수열 중 답을 구해야한다. 하지만 다를건 없다 그냥 하나씩 입력받으면서 증가하는 경우의 카운팅과, 감소하는 경우의 카운팅을 따로따로 해주면 된다. 한번에 세지 못하고 따로따로 세줘야 하는 이유는, 모든 수가 동일한 구간이 포함된 경우 (e.g. '1 1 1 1 1 1')를 제대로 판단하기 위해서이다. 이 경우 그 이전과 이후에 무슨값이 나오냐에 따라 증가하는 경우라 봐도 되고, 감소하는 경우라 봐도 된다.

 

 

3.

  그리고 영향을 끼치는 부분이 바로 직전 값 뿐이므로 배열로 할 필요 없이 이전값만 기억하면 카운팅을 할 수 있다.

  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int max = 1;
        int incCnt = 1;
        int decCnt = 1;

        int bf = Integer.parseInt(st.nextToken());
        n--;

        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());

            if (cur==bf) {
                incCnt++;
                decCnt++;
                continue;
            }

            // inc chk
            if (cur < bf) {
                max = Math.max(max, incCnt);
                incCnt = 1;
            } else {
                incCnt++;
            }

            // dec chk
            if (cur > bf) {
                max = Math.max(max, decCnt);
                decCnt = 1;
            } else {
                decCnt++;
            }

            bf = cur;
        }
        
        max = Math.max(max, Math.max(incCnt, decCnt));
        System.out.println(max);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}