정렬 문제 - 구간정렬(오름차순, 내림차순 구간 max, min으로 판단)

정수 배열 nums 가 주어졌을 때
오름차순으로 정렬하기 위해 배열 내에서 정렬이 필요한 구간의 길이를 출력하는 프로그램을 작성하세요.

입출력 예시
입력: 2, 6, 4, 8, 5, 3, 9, 10
출력: 5

입력: 1, 3, 1
출력: 2

 

• 내 풀이

public class Main {
    public static int solution(int[] nums) {
        int startIdx = 0; 
        int endIdx = 0; // max 보다 크면서 이후로 작은 값이 없는 것이 endIdx.. -> 해설과 차이나는 부분!

        startIdx = getStartIdx(nums);

        if(startIdx == -1){
            return 0;
        }

        endIdx = getEndIdx(nums, startIdx);

        return endIdx - startIdx + 1; 
    }

    public static int getStartIdx(int[] nums) {
        int startIdx = -1;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                startIdx = i;
                break;
            }
        }
        return startIdx;
    }

    public static int getEndIdx(int[] nums, int startIdx) {
        int max = nums[startIdx];
        int endIdx = nums.length - 1;

        for (int i = startIdx + 1; i < nums.length; i++) {
            if (nums[i - 1] < nums[i] && max < nums[i]) {
                if (isOrdered(nums, i)) { // 해설 방식이 더 효율적임
                    endIdx = i - 1;
                    break;
                }else{
                    max = Math.max(max, nums[i]);
                }
            }
        }

        return endIdx;
    }

    public static boolean isOrdered(int[] nums, int idx) {
        for (int i = idx; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // Test code
        int[] nums = {2, 6, 4, 8, 5, 3, 9, 10};
        System.out.println(solution(nums));

        nums = new int[]{1, 3, 1};
        System.out.println(solution(nums));

        nums = new int[]{1, 9, 3, 4, 5};
        System.out.println(solution(nums));

        nums = new int[]{1, 2, 3, 4, 5};
        System.out.println(solution(nums));
    }
}

 

• 해설

/**
 * 내가 찾은 방향. -> idx++ 진행하며 해당 값이 max보다 클 때 해당 값 이후로 오름차순이면 타겟은 해당값의 idx-1 이다. -> 마지막 오름차순이 아닌 값의 인덱스 구하기 !!
 * 해설 -> 같은 타겟 구하는데 방식의 해석이 조금 다름!
 * -> idx++ 진행하면서 현재 값이 max 보다 작으면 타겟 ->  max 가 보다 크다 == 오름차순이다. <-> max 보다 작다 == 오름차순이 아니다.. -> 마지막 오름차순이 아닌 값의 인덱스 구하기 !!
 * --> max 보다 작은 마지막 인덱스를 구하는 것!
 * --> min도 같은 이치로 idx-- 진행하면서 min보다 큰 값이 타겟..
 */
public class Main { 

    public static int solution(int[] nums) {
        int startIdx = 0;
        int min = Integer.MAX_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) { 
            if (min < nums[i]) {
                startIdx = i;
                continue;
            }
            min = nums[i];
        }

        int endIdx = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) { 
            if (max > nums[i]) {
                endIdx = i;
                continue;
            }
            max = nums[i];
        }

        return endIdx - startIdx + 1;  // startIdx의 기본값 0 endIdx 기본값은 -1으로하여 둘다 결과 없을 때 0이 되는 테크닉 기억..!
    }


    public static void main(String[] args) {
        // Test code
        int[] nums = {2, 6, 4, 8, 5, 3, 9, 10};
        System.out.println(solution(nums));

        nums = new int[]{1, 3, 1};
        System.out.println(solution(nums));

        nums = new int[]{1, 9, 3, 4, 5};
        System.out.println(solution(nums));

        nums = new int[]{1, 2, 3, 4, 5};
        System.out.println(solution(nums));
    }
}