문제를 보고 어떻게 접근 하면 되겠다 라고 바로 생각은 들었지만 그것을 코드로 바로 구현하는 구현력이 많이 떨어진다는걸 느끼게 되는 문제였다.
이 문제를 풀기 위해 하나하나 리스트에 인덱싱을 뺴가면서 풀려했더니 도저히 진전이 되지 않아서 구글링을 해보았다. 구글링을 하던 도중에 알게된 블로그인데 엄청나게 설명을 잘해주셔서 북마크에 추가까지 했다.. ( 감사합니다 )
여기서 알게된 내용은 이렇다. 먼저, greedy algorithm ( 탐욕 알고리즘 ) 에 대한 부분을 알게 되었다.
탐욕 알고리즘이란, 탐욕 알고리즘이란 매순간 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법.
이 부분에 탐욕 알고리즘에 대한 부분을 정리하자면 너무 길어지니 따로 글을 작성해보도록 하겠다.
그동안 나는 백준 알고리즘 문제 조금 풀거나 크롤링이나 셀레니움 위주로 사용을 했어서 이런 알고리즘 문제 풀이에는 아직 많이 미숙함을 느낀다. 머릿속으로는 대충 그림은 그려지지만 어떻게 문제를 풀어가야할지 몰라 결국 구글링을 하게된다.
접근 방법
- 체육복을 도난 당한 학생의 번호는 중복되지 않는다.
- 여벌의 체육복을 가져온 학생의 번호도 중복되지 않는다.
- 여기서 알수 있는건 서로 중복되는 학생의 번호가 없다는것이다.
- 추가로 중요한 부분은 여벌의 체육복을 가져온 학생도 체육복을 도난 당했을수도 있다. ( 여벌의 체육복까진 도난 당하진 않음 )
- 먼저 집합을 이용해서 중복되는 값을 제거한다
- 차집합을 이용하여 도난 당한 학생과 여벌의 체육복을 가져온 학생의 중복을 제거해준다.
- greedy algorithm 을 이용하여 최적의 방법으로 도난 당한 학생에게 여벌의 체육복을 빌려주는 방법을 탐색해본다.
def solution(n, lost, reserve):
result_reserve = set(reserve) - set(lost) # 집합을 이용하여 중복값 제거후 차집합
result_lost = set(lost) - set(reserve)
for i in result_reserve: # 여분의 체육복이 있는 학생의 왼쪽부터 탐색
if i-1 in result_lost:
result_lost.remove(i-1) # 왼쪽학생이 잃어버렸다면 도난 당한 학생 집합에서 제거
elif i+1 in result_lost: # 왼쪽 학생이 안 잃어버렸다면 오른쪽학생탐색
result_lost.remove(i+1)
return n-len(result_lost) # 전체 학생수에서 체육복 못빌린 학생 수만큼 뺸 값을 return
왼쪽부터 탐색했던 이유
왼쪽을 먼저 빌려주는 방법을 택하지 않고 오른쪽 먼저 주는 방법을 택했다면 오른쪽은 받지만 왼쪽은 못받는 경우가 생긴다. 하지만, 왼쪽을 먼저 탐색하고 오른쪽을 탐색하는 방법을 택하면 완벽하게 문제를 해결할수있다.
이 문제를 통해 느낀건 탐욕 알고리즘에 대해 알게된점, 그리고 집합이 꽤나 유용하게 사용된다는점이다. 특히나 집합도 remove를 이용하여 값을 제거 할수 있다는것도 꽤나 흥미로운 문제였다. 틈틈히 탐욕 알고리즘에 대해 복습하여 절대 잊어 버리지 않도록 해야겠다.
문제 푸는데 큰 도움을 주신분 = https://rain-bow.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%B2%B4%EC%9C%A1%EB%B3%B5
지금은 구글링을 통해 많이 도움 받고 있지만 나도 많이 성장해서 배운 만큼 베풀고싶다!!
