프로그래머스: [K번째 수]

📌 프로그래머스: [K번째 수]

🔗 문제 링크

---

문제 접근 방식 💡

• commands 리스트를 순회하면서 각 요청([i, j, k])을 처리.
• 주어진 배열의 i번째부터 j번째까지 자른 후 정렬.
• 정렬된 배열에서 k번째 원소를 선택하여 결과 리스트에 추가.

---

Solution 💻

def solution(array, commands):
    answer = []
    for command in commands:
        arr = sorted(array[command[0]-1:command[1]])
        answer.append(arr[command[2]-1])
    return answer

시간 복잡도 분석 ⏲️

• 자르기(array[i-1:j]): O(N)
• 정렬(sorted()): O(N log N)
• 선택(arr[k-1]): O(1)
• 총 시간 복잡도: O(M * N log N),
  • M은 commands의 길이, N은 배열의 크기.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(M),
  • answer 리스트에 M개의 값을 저장.