[알고리즘] 프로그래머스 Level 1 - 체육복

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

10 / 50(NEW!)

 

탐색

12 / 50

 

기초 동적 프로그래밍

10 / 50

---

투포인터

2 / 10

 

이분탐색

0 / 10

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

→ 코딩테스트 연습 > 탐욕법(Greedy)에 해당하는 문제

---

문제 해결 아이디어

여별의 체육복을 가지고 있는 학생들이 앞 학생에게 체육복을 주고, 

없으면 뒷 학생들에게 체육복을 주는 방식으로 구현

→ 문제에서 여별의 체육복을 들고 있는 학생이 도난당할 수도 있음

주의해야 할 것이, 여별을 들고 있는 학생도 앞 뒤로 주게 되면 더 좋게 나오는 경우도 있다.

그러나 문제에서 그런 경우 무조건 자기꺼는 자기가 쓰라고 함.

그래서 처음에 그러한 경우를 제거해야 한다.

 

풀이 시에는 python의 집합을 사용해서 in과 remove 시에 O(1)을 보장하도록 하였다.

---

구현

내 풀이

def solution(n, lost, reserve):
    # 여벌 체육복 가져온 학생이 도난당한 경우 제거
    _lost = set(lost)
    _reserve = set(reserve)

    lost = _lost - _reserve
    reserve = _reserve - _lost

    # 앞 -> 뒤 순으로 체육복 빌려주기
    for r in reserve:
        if r - 1 in lost:
            lost.remove(r - 1)
        elif r + 1 in lost:
            lost.remove(r + 1)
    
    return n - len(lost)

---

메모

• 걸린 시간: 1시간

---

마치며

약 한달 만에 알고리즘 포스팅..ㅠㅠ

다시 아ㅏ자자ㅏ자