[프로그래머스] 체육복 파이썬

https://school.programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

 

프로그래머스 고득점키트 탐욕법의 Level1 문제이다.

 

1. 배열을 이용한 풀이방법

2. 집합과 정렬을 이용한 풀이방법

 

전체 학생수가 n명이고, 도난당한 학생 수가 k 명이라면

첫 번째 방법은 O(n)으로 답을 구할 수 있고, 두 번째 방법은 정렬을 사용하기 때문에 O(klogk)로 구할 수 있다.

 

위 문제는 전체 학생수가 30명이라서 어느 방법으로 풀던 상관없지만, 만약 n이 충분히 크다고 가정하면

 

전체 학생 수와 도난당한 학생 수가 크게 차이가 나지 않는다면 첫번째 방법을 사용하는 것이 좋고

전체 학생 수에 비해 도난당한 학생 수가 적다면 두번째 방법을 사용하는 것이 좋다.

---

1. 배열을 사용한 문제

def solution(n, lost, reserve):
    students = [1]*(n+2)
    for i in reserve:
        students[i] += 1
    for i in lost:
        students[i] -= 1

    for i in range(1,n+1):
        if students[i] == 2 and students[i-1] == 0:
            students[i] = students[i-1] = 1
        if students[i] == 2 and students[i+1] == 0:
            students[i] = students[i+1] = 1
    return len([s for s in students[1:-1] if s > 0])

 

초기 students 배열은 학생 번호에 따른 체육복 수로 1로 초기화해준다. n+2로 초기화한 이유는 후에 체육복을 빌려주는 과정의 코드를 작성할 때, 시작과 끝에서 예외처리를 간단하게 하기 위해 여분의 크기로 초기화했다.

 

3번째라인에서 6번째까지 lost와 reserve를 고려해서 체육복 수를 할당했는데, 이때 여분의 체육복을 가지고있는데 도난당한 경우 체육복 개수를 1로 만들었기 때문에 체육복을 빌려줄 수 없다는 조건을 지킬 수 있다.

 

탐욕법으로 접근하려면, 빌려주는 순서를 고려해야하는데, 여분 체육복을 가진 학생을 앞쪽부터 탐색한다면 마찬가지로 그 학생은 바로 앞의 학생부터 잃어버린 학생에게 체육복을 빌려줘야한다.

 

왜냐하며면 여분을 가진 학생이 2, 4, 6번이고 도난당한 학생이 1, 3, 5번일 때

 

만약 2번이 바로 앞 학생인 1번이 아닌 3번학생부터 빌려주면 4번 학생은 5번 학생에게 빌려줄 수 밖에 없고, 6번 학생은 여분의 체육복을 가지고 있지만 빌려줄 수 없기 때문에 여분의 체육복을 빌려줄 때 앞 쪽 학생부터 고려해야 한다.

2. 집합과 정렬을 사용한 풀이

def solution(n, lost, reserve):
    l, r = set(lost) - set(reserve), set(reserve) - set(lost)
    for x in sorted(r):
        if x-1 in l:
            l.remove(x-1)
        elif x + 1in l:
            l.remove(x+1)
    return n-len(l)

 

reserve의 시간복잡도가 k일 때, sorted(r)에서 시간복잡도가 O(klogk)이다. 그리고 set 자료형은 포함여부를 판단할 때 시간복잡도가 O(1)이기 때문에 전체 시간복잡도는 O(klogk)이다.