알고리즘 고득점 Kit - 정렬

출처 : 프로그래머스 알고리즘 고득점 Kit - 정렬

 

k번째 수 Lv.1

# 내 풀이
def solution(array, commands):
    answer = []
    for _ in range(len(commands)):
        sorting = sorted(array[commands[_][0]-1:commands[_][1]]) # 부분 배열 정렬
        answer.append(sorting[commands[_][2]-1]) # 정렬된 부분에서 특정 값 추출
    return answer
   
# 시간 복잡도
# O(k * m log m) (각 commands[_]에 대해 정렬을 수행하고, 반복 횟수 k에 따라 결정)
# 공간 복잡도
# O(k + m) (결과를 저장하는 공간 answer와 정렬 과정에서 사용되는 임시 배열 공간)

# 개선된 코드
def solution(array, commands):
    return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands))

 

원래 코드 vs. 수정된 코드

1. 시간 복잡도 비교

• 첫 번째 코드:
  • 시간 복잡도: O(k * m log m)
  • sorted()를 사용하여 각 부분 배열을 정렬한 후, 결과를 추출합니다.
• 두 번째 코드:
  • 시간 복잡도: O(k * m log m)
  • 두 코드 모두 시간 복잡도는 동일합니다. 둘 다 sorted()를 사용하여 정렬하므로, 시간 복잡도에서 차이는 없습니다.

2. 공간 복잡도 비교

• 첫 번째 코드:
  • 공간 복잡도: O(k + m) (부분 배열을 정렬할 때마다 새로운 배열을 생성)
• 두 번째 코드:
  • 공간 복잡도: O(k + m) (마찬가지로 부분 배열을 정렬할 때마다 새로운 배열을 생성)

두 코드 모두 공간 복잡도는 동일하지만, 두 번째 코드에서는 map 함수와 lambda 함수를 사용하여 좀 더 함수형 프로그래밍 스타일로 작성되어 있습니다. map 함수는 이터레이터를 반환하므로 약간 더 메모리를 절약할 수 있는 여지가 있습니다.

 

※ 이터레이터 vs. 리스트

이터레이터는 map 함수의 결과로, 값이 필요할 때마다 순차적으로 생성하는 객체이다. 리스트, 튜플, 집합 등의 자료구조에서 요소를 하나씩 반환하는 방법을 제공한다. 모든 값을 한 번에 메모리에 저장하지 않고 요청된 정보만을 반환하기 때문에 메모리를 절약할 수 있다. 그러나 수정된 코드에서는 결과적으로 이터레이터를 list()함수로 감싸 모든 값을 리스트의 형태로써 메모리에 저장하였으므로 이전 코드와 공간 복잡도는 동일해진다.

파이썬 map 함수와 lambda 함수

파이썬에서 map 함수와 lambda 함수는 함께 자주 사용되며, 함수형 프로그래밍 스타일을 채택할 수 있게 도와줍니다. 이 두 기능을 잘 활용하면 코드를 더 간결하고 효율적으로 작성할 수 있습니다.

---

1. map 함수

map 함수는 반복 가능한(iterable) 객체의 모든 요소에 주어진 함수를 적용하는 함수입니다.
이 함수는 반복 가능한 객체의 각 항목에 대해 함수를 호출하고, 그 결과를 map 객체로 반환합니다. 이 결과는 이터레이터 형태로 나오며, 이를 리스트나 다른 자료형으로 변환할 수 있습니다.

문법

map(function, iterable)

• function: 각 요소에 적용할 함수
• iterable: 반복 가능한 객체 (리스트, 튜플 등)

예시

# 예시 1: 각 요소를 제곱하는 함수 적용
numbers = [1, 2, 3, 4, 5]
result = map(lambda x: x**2, numbers)  # 각 숫자에 대해 제곱을 계산
print(list(result))  # [1, 4, 9, 16, 25]

위 예시에서는 map 함수가 numbers 리스트의 각 요소에 대해 lambda x: x**2라는 람다 함수를 적용한 결과입니다.

---

2. lambda 함수

lambda 함수는 익명 함수라고도 불리며, 이름 없이 간단한 연산을 수행하는 함수를 정의할 때 사용됩니다. 주로 한 번만 사용되는 간단한 함수에 유용합니다.

문법

lambda arguments: expression

• arguments: 함수에 전달할 인수들
• expression: 함수가 수행할 연산 (반환 값)

예시

# 예시 1: 두 수를 더하는 람다 함수
add = lambda x, y: x + y
print(add(3, 5))  # 8

lambda 함수는 return 키워드를 사용하지 않고, 한 줄로 표현된 함수입니다. 위 예시에서 lambda x, y: x + y는 x와 y를 더하는 함수를 정의한 것입니다.

---

3. map과 lambda의 결합 사용 예시

map 함수는 lambda 함수와 함께 자주 사용됩니다. lambda 함수로 인라인으로 작성된 간단한 함수들을 map으로 여러 데이터에 일괄 적용할 수 있기 때문입니다.

예시

# 예시 2: 각 숫자에 대해 3배를 곱하는 함수 적용
numbers = [1, 2, 3, 4, 5]
result = map(lambda x: x * 3, numbers)
print(list(result))  # [3, 6, 9, 12, 15]

이 예시에서는 map 함수가 numbers 리스트의 각 항목에 대해 람다 함수 lambda x: x * 3을 적용하여 결과를 반환합니다.

---

4. map 함수와 lambda 함수의 장점

• 코드의 간결성: lambda 함수와 map을 결합하면 별도의 함수 정의 없이 짧고 간결하게 코드를 작성할 수 있습니다.
• 고차 함수: map은 고차 함수로, 다른 함수(여기서는 lambda 함수)를 매개변수로 받아 처리합니다.
• 가독성: 복잡하지 않은 연산에 대해 코드를 간결하고 직관적으로 작성할 수 있습니다.

---

5. map 함수와 lambda 함수의 주의사항

• 반환 타입: map은 결과를 이터레이터로 반환하므로, 이를 list()나 tuple() 등으로 변환해야 결과를 확인할 수 있습니다.
• 성능: map은 for문에 비해 성능이 좋을 수 있지만, 너무 복잡한 함수나 중첩된 사용은 오히려 가독성을 떨어뜨릴 수 있습니다.

예시: map과 lambda를 사용하는 경우

# 예시 3: 두 리스트의 요소별로 더하는 예시
list1 = [1, 2, 3]
list2 = [4, 5, 6]

# lambda를 이용하여 두 리스트의 각 요소를 더함
result = map(lambda x, y: x + y, list1, list2)
print(list(result))  # [5, 7, 9]

이 예시에서는 map 함수가 두 개의 리스트(list1과 list2)에서 각 항목을 lambda 함수로 더하여 반환합니다.

---

결론

• map 함수는 반복 가능한 객체의 모든 요소에 대해 함수를 적용하고, 그 결과를 반환하는 함수입니다.
• lambda 함수는 간단한 연산을 익명으로 정의하는 함수입니다.
• map과 lambda를 결합하면 코드가 간결하고 효율적으로 작성됩니다.

 

가장 큰 수 Lv.2

 

 

def solution(numbers):
    str_numbers = list(map(str, numbers))
    sorted_numbers = sorted(str_numbers, key = lambda x:x*10, reverse=True)
    answer = ''.join(sorted_numbers)
    return "0" if answer[0]=="0" else answer
    
# 코드 설명 : 각 요소 문자열로 변환 -> 요소를 10글자씩 늘려 비교해 내림차순 정렬 -> 문자열 병합 ->
# '0000'같은 것이 출력될 수도 있으므로 예외 처리한 후 return 값 반환

# 개선한 코드
def solution(numbers):
    str_numbers = list(map(str, numbers))
    sorted_numbers = sorted(str_numbers, key = lambda x:x*3, reverse=True)
    return str(int(''.join(sorted_numbers)))
    
# 코드 설명 : numbers의 각 숫자는 1000을 넘지 않으므로 x:x*3으로 해도 충분. 
# 결과를 정수로 한 번 변환하는 과정을 거쳐 '0000' 등을 예외 처리해야 하는 번거로움을 줄임.

# 다른 풀이
import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) 
    #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

1️⃣ 시간 복잡도 비교

(1) functools 사용 버전

import functools

def comparator(a, b):
    t1 = a + b
    t2 = b + a
    return (int(t1) > int(t2)) - (int(t1) < int(t2))

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator), reverse=True)
    return str(int(''.join(n)))

시간 분석

• numbers를 문자열로 변환하는 연산 → O(N)O(N)
• sorted() 실행 → O(Nlog⁡N)O(N \log N)
  • 비교 연산(comparator)에서 두 문자열을 더하고 비교하는 과정이 있음.
  • 비교 함수가 O(1)O(1)이므로, 전체 정렬은 O(Nlog⁡N)O(N \log N).
• ''.join(n)으로 문자열을 합치는 연산 → O(N)O(N)
• 최종적으로 int() 변환 → O(1)O(1) (단순한 변환)

✅ 최종 시간 복잡도: O(Nlog⁡N)O(N \log N)

---

(2) lambda x: x * 3 사용 버전

def solution(numbers):
    n = list(map(str, numbers))
    n.sort(key=lambda x: x * 3, reverse=True)
    return str(int(''.join(n)))

시간 분석

• map(str, numbers) 실행 → O(N)O(N)
• sort() 실행 → O(Nlog⁡N)O(N \log N)
  • key=lambda x: x * 3는 각 요소를 3번 반복하여 비교하는 연산이므로 O(1)O(1)이지만,
    정렬 과정 자체는 O(Nlog⁡N)O(N \log N)
• ''.join(n) 실행 → O(N)O(N)
• 최종적으로 int() 변환 → O(1)O(1)

✅ 최종 시간 복잡도: O(Nlog⁡N)O(N \log N)

---

2️⃣ 공간 복잡도 비교

(1) functools 사용 버전

• n = [str(x) for x in numbers] → O(N)O(N) (입력 리스트를 문자열 리스트로 변환)
• sorted(n, key=functools.cmp_to_key(comparator)) → 정렬 과정에서 새로운 리스트가 생성됨 → O(N)O(N)
• ''.join(n) → 출력 문자열을 저장하는 공간이 필요 → O(N)O(N)
• 비교 함수 comparator는 추가적인 공간을 거의 사용하지 않음 (O(1)O(1))

✅ 최종 공간 복잡도: O(N)O(N)

---

(2) lambda x: x * 3 사용 버전

• n = list(map(str, numbers)) → O(N)O(N) (입력 리스트를 문자열 리스트로 변환)
• sort(key=lambda x: x * 3) → 내부적으로 sort()가 제자리 정렬을 수행하여 추가 공간을 사용하지 않음
  (파이썬의 .sort()는 Timsort 알고리즘을 사용하며, 최악의 경우에도 O(N)O(N) 추가 공간만 사용)
• ''.join(n) → O(N)O(N) (출력 문자열 저장)
• 비교 함수는 추가 공간을 사용하지 않음 (O(1)O(1))

✅ 최종 공간 복잡도: O(N)O(N)

---

📌 결론

방법 시간 복잡도 공간 복잡도

functools 사용 버전	O(Nlog⁡N)O(N \log N)	O(N)O(N)
lambda x: x * 3 사용 버전	O(Nlog⁡N)O(N \log N)	O(N)O(N)

📌 시간 복잡도는 두 방법 모두 O(Nlog⁡N)O(N \log N)로 동일.
📌 공간 복잡도는 두 방법 모두 O(N)O(N)로 동일하지만,

• functools를 사용하면 sorted()가 새로운 리스트를 반환하기 때문에 약간 더 많은 메모리를 사용할 가능성이 있음.
• sort()는 제자리 정렬(in-place sorting) 이므로 메모리를 약간 절약할 수 있음.

✅ 최적의 선택:

• 메모리를 조금 더 절약하고 싶다면 lambda x: x * 3 방식이 유리함.
• 비교 연산이 명확한 방식이 더 익숙하다면 functools 버전을 사용해도 무방함.

 

H-Index Lv.3

def solution(citations):
    citations.sort(reverse=True)
    n = len(citations)
    answer = 0
    for i in range(n):
        if citations[i]>=i+1:
            answer = i+1
        else:
            break
    return answer
    
    # 코드 설명 :

프로그래머스