프로그래머스 - 정렬 - K번째수

1. 문제 출처

2. 문제 설명

3. 해답모음 - 다양한 정렬 함수의 활용을 통한 학습 

 

 

 

1. 문제 출처

 

문제의 출처는 유명한 프로그래머스 사이트의 코딩테스트 연습 문제를 가져와봤습니다. 

 

 

문제로 이동하기

 

2. 문제 설명

(1) Input의 설명

commands = 인덱싱 기준의 input

array = 정렬 대상 리스트

 

(2) 문제의 핵심 - 정렬 방법

이 문제의 input은 굉장히 직관적이어서 이해하기 쉽습니다. 

 

다만 여기서 핵심은 데이터를 정렬할 때 어떤 방식을 이용하여 데이터를 정렬하느냐 입니다. 

 

저는 연습삼아서 기본 내장 함수를 포함하여, 퀵정렬, 버블 정렬, 병합 정렬 등을 이용해서 문제를 풀어보도록 하겠습니다. 

 

3. 해답모음 - 다양한 정렬 함수의 활용을 통한 학습 

(1) 내장함수를 이용한 해답

def solution(array, commands):
    answer = []
 
    for individual_list in commands:
        
        i = individual_list[0]-1
        j = individual_list[1]-1
        k = individual_list[2]-1
    
        ## 퀵소트
        f_list = sorted(array[i:j+1])
        
        answer.append(f_list[k])
 
    return answer

 

(2) 퀵정렬을 이용한 해답

def quick_sort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]
    left = list()
    right = list()
    
    for i in range(1 , len(data)):
        if data[i] > pivot:
            right.append(data[i])
        else:
            left.append(data[i])
    
    return quick_sort(left) + [pivot] + quick_sort(right)
 
 
 
def solution(array, commands):
    answer = []
 
    for individual_list in commands:
        
        i = individual_list[0]-1
        j = individual_list[1]-1
        k = individual_list[2]-1
    
        ## 퀵소트
        f_list = quick_sort(array[i:j+1])
        
        answer.append(f_list[k])
 
    return answer

def bubble_sort(data):
    
    for i in range(len(data) - 1):
        swap = False
        for index in range(len(data) - 1 - i):
            if data[index] > data[index + 1]:
                data[index], data[index+1] = data[index+1], data[index]
                swap = True
                
        if swap == False:
            break
    return data
    
    
 
 
def solution(array, commands):
    answer = []
 
    for individual_list in commands:
        
        i = individual_list[0]-1
        j = individual_list[1]-1
        k = individual_list[2]-1
    
        ## 퀵소트
        f_list = bubble_sort(array[i:j+1])
        
        answer.append(f_list[k])
 
    return answer

 

(4) 병합 정렬을 사용한 해답

 

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1
 
    # case2 - left 만 남아있을때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right만 남아있을때 
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged
 
 
def mergesplit(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)
    
 
 
def solution(array, commands):
    answer = []
 
    for individual_list in commands:
        
        i = individual_list[0]-1
        j = individual_list[1]-1
        k = individual_list[2]-1
    
        ## 퀵소트
        f_list = mergesplit(array[i:j+1])
        
        answer.append(f_list[k])
 
    return answer