체육복 (Greedy - 1)

이것저것 따져보니 고려할 사항 없이, 여벌을 가져온 학생 왼쪽번호 학생이 잃어버렸으면 오른쪽 잃어버린 학생보다 먼저 주는 방식으로 하면 된다.

 

자꾸 테스트셋 3개가 틀려서 문제를 다시 보았더니, 여벌을 가져온 학생이 도난당할 경우가 있다는 조건이 있었다.

따라서 맨 처음에 이 경우를 발견해서 제거해주고, (answer의 증가에 영향 안 미치도록 조치해준다)

그 뒤에 옷을 나누어주며 answer를 더해간다.

answer의 초기값은 ( 전체 학생 수 - 잃어버린 학생 수 ) 이다.

 

이 문제를 보면서 Greedy Algorithm이라는 생각은 잘 안든다..

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()
    answer = n - len(lost)
    
    
    for i in range(len(reserve)): #여벌 잃어버린 사람 처리
        for j in range(len(lost)):
            if lost[j] == reserve[i]:
                reserve[i] = -10 #제외시키기 위해 의미없는 값 대입
                lost[j] = -1 #제외시키기 위해 의미없는 값 대입
                answer += 1
                
    
    for i in range(len(reserve)): # 무조건 왼쪽 먼저 사람 주는 걸로
        for j in range(len(lost)):
            if lost[j] == reserve[i] - 1:
                lost[j] = -1
                answer += 1
                break
            elif lost[j] == reserve[i] + 1:
                lost[j] = -1
                answer += 1
                break
            if lost[j] >= reserve[i] +2: #수행 시간 줄이기 위해
                break
    return answer

 

 

집합을 이용한 풀이도 눈여겨볼만하다.