[Python 코테 입문] 2. (문제 1번) 최솟값의 위치

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션2. 배열, 연결리스트, deque

 

(문제 1번) 최솟값의 위치

수열의 원소에서 가장 작은 값을 찾고 싶습니다.

매개변수 nums에 길이가 n인 수열이 주어지면 수열의 원소 중에서 가장 작은 값을 찾아 그 값의 nums 배열의 인덱스 번호를 반환하는 프로그램을 작성하세요.

배열의 인덱스 번호는 0부터 시작합니다.

 

입출력 예

nums	answer
[7, 10, 5, 3, 2, 15, 19]	4
[-12, 12, 30, -15, -5, 3, 9, -11, 14]	3
[17, 11, 5, 8, 23, 29, 19, 12, 25, 16, 2]	10
[7, 5, 12, -9, -12, 22, -30, -35, -21]	7

 

제한사항

• nums의 길이 : 3 <= n <= 100,000
• 배열 nums의 원소는 정수입니다. -1,000,000 <= nums[i] <= 1,000,000
• 배열 nums의 원소는 중복된 값이 존재하지 않습니다.

 

입력예제 1 설명

[2, 7, 1, 12, 8, 15, 19]의 최솟값은 1이고 1은 배열의 2번 인덱스 위치에 있습니다.

 

풀이

def findMinValue(nums):
  nums.sort()
  return nums[0];

def findIndex(nums, val):
  return nums.index(val);

def findMinIndex(nums):
  newNums = nums.copy()
  min = findMinValue(nums)
  index = findIndex(newNums, min)
  return index;

nums = [2, 7, 1, 12, 8, 15, 19]

findMinIndex(nums)

2

 

배열은 Python에서 list 자료형으로 구현되어 있다.

list의 기본 함수들을 사용해서 문제를 풀었다.

 

풀이 과정

1. 입력으로 들어온 nums는 크기가 3 이상 10만 이하인 list(배열) 자료형이다. nums의 값들은 -100만 이상 100만 이하의 정수이며, 중복된 값은 존재하지 않는다.

2. findMinValue(nums) 함수를 정의한다. 이 함수는 파라미터로 받은 nums를 sort() 함수로 정렬해서 0번째 인덱스에 해당하는 값을 리턴한다. 즉, 배열의 최솟값을 리턴한다.

3. findIndex(nums, val) 함수를 정의한다. 이 함수는 두 개의 파라미터인 nums와 val을 받는다. index() 함수를 써서 nums에서 val 값의 인덱스를 반환한다. 즉, findIndex() 함수에 파라미터로 배열과 최솟값을 넘기면 최솟값의 인덱스를 반환한다.

4. findMinIndex(nums) 함수를 정의한다. 이 함수는 파라미터로 nums 배열을 받아 최솟값의 인덱스를 반환한다.

 

시간복잡도

파이썬 list의 copy() 함수 : O(n)

파이썬 list의 sort() 함수 : O(nlogn)

 

(참고) 파이썬 자료형 별 주요 연산자의 시간복잡도(Big-O)

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

 

정답 풀이

분석

1. 첫 번째 제한사항(nums의 길이 : 3 <= n <= 100,000)을 보면 입력크기가 10만까지 들어온다.

시간복잡도는 O(n)이나 O(nlogn)이어야 한다.  시간복잡도가 O(n²)이면 안 된다.

2. 배열을 순차탐색하며 최솟값을 찾아 인덱스를 반환한다. 단순 for loop를 쓰면 된다. 시간복잡도는 O(n)이다.

 

풀이

def solution(nums):
    answer = 0
    # 배열의 첫 번째 값부터 들어갈 수 있도록 minValue는 배열 원소의 최대값보다 훨씬 큰 값으로 초기화한다.
    minValue = 10000000
    for i in range(len(nums)):
      if(nums[i] < minValue):
        minValue = nums[i]
        answer = i
    
    return answer

print(solution([7, 10, 5, 3, 2, 15, 19]))
print(solution([-12, 12, 30, -15, -5, 3, 9, -11, 14]))
print(solution([17, 11, 5, 8, 23, 29, 19, 12, 25, 16, 2]))
print(solution([7, 5, 12, -9, -12, 22, -30, -35, -21]))
print(solution([2, 7, 1, 12, 8, 15, 19]))

4

3

10

7

2