[Algorithm] 정렬 - K번째 수

 

 

programmers에 등록되어있는 정렬 - K번째 수 구하기 알고리즘에 대한 풀이입니다.

개인적인 공부를 위해 작성하는 개인적인 해석으로 경우에 따라 틀린 해석일 수도 있음을 상술합니다.

알고리즘 코딩 테스트는 간편하고 빠르게 구현할 수 있는 언어인 파이썬으로 응시하는 경향이 강하다고 합니다.

따라서 알고리즘 포스팅 또한 파이썬을 기준으로 풀어보도록 하겠습니다.

 

코드 링크는 아래 첨부합니다.

https://programmers.co.kr/learn/courses/30/lessons/42748

 

본격적인 포스팅을 하기에 앞서 일러두자면, 후술할 설명들은 최대한 자세하게 코드의 흐름을 설명하고자 하였으므로, 숙달된 분들에게는 불필요한 서술이 많습니다.

만약 코드 자체만으로 분석이 가능하신 분들은 위에서 두 번째와 세 번째 코드 블럭만 참고하시면 됩니다.

 

설명하기에 앞서, 알고리즘 문제에 대한 설명 전문을 첨부합니다.

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

 

 

그리고 위 설명을 풀이하기 위한 디폴트 코드는 아래와 같습니다.

 

def solution(array, commands):
    answer = []
    
    return answer

 

solution 함수는 array와 commands를 매개변수로 받고 있습니다.

 

문제 설명에 의하면 commands라는 객체는 [시작 인덱스, 끝 인덱스, 포인트 인덱스]의 그룹이 복수개로 존재합니다.

(이는 commands 라는 배열을 순환해야 함을 의미합니다.)

여기서 실직적으로 값을 뽑아내기 위한 포인트 인덱스가 k번째 수에 해당하는 값입니다.

 

문제에서는 이들 변수를 아래와 같이 정의하고 있습니다.

i = 시작 인덱스

j = 끝 인덱스

k = 포인트 인덱스

 

알고리즘의 순서는 아래와 같습니다.

1. commands 배열을 순환하며, 시작, 끝, 포인트 인덱스 변수를 뽑아낸다.

2. array 변수를 시작 인덱스부터 끝 인덱스까지 잘라낸다.

3. 잘라낸 array변수를 오름차순으로 정렬한다.

4. 정렬한 array변수에서 k번째에 해당하는 값을 뽑아 answer 변수에 append 합니다.

 

위 알고리즘에 근거한 제 코드 풀이는 아래와 같습니다.

def solution(array, commands):
    answer = []
    
    for cmd in commands:
        # i(시작 인덱스), j(끝 인덱스), k(포인트 인덱스)를 뽑아낸다.
        i = cmd[0] - 1
        j = cmd[1]
        k = cmd[2] - 1
        
        # 배열을 i ~ j 까지 잘라낸다. 
        tmp = array[i:j]
        
        #잘라낸 배열을 오름차순 정렬
        tmp.sort()
        
        #answer 배열에 append
        answer.append(tmp[k])
        
    return answer

 

commands는 복수개로 존재할 수 있으니 for문으로 순환하며, 현재 순환 중인 commands 배열을 cmd 변수로 지정합니다.

 

여기서, i와 k 변수에 -1을 한 이유는, 배열은 첫 인덱스가 0이기 때문입니다.

i가 1인 경우, 배열의 첫 번째 값을 의미하므로 0번 인덱스에 접근해야합니다.

그렇다면 1이 할당되어있는 i 값에서 -1을 해주어야 0이 되므로 cmd[0] -1 이와 같이 처리해준 것입니다.

 

위와 같이 프로그래밍해도 무사히 채점은 통과할 수 있습니다만, 위 알고리즘을 람다식을 이용해 획기적으로 짧은 코드로 바꿔줄 수도 있습니다.

 

아래의 코드를 참고해 주세요.

def solution(array, commands):

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

람다식은 익명 함수로, 필요할 때 1회용으로 생성해 바로 실행하는 함수를 의미합니다.

간단한 논리이고 한 번만 쓰일 기능이라면 구태여 def ~~~ 와 같이 별도의 함수를 생성하지 않아도 된다는 것이죠.

알고리즘 자체는 상술한 것과 다르지 않으므로 4단계로 상술한 알고리즘을 상기하며 동작 방식을 하나하나 살펴보도록 하겠습니다.

 

1. commands 배열을 순환하며, 시작, 끝, 포인트 인덱스 변수를 뽑아낸다.

이는 map() 함수로 처음 코드에서 사용한 for문을 대체합니다.

map함수는 특정 함수와 반복 가능한 값을 매개 변수로 받으며, 사용자가 지시한 처리 과정을 거쳐 결과물을 반환합니다.

이때, map에서 반환한 결괏값은 list형태로 변환 해주어야 우리가 원하는 형태의 데이터를 얻을 수 있습니다.

commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

answer = list(map(list, commands))

#결과: [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

 

위 코드는 map을 이용해 commands 값을 순환하며 순환되는 값들을 list 형태로 바꿔주는 코드입니다.

따라서 원래의 commands 변수에 있던 값들이 변하지 않고 그대로 출력해주는 것처럼 보입니다만, 제기능을 하고 있다고 볼 수 있습니다.

 

하지만 우리는 시작 인덱스, 끝 인덱스, 포인트 인덱스를 추출해야 하므로 이대로는 써먹을 수가 없습니다.

여기서, 익명 함수를 생성해 commands에서 순환하는 값에서 각 인덱스들을 추출해주도록 하겠습니다.

 

commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

answer = list(map(lambda x : [x[0], x[1], x[2]], commands))

#결과: [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

위 코드를 실행해 보면 결괏값은 다르지 않은 것을 알 수 있습니다.

하지만 여기서 lambda라는 키워드로 시작하는 코드를 볼 수 있는데요, 이것이 바로 익명 함수입니다.

옆에 보이는 x 가 commands를 순환하며 뽑아진 값에 대한 매개 변수입니다.

위 코드를 실행하게 되면 x는 아마도 아래의 과정으로 값을 할당하게 될 겁니다.

 

x = [2, 5, 3]

x = [4, 4, 1]

x = [1, 7, 3]

 

그렇다면 우리는 x에 담겨 있는 각 시작, 끝, 포인트 인덱스를 추출해 낼 수 있겠죠.

 

람다식에서의 반환은 "lambda x : ~~" 이 부분의 물결 표시 영역에서 이루어지게 됩니다.

우리는 할당받은 x를 인덱스를 통해 접근할 수 있게 되었으므로, 첫 번째 순환임을 가정했을 때, x[0]의 값인 2를 얻을 수가 있습니다.

 

즉, 첫 번째 코드에서의 i, j ,k 값을 예시로 들면 아래와 완전히 같게 됩니다.

i = x[0]

j = x[1]

k = x[2]

 

위 코드에서는 각 값들을 배열 형태로 반환해 주고 있으므로 결과적으로는 원래의 commands값과 다르지 않은 값을 보여주고 있는 것입니다.

 

만약 람다식을 쓰지 않고 별도의 함수를 생성해준다면 아래와 같은 코드가 됩니다.

 

#람다식을 대처하는 함수 =======
def spl(x):
    return [x[0], x[1], x[2]]
#==============================

commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

answer = list(map(spl, commands))

commands가 순환할 때마다 할당되는 변수는 우리가 만들어준 spl 변수의 매개변수가 되어 spl변수를 수행한 후 결괏값을 반환합니다.

 

 

2. array 변수를 시작 인덱스부터 끝 인덱스까지 잘라낸다.

array = [1, 5, 2, 6, 3, 7, 4];

commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

answer = list(map(lambda x : array[x[0] - 1 : x[1]], commands))

#결과: [[5, 2, 6, 3], [6], [1, 5, 2, 6, 3, 7, 4]]

위 과정을 통해 우리는 x 변수가 commands를 순환하면서 할당된 값임을 알고 있습니다.

또한 x에서 인덱스를 통해 특정 값에 접근할 수 있다는 것도 알고 있습니다.

그렇다면 x에서 추출한 특정값을 통해 array에 접근할 수도 있겠죠.

 

배열의 특정 구간을 추출하는 문법은 array[ : ]입니다.

이 문법은 세미콜론 ( : )을 기준으로 왼쪽이 시작 인덱스, 오른쪽이 끝에서 바로 이전 인덱스를 의미합니다.

만약 array[1:3]을 수행하게 되면 1번 인덱스 ~ 2번 인덱스까지 추출한다는 의미가 되므로 사용 시 주의가 필요하겠습니다.

 

각설하고, commands의 첫 번째 x 값을 예시로 들어, 결과 값이 [5, 2, 6, 3]으로 나온 이유를 분석해보겠습니다.

첫번째 x 값의 구성은 [2, 5, 3]입니다.

코드에서는 2 번째 값부터 5번째 이전의 값까지의 배열을 뽑으라고 명령하고 있으므로 반환 결과 값은 아래와 같게 됩니다.

[1, 5, 2, 6, 3, 7, 4]

 

3. 잘라낸 array변수를 오름차순으로 정렬한다.

이제, 뽑아놓은 결과 값을 오름차순으로 정렬해야 합니다.

정렬은 sorted 함수를 이용해 간단히 할 수 있으며, 별도의 옵션이 없는 경우 오름차순으로 정렬합니다.

sorted 함수를 적용한 코드는 아래와 같습니다.

 

array = [1, 5, 2, 6, 3, 7, 4];

commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

answer = list(map(lambda x : sorted(array[x[0] - 1 : x[1]]), commands))

#결과: [[2, 3, 5, 6], [6], [1, 2, 3, 4, 5, 6, 7]]

2번에서 수행한 결과 값이 sorted() 함수로 감싸줬을 뿐인데 깔끔하게 오름차순으로 정렬이 된 것을 확인할 수 있습니다.

이제, sorted로 반환된 배열에서 k번째 수를 뽑아내기만 하면 이 문제는 완료입니다.

 

4. 정렬한 array변수에서 k번째에 해당하는 값을 뽑아 answer 변수에 append 합니다.

여기서 우리는 map 함수를 사용하고 있기 때문에 사실 answer변수에 append를 수행할 필요는 없습니다.

다만 sorted() 된 배열에서 sorted()[x[2] - 1]만 해주면 되죠.

 

answer = list(map(lambda x : 정렬된배열[x[2] -1], commands))

가독성을 위해 sorted(array[x[0] - 1 : x[1]]) 부분을 '정렬된배열'로 치환했습니다.

'정렬된배열'은 i 번째에서 k번째까지의 배열을 잘라내어 오름차순으로 정렬한 결괏값을 의미합니다.

여기서 x[2] 값인 포인트 인덱스를 이용해 문제에서 요구한 k 값을 뽑아내는 것이 가능했습니다.

 

아래는 빈 스크립트에서 붙여 넣기로 바로 수행할 수 있는 간이 코드입니다.

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

array = [1, 5, 2, 6, 3, 7, 4]
commands = [[2, 5, 3], [4, 4, 1], [1, 7, 3]]

solution(array, commands)

#결과: [5, 6, 3]