[프로그래머스] 정렬 - K번째 수(파이썬 문제 풀이)

문제 링크

코딩테스트 연습 - K번째수

 

주어진 범위를 정렬한 뒤 K번째 수를 출력하는 문제입니다.

파이썬의 내장 함수를 사용해도 되지만 복습 차원에서 퀵 정렬을 사용해 문제를 풀이해 보았습니다

퀵 정렬을 구현하는 함수를 만들고, 입력받은 커맨드에 따라 원본 배열에서 범위를 추출하여 퀵 정렬 함수에 전달하고 정렬된 배열에서 k번 째(k-1) 데이터를 출력하도록 구성했습니다.

 

문제 풀이(파이썬)

---

def Qsort(s, e):
    if s < e:
        pivot = tmp[e]
        pos = s

        for i in range(s, e):
            if tmp[i] < pivot:
                tmp[pos], tmp[i] = tmp[i], tmp[pos]
                pos += 1
        tmp[pos], tmp[e] = tmp[e], tmp[pos]
        Qsort(s, pos-1)
        Qsort(pos+1, e)


def solution(array, commands):
    global tmp
    res = list()
    for c in commands:
        i, j, k = c

        # 원본 arr에서 영역 추출
        tmp = list()
        for a in range(i-1, j):
            tmp.append(array[a])

        Qsort(0, len(tmp)-1)
        res.append(tmp[k-1])

    return res

 

파이썬스러운 풀이 방법

def solution(array, commands):
    return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))

# 파이썬 내장함수 사용 + 직관적으로 이해하기 쉬운 코드
def solution(array, commands):
    answer = []
    for command in commands:
        i,j,k = command
        answer.append(list(sorted(array[i-1:j]))[k-1])
    return answer