[BOJ] 2491 수열 - JAVA

1. 문제

https://www.acmicpc.net/problem/2491

2491번: 수열

가장 긴 증가하는 부분수열, 가장 긴 감소하는 부분수열 중 더 긴 수열의 길이를 출력한다.

---

2. 풀이

"카운트"만 세면 되기 때문에 하나씩 입력받아가면서 조건에 해당되면 +1, 아니라면 1을 저장한다.

증가하는 수열, 감소하는 수열 모두 cnt를 체크하면 그 두 값과 현재 저장된 max값을 비교해서 더 큰 값을 다시 담는다.

마지막으로 꼭! 이전 숫자를 현재 숫자로 교체한다.

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

public class BOJ_2491_수열 {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        StringTokenizer st = new StringTokenizer(in.readLine());

        int max = 1;
        int iCnt = 1, dCnt = 1;

        int prev = Integer.parseInt(st.nextToken());

        for (int i = 1; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            iCnt = prev <= num ? iCnt + 1 : 1;
            dCnt = prev >= num ? dCnt + 1 : 1;

            max = iCnt > dCnt ? Math.max(max, iCnt) : Math.max(max, dCnt);
            prev = num;
        }

        System.out.println(max);

    }
}

 

이 문제는 시간초과가 났었는데, 그 이유는 카운트만 세지 않고 그 값을 리스트에 저장하면서 하려고 했기 때문이다.

수열 리스트를 만들어서 인덱스로 관리했다. 방식은 아래와 같다.

1. 수열이 비어있거나 인덱스가 수열의 사이즈와 같고 현재 숫자를 추가할 수 있다면-> list.add & idx++한다.
2. 수열의 인덱스값과 비교한 결과 숫자를 추가할 수 있다면 -> list.set(++idx, 현재숫자)한다.
3. 그 밖의 경우는 list.set(0,현재숫자)를 하고 인덱스를 0으로 바꾼다. 
4. 숫자를 모두 입력받았다면 증가하는 수열 리스트의 사이즈, 감소하는 수열 리스트의 사이즈 둘을 비교해 더 큰 값을 출력한다.

---

3. 결과

시간초과는 위의 그 이유였고, 그 이후는 prev를 현재 숫자로 안바꿔줘서 계속 틀렸다.

고치는 와중에 코드만 점점 간결해졌다. ㅎㅎ