실력키우기 수열(JAVA)

1998 : 수열

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 590회    시도횟수: 2650회   

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라.

 

예를 들어 수열 1 2 2 4 4 5 7 7 2 의 경우에는 1≤2≤2≤4≤4≤5≤7≤7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4 1 3 3 2 2 9 2 3 의 경우에는 3≥3≥2≥2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1 5 3 6 4 7 1 3 2 9 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

 

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

첫째 줄에 가장 긴 길이를 출력한다.

[Copy] 9 1 2 2 4 4 5 7 7 2

[Copy] 8

[Copy] 9 4 1 3 3 2 2 9 2 3

[Copy] 4

[Copy] 11 1 5 3 6 4 7 1 3 2 9 5

[Copy] 2

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

/**************************************************************     Problem: 1998     User: a132034     Language: Java     Result: Success     Time:826 ms     Memory:27088 kb ****************************************************************/     import java.util.Scanner;   public class Main {     private static Scanner sc;     public static int[] result;     public static void main(String[] args) {         sc = new Scanner(System.in);         int N = sc.nextInt();         int arr[] = new int[N];         int max = 0;         int curB = 0;         int curS = 0;         for(int i = 0 ; i < N; ++i)             arr[i] = sc.nextInt();                   boolean flgB = false;         boolean flgS = false;                   //길이가 1일 경우 생각할 것없이 1, cur변수를 2부터 시작하므로 예외처리.         if(N == 1){             System.out.println(1);             return;         }                   for(int i = 0 ; i < N-1; ++i)         {             if(arr[i] <= arr[i+1])             {                 if(flgB == false){                     curB = 2;                     flgB = true;                 }                 else                     curB++;               }             else             {                 if(max < curB)                 {                     max = curB;                 }                 flgB = false;             }                           if(arr[i] >= arr[i+1])             {                 if(flgS == false){                     curS = 2;                     flgS = true;                 }                 else                     curS++;             }             else             {                 if(max < curS)                 {                     max = curS;                 }                 flgS = false;             }         }                       //마지막이 if을 만족하여 else를 오지 못할 경우를 대비         if(max < curS)         {             max = curS;         }         if(max < curB)         {             max = curB;         }                   System.out.println(max);                         } }

딱히 어려운 것 없이 이전값보다 클(작을) 경우 cur값을 ++시켜 주었고, 조건을 만족하지 못하는 경우 flag를 주어 다시 시작하도록 하였다. 

만족하는 경우 수열의 길이는 2부터 시작한다고 생각하여 초기값을 2로 주었다. 

각각의 변수를 만들어 더 큰 연속 수열과 더 작은 연속 수열을 한 루프 안에서 계산하며 max변수에 더 긴 길이값을 넣어주었다. 

이렇게 풀었을 경우

2가지 문제가 발생한다. 

1. 만약 수열이 1개만 들어왔을 경우. 

수열의 최소 길이를 2로 설정해 두었기 때문에 예외처리가 필요하다.

2. 만약 수열의 마지막이 그 전값보다 크(작)기 때문에 if를 만족했는데 (38 or 57줄) 그떄의 수열의 길이가 최대인 경우 

이 경우 else를 타지 못해 max보다 더 긴 결과가 나와도 max값의 갱신이 되지 않아 모든 루프가 끝난 후 한번 더 비교해주었다.