체육복 (greedy)

체육복

문제)

• n, lost, reserve 가 주어지고, n이 최대인 값을 구하라.
• lost와 같은 reserve이면, 기능이 없으므로 미리 중복 제거
• reserve에 있는 값이 lost보다 -1, +1 차이이면, lost와 함께 제거할 수 있다.

제출)

• set간의 -(차집합) 연산으로 간편하게 중복제거 후의 값을 다시 대입할 수 있었다.

• 반복문에서 순환의 범위가 되는 자료 자체를 pop(), remove(), add() 등으로 증감하면
  index out range 가 나거나, 검색 범위를 검색하지 않을 수도 있으니 주의하자.

  • 2중 반복문에서 reserve.pop() 이후 break 되어, 다시 줄여진 범위내에서 만큼만 검색

def solution(n, lost, reserve):

    # Set
    s_lost= set(lost)
    s_res = set(reserve)
    # 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다.
    # -> lost && reserve는 제외
    lost = list(s_lost - s_res)
    reserve = list(s_res - s_lost)

    len_lost = len(lost)

    for i in range(len(lost)):
        for j in range(len(reserve)):
            #앞/뒤 찾으면 len_lost에서 줄여주고, reserve에서는 뺀다.
            if lost[i]-1 == reserve[j]:
                len_lost -=1
                reserve.pop(j)
                break
            elif lost[i]+1 == reserve[j]:
                len_lost -=1
                reserve.pop(j)
                break
            
    return n - len_lost

추가한 테스트케이스

    # [3, 5]      [4]
    # [1, 5]      [3, 6, 7, 8, 9]
    # [2, 4, 5]   [3, 6, 7, 8, 9]