[99클럽] 코테 스터디 31일차 TIL - 정렬(2733. Neither Minimum nor Maximum)

문제

서로 다른 정수값이 있는 nums[] 배열이 주어진다.
nums[] 배열에서 최댓값도 최솟값도 아닌 값을 찾아 그중 한 개만 반환하라.
만약 그런 값이 없다면 -1을 반환하라.
https://leetcode.com/problems/neither-minimum-nor-maximum/

풀이 방법

• 내 코드 - 시간 복잡도: O(NlogN)
  1. nums[]를 정렬한다.
  2. nums[]를 두 번째 요소부터 순회하면서 마지막 요소와 같지 않다면 최솟값도 최댓값도 아니므로 반환한다.
  3. 모든 요소를 순회하였음에도 반환이 되지 않았다면 -1을 반환한다.
     Arrays.sort() 시간 복잡도 O(NlogN)

class Solution {
    public int findNonMinOrMax(int[] nums) {

        Arrays.sort(nums);

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

    }
}

• 정렬을 이용하지 않은 코드 - 시간복잡도: O(N)
  1. nums[]의 크기가 3보다 작다면 최솟값도 최댓값도 아닌 값은 존재하지 않으므로 -1을 반환한다.
  2. nums[]를 순회하며 최솟값과 최댓값을 찾는다.
  3. 다시 nums[]를 순회하며 최솟값도 최댓값도 아닌 값을 찾아 반환하고 없다면 -1을 반환한다.

class Solution {
    public int findNonMinOrMax(int[] nums) {
        if (nums == null || nums.length < 3) {
            return -1;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int num : nums) {
            if (num < min) {
                min = num;
            }
            if (num > max) {
                max = num;
            }
        }

        for (int num : nums) {
            if (num != min && num != max) {
                return num;
            }
        }

        return -1;
    }
}

오늘 회고

문제를 풀 때 정렬을 자주 사용했는데 시간 복잡도가 O(NlogN)이나 걸린 다는 것을 처음 알았다.
다음부턴 정렬보다 효율적인 방법이 있는지 다시 한번 더 생각해본 뒤 풀자.
오늘도 최선을 다하자.