[엘리스][Python] 시즌2. 알고리즘 코드 챌린지 [Day2] - 정리 정돈을 좋아하는 k씨

https://code-challenge.elice.io/courses/282926/lectures/2455429/lecturepages/21567982/

알고리즘 문제집 | 엘리스 코드 챌린지

 

Day 2

💡 풀이 과정

• 단순하게 i ~ j 까지 배열에서 정렬 시 k 번째 수를 반환하는 문제이다.
• 입력 값들을 정렬시키면 더 효율적으로 풀 수 있을 것 같다.
  • 누적합처럼 요소들을 추가 삭제시키면서 정렬해나아가면 효율적일 것 같다.
• 하지만 해당 문제 조건에서 n, m 이 그렇게 높지 않기에 매번 i ~ j 까지 배열을 정렬해서 k 번째를 반환했다.

---

📌 포인트

• 시간 복잡도를 고려하지 않았지만 통과
• 고려한다면 입력값을 정렬시켜 누적합처럼 k 번째를 구했을 것이다.

---

💻  코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))

for _ in range(m):
    i, j, k = map(int, input().split())
    sortArr = sorted(arr[i-1:j])
    print(sortArr[k-1])