문제.
https://programmers.co.kr/learn/courses/30/lessons/42862
레벨 1이지만 얻어갈 게 많은 문제라고 생각한다.
이전에 푼 적이 있는데 다시 풀어보니 틀리더라..🤦🏻♀️ 강의 듣고 보니 놓친 부분들이 꽤 존재한다.
📌 아래 강의 참고:
https://programmers.co.kr/learn/courses/9877
접근 방식
강의에서는 두가지 접근 방식을 제안한다.
- 방법 1. 번호 순서대로 스캔하면서 체육복을 빌려줄 수 있는 학생을 찾아서 처리하기
1) 1로 초기화한 길이 n+2의 배열을 만든다. 왜 n+2냐면 코드 구현의 편의성을 위해 맨 앞과 맨 뒤를 가짜로 세워두는 것이다. (코드를 보면 이해가 더 편할 것이다)
2) reserve를 돌면서 해당 번호의 숫자를 하나 늘린다.
3) lost를 돌면서 해당 번호의 숫자를 하나 줄인다.
- 방법 2. 여벌의 체육복을 가져온 학생들을 정렬 후 순회하면서 lost을 찾아 처리하기
두가지 방식의 알고리즘 시간복잡도를 비교한 부분이 흥미로웠다.
언뜻 생각했을 때는 방법2가 더 스마트하고 효율적이라고 생각했는데, 상황에 따라 비교를 해보니 그렇지도 않더라👀
두가지 방식의 코드
- 방법 1
#방법1. 전체 유니폼 목록 기록 -> O(n)
def solution1(n, lost, reserve):
uniform = [1] * (n + 2)
for r in reserve:
uniform[r] += 1
for l in lost:
uniform[l] -= 1
#이러면 아예 체육복이 없는 학생은 0, 체육복이 여벌로 있는 학생은 2인 uniform 배열이 된다.
for i in range(1, n + 1):
if uniform[i-1] == 0 and uniform[i] == 2:
uniform[i-1], uniform[i] = 1, 1
elif uniform[i] == 2 and uniform[i+1] == 0:
uniform[i], uniform[i+1] = 1, 1
return len([u for u in uniform[1:-1] if u > 0])- 방법 2
#방법2. set의 활용으로 포함 여부를 확인하는 방식 -> O(k log k)
def solution2(n, lost, reserve):
s = set(lost) & set(reserve) #교집합
l = set(lost) - s
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)시간복잡도 비교
n은 전체 학생 수, k는 reserve의 길이
-
방법 1의 경우 :
O(n)
👉 n을 순회하며 reserve를 확인하기 때문에 n에 linear한 시간복잡도를 가진다. -
방법 2의 경우 :
O(k log k)
👉 k를 sort하여 바로 집합에 속하는지 아닌지 확인하는 방식이기 때문에, 정렬에O(k log k), reserve를 순회하며 처리하는 방식은O(k)*O(1)이다
방법1 vs. 방법2
n이 얼마 크지 않거나, n과 k가 비슷한 수준이면 방법1이 적합하다.
반면, n이 굉장히 크거나 k가 그에 비해 훨씬 작다면 방법 1은 낭비적인 방법이 될 것이다. (n이 10000000라면?)
🤔 n에 linear하게 하나하나 순회한다고 치면 시간을 훨씬 많이 잡아먹고 + 그 와중에 k가 별로 없다면 낭비이기 때문
그땐 방법2가 적합하다!
내가 놓친 부분
나는 방법2로 접근했었다. 다만 reserve를 sort할 생각을 못했는데, 단순히 lost의 포함 여부만 생각했기 때문이다.
그러나 reserve를 sort하는 게 굉장히 중요한 부분이다. 왜냐하면 lost 포함여부를 조회하는 순서가 존재하기 때문이다.
코드를 보면 1. 앞번호, 2. 뒷번호 순으로 조회하는데, 이 때문에 아래와 같은 경우 곤란해질 수 있다:
r = [5, 3, 1]
l = [2, 4, 6]
이 경우, 5는 4에게 빌려주고, 3은 2에게 빌려줄 것이다. 그러므로 사실 최적해인 1-2, 3-4, 5-6을 만족하지 못한다. (앞이 reserve, 뒤가 lost 짝)
결국, 오름차순 정렬이 방법2의 포인트였다.
