[프로그래머스] level 1 - 체육복 (탐욕법)

def solution(n, lost, reserve):
    answer = 0
    
    size_min = 0
    save = set([])
    Re_set = set([])
    
    for i in reserve:
        Re_set.add(i)
   
    for i in Re_set:
        for j in lost:
            if i==j:
                lost.remove(j)
                reserve.remove(i)

    size_min = n - len(lost)

    for i in reserve:
        for j in lost:
            if i+1 == j or i-1 == j:
                save.add(j)
                break

    answer = size_min+len(save)
    return answer

 

---

이문제에서 고려해야 할 조건은 여분의 체육복이 있는학생과 잃어버린 학생이 같은 경우 이다.

사실 집합의 속성을 이용해서 문제를 풀어보려 했는데 하다보니까 코드 방향이 바뀌어졌다.

그냥 리스트로 해결했어도 될것같다.

 

첫번째로 생각했던 것은 전체 학생수에서 잃어버린 학생수를 제외한 나머지는 무조건 수업을 듣는다. 였다.

그래서 size_min 을 정의하여 최소한의 학생수를 먼저 구했고,

나머지는 조건에 명시된대로 앞뒤의 학생중 조건에 부합하는 학생만을 추가하여 더하는 방식으로 풀이했다.

 

그리고 그전에 여분의 체육복이있는 학생들을 새로운 집합안에 넣어 for문을 돌릴 집합을 만들어두고,

잃어버린 학생과 여분의 체육복이있는 학생이 같다면 각각의 리스트에서 중복값을 제거했다.

만약, 새로운 집합을 정의하지 않고 그대로 reserve 리스트를 for문으로 넣어 연산을 진행하면, 결과값이 다르게 나온다.

 

 for i in Re_set:
        for j in lost:
            if i==j:
                lost.remove(j)
                reserve.remove(i)

 

여기서 Re_set 과 reserve 의 초기값은 같지만 연산이 진행되면 달라진다.

연산을 진행하면 for문이 제대로 실행되지않기때문에 반드시

for문에 영향을 주지 않도록 새롭게 정의를 한 집합이나 리스트가 필요하다.

 

이부분만 체크하고 알고리즘을 짜면 쉽게 풀어낼수 있다.