프로그래머스 LV 1 K번째 수

문제 유형 : 정렬 
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42748

프로그래머스

 

1. 문제 풀이 

1) array =  [1,5,2,6,3,7,4] 일 때 i,j,k가 무엇인지를 파악하는 것이 중요했다. 
i = 2  : i부터

j = 5 : j까지 

k = K번째 숫자 

2) commands = [ [i,j,k] [i,j,k] ] 이런 식으로 2차원 배열이기 때문에 commands를 해석해주는 것이 중요했다. 

commands= [ [2,5,3] , [4,4,1] , [1,7,3] ] 일 때 하나씩 쪼개보면 다음과 같이 정리할 수 있다. 

commands[0] = [2,5,3]  => commands[0][0] = 2 = i , [0][1] = 5 = j , [0][2] = 3 = k 

commands[1] = [4,4,1]  => commands[1][0] = 4 , [1][1] = 4 , [1][2] = 1

commands[2] = [1,7,3] => commands[2][0] = 1 . [2][1] = 7 , [2][2] = 3

3) 위 2)를 정리하자면 다음과 같다. 

- commands[0]~ commands[i] 까지 반복문 돌림

- commands[i][0] = i , commands[i][1] = j , commands[i][2] = k 

4) N번째 숫자 정의 

처음에 list range error 가 떠서 다시 살펴봤더니 K번째 숫자 , J번째 같은 것들이 사람 기준이였던 것이다. 즉 K=2일 때 
2번째면 실제로 문법적으로는 0부터 시작하므로 1번째인 것이다. 그래서 처음 범위에 -1를 해줘야 했다.

5) 오름차순 정의 후 k번째 숫자를 answer이라는 빈 배열에 append 해주었다.

 

2. 풀이 코드 

def solution(array, commands):
    answer = []
    for i in commands:
        start = i[0]
        end = i[1]
        target = i[2]
        
        arr1 = array[start-1:end]
        arr1.sort()
        num = arr1[target-1]
        answer.append(num)
            
    return answer

=> i로 반복문을 돌렸기 때문에 start, end, target 을 문제에서 i,j,k로 생각했다. 

=> arr1 이라는 새로운 배열에 array 에 start번째이지만 프로그래밍적으로는 start-1번째 이므로 slice된 배열을 넣어주었다

=> 그리고 오름차순으로 정렬하라 했기 때문에 sort()로 정렬해주었다. 

=> num은 문제에서의 K번째 숫자를 이야기한다. 이 또한 실제로 target 번째는 파이썬에서는 target-1번째이므로 target-1을 해주었다.

=> 그 숫자를 answer이라는 빈 배열에 넣어주었다. 

 

3. 시간복잡도

: 시간복잡도는 반복문 돌아가는 N번과 sort로 정렬하는 NlogN을 더해서 O(N+NlogN) , 즉 O(NlogN)이 나올 것이다

: 공간복잡도는 start와 end로 슬라이싱되는 것과 target으로 찍힌 숫자의 갯수에 비례하므로 O(N)이 나올 것이다.