[Algorithm] 프로그래머스 - 제일 작은 수 제거하기

시작하며...

모든 알고리즘 문제 풀이는 제가 직접 짜서 정답을 맞춘 결과만을 공유합니다.

마지막 'More Solution'은 다른 정답자들 풀이 중 생각지 못했던 부분들이나 좋게 느껴진 풀이법 몇개를 가져와서 공유하였습니다.

 

[Level 1] 제일 작은 수 제거하기

프로그래머스

 

문제 설명

정수를 저장한 배열, arr 에서 가장 작은 수를 제거한 배열을 리턴하는 함수, solution을 완성해주세요. 단, 리턴하려는 배열이 빈 배열인 경우엔 배열에 -1을 채워 리턴하세요. 예를들어 arr이 [4,3,2,1]인 경우는 [4,3,2]를 리턴 하고, [10]면 [-1]을 리턴 합니다.

제한 조건

• arr은 길이 1 이상인 배열입니다.
• 인덱스 i, j에 대해 i ≠ j이면 arr[i] ≠ arr[j] 입니다.

입출력 예

 

My Solution

def solution(arr):
    if len(arr) == 1:
        return [-1]
    else:
        tmp = arr[0]
        tmp_idx = 0
        for i in range(1, len(arr)):
            if tmp > arr[i]:
                tmp = arr[i]
                tmp_idx = i
        del arr[tmp_idx]
        return arr

오늘 풀이한 문제중 가장 생각이 많았던 문제, 다른 풀이 보면서 생각이 더 깊어진 문제

문제 자체는 그렇게 어렵지 않았다.

• 최소값 추출 후 빈 리스트 -> 길이가 1인 리스트라는 말이므로 주어진 리스트의 길이가 1일 경우 [-1]을 리턴
• 리스트의 처음부터 검색을 시작한다. 최소값을 저장할 변수 tmp와 tmp의 인덱스를 저장할 변수 tmp_idx를 초기화
• 1부터 주어진 리스트의 길이만큼 반복문을 돌면서 tmp와 i번째의 값의 크기를 비교해서 arr[i]가 더 작을 경우 tmp에 다시 저장, tmp_idx 에 인덱스값 i를 저장하는 반복문을 구현
• 반복문 종료 후 최소값 인덱스인 tmp_idx 를 del 함수를 이용해 제거하고 arr 을 리턴

 

More Solution

def solution(arr):
    if len(arr) == 1:
        return [-1]
    else:
        return [i for i in arr if i > min(arr)]

이 풀이법은 구버전 풀이법이라 return -1을 하는 경우는 제외되어있어 추가되었다. 

그럼에도 내가한 풀이를 한줄로 깔끔하게 풀어낸 풀이라서 가져와보았다.

min( ) 메소드와 List Comprehension을 이용해 한줄로 구현한 코드라서 대단하다고 생각했는데, 이 풀이의 댓글을 보니 min( ) 메소드 또한 리스트 크기만큼 반복하여 찾는것이기 때문에 시간복잡도가 증가해서 비효율적인 코드라고 한다. 

아직 시간복잡도를 계산하는 것을 잘 하지 못해서 부족하지만...for 문 안에 min( )이 있어서 O(n^2) 이 되는건가 싶다.

한줄로 깔끔해보이기는 하지만 효율성 측면에서는 내 코드가 시간복잡도 면에서는 좋은 것인가?

공부할 게 더 늘어만 간다...

 

def solution(arr):
    if len(arr) == 1:
        return [-1]
    else:
        arr.remove(min(arr))
        return arr

추가로 소개할 풀이!

리스트의 최소값을 remove 해주는 방법으로 풀이하였다.

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges