문제

2733. Neither Minimum nor Maximum

User Accepted:14764
User Tried:15065
Total Accepted:24475
Total Submissions:29927
Difficulty:Easy

Given an integer array nums containing distinct positive integers, find and return any number from the array that is neither the minimum nor the maximum value in the array, or -1 if there is no such number.

Return the selected integer.

Example 1:
  Input: nums = [3,2,1,4]
  Output: 2
  Explanation: In this example, the minimum value is 1 and the maximum value is 4. 
  Therefore, either 2 or 3 can be valid answers.

Example 2:
  Input: nums = [1,2]
  Output: -1
  Explanation: Since there is no number in nums that is neither the maximum nor the minimum, 
  we cannot select a number that satisfies the given condition. Therefore, there is no answer.

Example 3:
  Input: nums = [2,1,3]
  Output: 2
  Explanation: Since 2 is neither the maximum nor the minimum value in nums, 
  it is the only valid answer. 
 

Constraints:
  1 <= nums.length <= 100
  1 <= nums[i] <= 100
  All values in nums are distinct

풀이

# O(NlogN)
if len(nums) < 3:
	return -1
nums.sort()
return nums[1]

한 번 정렬을 한 후 1번째 인덱스를 반환하는 방식이다. 정렬에 O(NlogN)의 시간복잡도를 갖는다.

# O(N)
if len(nums) < 3:
	return -1
max_num = max(nums)
min_num = min(nums)
for num in nums:
	if min_num < num < max_num:
		return num

내가 이 문제를 보고 당장 생각나는대로 풀었던 코드를 좀 다듬었다.
나는 쓸데없이 최대값, 최솟값을 통해 그 값의 인덱스도 구한 후 그 인덱스로 반복문을 실행했었다.
max()와 min()을 위해 리스트를 한 번 순회할 때 마다 O(N)의 시간복잡도를 갖는다.

# O(1)
if len(nums) < 3:
	return -1
a = nums[0]
b = nums[1]
c = nums[2]
if a < b < c or c < b < a:
	return b
elif b < a < c or c < a < b: 
	return a
else:
	return c

상수 시간복잡도를 갖는 풀이법이다. 막상 보면 왜 이런 생각을 못 했지 싶을 정도로 간단하지만 이런걸 문제 풀려고 앉은 자리에서 생각해내는 것도 다 경험이 쌓여야 하는 것이지 않을까 싶다.