[코딩테스트 고득점 Kit / Level1 👶🏻 / 정렬] K번째수(python)

1. 문제 설명

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 함수를 작성해주세요.

2. 제한 사항

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

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입니다.

4. 나의 풀이

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

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

commands [[2, 5, 3], [4, 4, 1], [1, 7, 3]] 일 때

[2, 5, 3]의 경우 2번째부터 5번째인데, 1번째부터 시작하는 듯하지만 컴퓨터는 0부터 수를 세기 때문에 사실은 1번째 부터 4번째를 의미한다. 그래서 command[0]-1으로 시작값을 준다.

뒤에는 command[1]로 되어있는데, 끝나는 숫자에서 1이 빼서 세지기 때문에 5를 적어도 사실은 4번째까지 알아서 된다.

그 다음 그 값들을 배열에 담아서 sort()함수로 정렬한다.

정렬한 다음, command[2]에 있던 명령어에서 3번째 것을 구하고 싶다면 사실은 0부터 시작해서 2번째 것을 구하고 싶은 것이기 때문에 -1을 빼서 정답지에 넣어준다.

5. 다른 사람의 풀이

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

정말 간단하게 풀었당 ...ㅋㅋㅋ

이 식의 lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1] 부터 분석해보겠다.

 

💡 람다(Lambda) 함수
map(), reduce(), filter() 와 함께 사용되는 강력한 일시적 함수. 필요한 곳에서 사용하고 즉시 버릴 수 있다.
예를 들어, f = lambda x , y : x +y 라고 함수 정의하면 f (4,6) 는 10이 된다.

 

💡 map() 함수
map(function, iterable) 에서 첫 번째 function 은 함수의 이름이며 두 번째 iterable은 한 번에 하나의 요소를 반환할 수 있는 객체. 
즉, 정의한 람다 함수를 iterable의 모든 요소에 대해 돌아가면서 적용한다.
위 풀이에서 commands 2중 리스트 안의 모든 1차원 리스트에 대하여 돌아가면서 숫자를 뽑고 있다.
그 후 list로 마무리한다.

 

💡sorted

sorted() 정렬함수는 정렬된 결과를 list로 반환한다.

#str
sorted("hello") #["e","h","l","l","o"]

#list
sorted([5,2,1,3,4]) #["1","2","3","4","5"]
sorted([[2,1,3],[3,2,1],[1,2,3]]) #[[1, 2, 3], [2, 1, 3], [3, 2, 1]]

#set
sorted({3,2,1}) #[1,2,3]

#tuple
sorted((3,2,1)) #[1,2,3]

#dict
sorted({3:1,2:3,1:4}) #[1,2,3]

dictionary는 정렬할 때 key값을 추출해서 정렬한다.

value값을 기준으로 정렬하려면 sorted의 파라미터 key를 이용하면 된다.

dict = {3:1, 2:3, 1:4}

sorted(dict.items(), key=lambda x: x[1])

# 내림차순으로 정렬하고 싶을 때
sorted(range(1,10), reverse=True) #[9, 8, 7, 6, 5, 4, 3, 2, 1]

lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1] 을 다시 보면,

sorted(array[x[0]-1:x[1]])에서 배열의 0번부터 n-1번까지 정렬을 한 다음

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

반환된 리스트에서 k번째 숫자 x[2]-1를 리턴하여 리스트를 만든다.

 

6. 깨달은점

- 람다와 map을 이용하면 굉장히 간단하게 풀 수 있다.