문제
점심시간에 도둑이 들어 일부 학생이 체육복을 도난당함
여벌 체육복이 있는 학생이 이들에게 체육복을 빌려줄 것
학생들의 번호 = 체격순 그래서 바로 앞번호 학생 혹은 바로 뒷번호 학생에게만 체육복 빌려줄 수 있음. ex. 4번학생은 3번 혹은 5번학생에게만 빌려줄 수 있음
체육복 없으면 수업 못 들으니까 체육복 적절히 빌려주어 최대한 많은 학생이 체육수업을 듣도록 할 것
전체학생수 n과 도난당한 학생들 번호 담긴 배열 lost, 여벌의 체육복 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수
체육 수업 들을 수 있는 학생 최댓값을 return
<제한>
전체 학생 수 2명 이상 30명 이하
도난당한 학생 수 2명 이상 n명 이하 (중복 번호 x)
여벌 체육복 가져온 학생 수 1명 이상 n명 이하 (중복 번호 x)
여벌 체육복 있는 학생만 빌려줄 수 있음
여벌 체육복 가져온 학생이 체육복을 도난당했을 수도 있다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정. 남은 체육복 하나이기에 다른 학생에게 체육복 빌려줄 수 없다.
탐욕법(Greedy Algorithm)이란?
알고리즘의 각 단계에서 그 순간에 최적이라고 생각되는 것을 선택하는 방법
이 방법으로 최적해를 찾을 수 있는 문제는
현재의 선택이 마지막 해답의 최적성을 해치지 않을 때의 문제이다 = 지금 좋은게 나중에도 좋다
따라서 빌려줄 학생들을 "정해진 순서"로 살펴 "정해진 순서"에 우선하여 빌려줄 방향을 정해야 합니다.
앞번호를 빌려주는 방향부터 확인해야겠죠?
[방법1]
학생 수는 많아봤자 30명이기 때문에
학생 수 만큼 배열 확보 → 각자가 갖고 있는 체육복 수 기록
번호대로 스캔하며 빌려줄 관계 정함
<복잡도는 어떨까?>
여벌을 가져온 학생을 처리하는 것은 reserve 길이에 비례
체육복을 잃어버린 학생을 처리하는 것은 lost의 길이에 비례
체육복 빌려주기 처리는 전체학생 수 n에 비례
결국 O(n)의 복잡도를 가지게 될 것이다. 이정도면 훌륭한 알고리즘
[방법2]
만약 전체 학생수가 엄청 크면 1000만명이면? O(n)보다 낮은 복잡도 알고리즘은 어려울 것 같아요
그러나 여벌의 체육복을 가져온 학생이 매우 적으면
방법 1을 한다면 1000만의 길이를 갖는 리스트가 필요해지기 때문에 기억공간이 너무 많이 필요합니다.
그러면 여벌의 체육복을 가져온 학생들을 기준으로 살펴볼 수 있지 않을까?
⇒ 여벌의 체육복을 가져온 학생들의 번호를 정렬한 후 이것을 하나하나 순서대로 살펴보며 빌려줄 수 있는 다른 학생을 찾아 처리하는 방법 가능
<복잡도는 어떨까?>
•
여벌 체육복 학생 리스트 정렬 복잡도(여벌 가져온 학생 수 k명일 때) O(klogk)
•
빌려줄 수 있는 학생 찾아 처리하기 : hash적용 : (O(k) x O(1)
•
전체 알고리즘 시간복잡도 O(klogk)
풀이코드
[방법1]
def solution(n, lost, reserve):
cnt = [1] * (n+2)
for r in reserve:
cnt[r] += 1
for l in lost:
cnt[l] -= 1
for i in range(1, n+1):
if cnt[i] == 2 and cnt[i-1] == 0:
cnt[i] -= 1
cnt[i-1] += 1
elif cnt[i] == 2 and cnt[i+1] == 0:
cnt[i] -= 1
cnt[i+1] += 1
return len([x for x in cnt[1:-1] if x > 0])
Python
복사
for i in range(1, n+1): : O(n)의 복잡도
len([x for x in cnt[1:-1] if x > 0]) : O(n)의 복잡도
전체 복잡도 O(n)
[방법2]
set 자료구조를 사용
set 또한 dictionary처럼 해쉬테이블 구조로 이루어져 있음.
dictionary와 다른점은 key, value로 이뤄져있지 않고, 순서도 없으며, 그저 어떤 요소가 이 집합(set)에 속해 있느냐만 판단
def solution(n, lost, reserve):
s = set(lost) & set(reserve) # 합집합
# 여벌가지고 있다가 도난당한 학생 lost에서 제거(안빌려줘도 되니까)
l = set(lost) - s # 차집합
# 도난 당하면 여벌 없어져서 빌려줄 수 없으니까 도난당한 학생 reserve에서 제거
r = set(reserve) - s
for x in sorted(r): # 빌려줄 수 있는 학생들 기준 탐색
if x - 1 in l:
l.remove(x-1) # 빌려주고 체육복 없는 명단에서 제거
elif x + 1 in l:
l.remove(x+1)
return n - len(l) # 마지막까지 l에 남아있는 번호의 학생만 수업참여 못함 전체에서 빼준다.
Python
복사
sorted → O(k log k) (k는 r의 원소 수)
set만들 때 일반적으로 O(k)
in → list이므로 O(k)
in연산자의 시간복잡도
remove메소드 → O(f) (f는 l의 원소수)
전체복잡도 O(k log k)
n의 크기는 매우 크고 reserve의 크기는 상대적으로 작을 경우 효율적인 알고리즘
