[랜덤 마라톤] k개의 부분 배열(22965)

1. 문제 풀이 아이디어

• 문제에서 나올 수 있는 경우의 수는 3가지다.

• 첫 번째는 정렬된 경우, 두 번째는 한 번 순회하여 정렬된 경우, 세 번째는 그 외의 경우다.

• 이 세 가지 경우로 나누어 처리하면 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        int[] a = new int[n];
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int count = 0;
        int prev = 0;
        int prevMin = 0;
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(stringTokenizer.nextToken());
            if (prev > cur) {
                count++;
            }
            if (count == 1 && cur > prevMin) {
                count++;
            }
            if (count > 1)
                break;
            if (prevMin == 0)
                prevMin = cur;
            prev = cur;
        }
        if (count == 0) System.out.println(1);
        else if (count == 1) System.out.println(2);
        else System.out.println(3);
        bufferedReader.close();
    }
}

3. 정리

• 값을 입력받을 때마다 이전 값과 비교하여, 이전 값이 현재 값보다 크면 count를 증가시킨다.

• count가 1이고 현재 값이 이전 최소값보다 크면 count를 다시 증가시킨다.

• count가 1보다 크면 반복문을 종료한다.

• count의 값에 따라 결과를 출력하여 문제를 해결한다.