[프로그래머스/레벨1] K번째수

문제 풀면서 작성한 메모

풀이 과정

---

여러 코딩 테스트를 치르면서, 코딩 테스트 문제 푸는 방법을 정했다.

1. 문제를 정독하면서 메모(검은색으로 작성)한다. 주의해야 할 것은 ※으로 표시한다.
2. 알고리즘(분홍색으로 작성)을 떠올리고 적용하려고 노력한다.
3. 필요한 변수에 대해서는 변수명(하늘색으로 작성)을 작성한다.
4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.
5. 의사 코드에 맞춰 구현한다.

앞으로 이 순서대로 문제를 풀어볼 예정이다!

1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다.

 

문제 정독하고

인덱스 메모

 

우선 문제 자체는 길지도 않고 어렵지도 않아서 메모할 것이 거의 없었다. 단, 인덱스가 0부터 시작한다는 점을 주의해야 했다. 문제에서 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]이라 했는데, 이를 코드로 구현하면 인덱스는 1이 아닌 0부터 시작하기 때문에 array[2:5]가 아니라 array[1:5]이 되어야 한다. 따라서 이를 주의해야 한다고 ※ 표시로 메모했다.

2. 알고리즘을 떠올리고 적용하려고 노력한다.

ㅎㅎ..

정렬 메모

알고리즘은 이미 문제 옆에 정렬이라 나와 있어서 알고 있었지만, 여기서는 알고리즘을 적용하려고 노력할 필요도 없었다. 선택 정렬, 버블 정렬, 삽입 정렬 등을 생각할 필요도 없이 그냥 sort()를 쓰면 되기 때문이다.

3. 필요한 변수에 대해서는 변수명을 작성한다.

변수명과 제한 사항 메모

이미 필요한 변수에 대해 변수명이 주어졌다. 크게 배열 array와 [i, j, k]를 원소로 가진 2차원 배열 commands 두 개다. 추가적으로 코드를 작성하면서 필요한 배열은 그때그때 만들기로 했다. 지금 보니 1 ≤ commands ≤ 50이 아니라 1 ≤ len(commands) ≤ 50다.. 자주 하는 실수^^..

4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.

def solution(array, commands):
	answer = []
    
    # commands의 길이만큼 반복
      # 1. array에서 i번째부터 j번째까지 자르기
      # 2. 1에서 나온 배열 정렬
      # 3. 2에서 나온 배열의 k번째 숫자 추출하여 answer에 담기 return answer

예전에는 바로 코딩하곤 했는데, 의사 코드를 작성하고 코딩하는 게 훨씬 시간을 절약할 수 있으므로 먼저 의사 코드를 작성하여 틀을 잡는다. 이때 작은 예시에서 큰 예시로 확장하는 것이 좋다.

테스트 케이스

예를 들어 현재 테스트 케이스에 commands를 보면 3개의 [i, k, j]가 들어있는데, 이 3개에 대한 반복문을 작성하기 전에 한 개의 [i, k, j]에 대해 먼저 작성해보는 것이다. 그리고 그것을 3개로 확장하는 것이 훨씬 더 쉽고 편하다. 이게 바로 분할 정복 알고리즘이다^_^☆

5. 의사 코드에 맞춰 구현한다.

def solution(array, commands):
	answer = []
    
    # commands에서 command 꺼내오기
    for command in commands:
    	i = command[0]
        j = command[1]
        k = command[2]
        
        # 1. array에서 i번째부터 j번째까지 자르기
        new_array = array[i-1:j]
        
        # 2. 1에서 나온 배열 정렬
        new_array.sort()
        
        # 3. 2에서 나온 배열의 k번째 숫자 추출하여 answer에 담기
        answer.append(new_array[k-1])
        
	return answer

의사 코드를 작성하는 것이 어렵지, 막상 작성하고 나면 구현은 껌이다. 시키는 대로 하면 된다! 그런데 코드로 구현하면서 의사 코드가 변경된 부분이 있다. 원래 4번째 줄에 '# commands에서 command 꺼내오기'가 아니라 '# commands의 길이만큼 반복'이었는데 for i in range(len(commands))를 쓰려고 보니 i 변수명이 중복되어 다른 변수명을 생각해보다가 직관적이지 않아 아예 for command in commands로 바꿨다. 즉, commands의 길이만큼 인덱스로 배열을 순회하는 것이 아니라 commands에서 배열을 꺼내오는 것으로 변경했다.

다른 사람의 풀이

---

*다른 사람의 풀이는 좋아요 가장 많은 순으로 3개씩 볼 예정!

....?

이게 한 줄 표현이 가능하다고...? 충격적.. 일단 직관적이지 않아서 파이참을 켜서 코드를 분석해보았다.

map 함수를 사용해서 commands에 대해 lambda 함수를 쓰고 그걸 list로 다시 만든 것까지 OK. 그러면 이제 저 lambda 함수의 정체를 파악해야 했다. sorted(array[x[0]-1:x[1]])[x[2]-1]에서 x에는 commands가 들어가니까 commands를 대입하면 sorted(array[commands[0]-1:commands[1]])[commands[2]-1]가 된다. 여기서 commands[0]은 i, commands[1]은 j, commands[2]는 k이므로 다시 바꾸면 sorted(array[i-1:j])[k-1]이다. 이제야 내 코드랑 비슷해졌다.

처음부터 이렇게 짜는 게 가능할까? ㅋㅋㅋㅋ 아마 만들어 놓고 줄이고 줄인게 아닐까...? 아무튼 map 함수와 lambda 함수를 사용하여 간단하게 구현했다. 이 두 함수는 정말 사용하기는 어렵지만 제대로 사용하면 코드가 너무 간단해져서 볼 때마다 신기한듯..

오오오오 언패킹

언패킹을 생각 못했다. 여기서 또 한 수 배워갑니다^^ i, j, k = command 한 줄이면 끝날 것을 세 줄로 작성했군. 게다가 내가 #1~3에 걸쳐 세 줄로 작성한 코드도 한 줄로 만드셨다. 생각해보니 sort 함수를 이용해 array를 정렬하고 new_array라는 새로운 변수에 할당할거면 그냥 처음부터 sorted 함수를 사용하면 되네...? 뭐한거지ㅋㅋㅋㅋ

나랑 가장 비슷한 코드

나랑 거의 비슷한데 9~11번째 줄이 다르다. i랑 j가 같으면 원소 하나만 가져오기 때문에 슬라이싱이 아니라 인덱싱을 사용했다. 오, 하긴 원소 하나만 가져올거면 정렬할 필요도 없겠구나. 나랑 거의 비슷해보이지만 훨씬 효율적인 코드였다...!

개념 정리

---

정렬 알고리즘을 생각할 필요도 없이 sorted 함수를 사용하면 되므로 생략! 참고로 파이썬의 정렬 함수인 sorted()와 list.sort()는 팀정렬(Tim Sort)이라고 한다. 데이터의 정렬된 정도에 따라 삽입정렬(Insertion Sort)과 병합정렬(Merge Sort) 사이를 전환하는 적응형 알고리즘이다.

오늘 깨달은 점을 정리하면서 마무리하자.
-map과 lambda는 마법의 함수^^
-언패킹하면 한 줄이면 끝남!

-sort 함수는 정렬만, sorted 함수는 정렬한 후 반환까지!

코드

---

leeejihyun/algorithm

출처

---

프로그래머스 코딩 테스트 연습 https://programmers.co.kr/learn/challenges
[python] 파이썬의 정렬, Tim Sort https://ssungkang.tistory.com/entry/python-파이썬의-정렬-Tim-Sort