[코딩 테스트] 프로그래머스 - 체육복 (Lv.1) in Python

전체 학생 수 n,

체육복 없는 학생들 번호가 담긴 배열 lost,

여벌의 체육복 가져온 학생들의 번호 담긴 배열 reserve가 주어질 때,

체육수업을 들을 수 있는 학생의 최댓값을 return

~> 단, 여벌의 체육복은 바로 앞이나 뒤의 학생에게만 빌려줄 수 있다.

 

프로그래머스 수업 내용을 토대로 작성한 코드들.

 

programmers.co.kr/learn/courses/30/lessons/42862

 

해결법

탐욕법 (Greedy) 사용!

각 단계에서 최적의 선택을 함. 현재 단계의 최적해가 문제 전체의 최적성을 해치지 않으면 됨.

 

Python 구현

방법 1

def solution(n, lost, reserve):
    li = [1] * (n+2)
    
    for i in lost:
    	li[i] -= 1
    for i in reserve:
    	li[i] += 1
        
    if li[i-1] == 0 and li[i] == 2:
    	li[i-1:i+1] = [1,1]
    elif li[i] == 2 and li[i+1] == 0:
    	li[i:i+2] = [1,1]
        
    answer = len([x for x in li[1:-1] if x>0])
    return answer

여분이 있으면 체육복의 수 = 2,

잃어버렸음 체육복의 수 = 0

 

연달아 있는 번호끼리만 체육복을 주고받을 수 있으므로,

리스트를 탐색하면서 값을 도출한다.

 

헛깨비로 맨 앞과 맨 뒤에 1을 넣어줌.

(예외 처리 줄이기 위함)

 

여벌을 가져온 학생 처리: reserve길이에 비례

체육복을 잃어버린 학생 처리: lost길이에 비례

체육복 빌려주기 처리: 전체 학생 수 (n)에 비례

~> 복잡도: O(n)

 

 

방법 2

n은 너무 큰데 lost가 너무 작으면 메모리의 낭비가 일 수 있다.

이 방법은 정렬 때문에 알고리즘 복잡도가 O(n log n)이 되지만, 위의 경우 더 도움되는 방법

def solution(n, lost, reserve):
	# 교집합
    inter = set(lost).intersection(set(reserve))
    
    # 체육복 여분 있는 학생들만
    reserve = set(reserve) - inter
    
    # 체육복 잃어버린 학생들만
    lost = set(lost)- inter
    
    for x in sorted(reserve):
    	if x-1 in lost:
        	lost.remove(x-1)
        elif x+1 in lost:
        	lost.remove(x+1)
        
    answer = n - len(lost)
    
    return answer

 

메모

- 방법 2의 set 사용이 흥미롭다. 강사님은 조금 다른 방법으로 교집합을 구하셨는데, 나는 더 흔한 a.intersection(b)가 더 편했다.

 

- set은 정렬되지 않은 원소의 집합이다. 그래서 sorted()를 쓰는 것이 생소했는데,

list의 메소드인 .sort()와는 달리,

sorted()는 iterable objects에 모두 적용된다고 한다.

 

sorted()

참고 - docs.python.org/3/howto/sorting.html

 

- 키를 지정해서 원하는 방식으로 sorting하는 것도 가능하다.

 

- operator 모듈의 itemgetter()와 attrgetter()를 이용하면 더 쉽게 가능하다.

~> itemgetter() : 지정하는 곳의 item을 가져온다.

~> attrgetter(): 지정하는 곳의 attribute를 가져온다.

 

참고 - docs.python.org/3/library/operator.html#operator.itemgetter

 

 

class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age
    def __repr__(self):
        return repr((self.name, self.grade, self.age))
        
        
student_objects = [
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
]

라고 했을 때, 나이 순으로 sort하는 방법 세 가지가 다음과 같다.

from operator import itemgetter, attrgetter

sorted(student_objects, key=lambda student: student.age)   # sort by age
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

sorted(student_tuples, key=itemgetter(2))
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

sorted(student_objects, key=attrgetter('age'))
# [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]