[프로그래머스] Level 1_ 체육복

유형

탐욕법(Greedy)

 

문제

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

코딩테스트 연습 - 체육복

 

나의 문제풀이

1) 실패

  - 여벌 체육복을 가져온 학생이 체육복 도난당한 경우 고려하지 않음

def solution(n, lost, reserve):
    cnt = 0

    for i in range(len(lost)):
        for j in range(len(reserve)):
            if lost[i] == (reserve[j]-1) or lost[i] == (reserve[j]+1):
                cnt += 1
                del reserve[j]
                break
        
    return n - (len(lost) - cnt)

 

 2) 실패 (정확성 - 85.0)

def solution(n, lost, reserve):
    cnt = 0

    for i in range(len(lost)):
        for j in range(len(reserve)):
            if lost[i] == reserve[j]:
                cnt += 1
                del reserve[j]
                break
            elif lost[i] == (reserve[j]-1) or lost[i] == (reserve[j]+1):
                cnt += 1
                del reserve[j]
                break
        
    return n - (len(lost) - cnt)

 

 3) 실패 (정확성 - 90.0)

  - 질문하기 참고해서 lost, reserve sort

def solution(n, lost, reserve):
    cnt = 0
    
    lost.sort()
    reserve.sort()

    for i in range(len(lost)):
        for j in range(len(reserve)):
            if lost[i] == reserve[j]:
                cnt += 1
                del reserve[j]
                break
            elif lost[i] == (reserve[j]-1) or lost[i] == (reserve[j]+1):
                cnt += 1
                del reserve[j]
                break
        
    return n - (len(lost) - cnt)

 

4) 성공 (+13)

 - 제한사항 미스. '여벌 체육복을 가져온 학생이 도난당할 수 있다. 단, 다른 학생에게 체육복 빌려줄 수 없다.'

• 차집합 이용해서 여벌 체육복 가져온 학생이 도난당할 수 있는 경우 제외. 

https://hashcode.co.kr/questions/960/%EB%91%90-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%A5%BC-%EB%B9%84%EA%B5%90%ED%95%B4%EC%84%9C-%EC%84%9C%EB%A1%9C-%EC%97%86%EB%8A%94-%EC%9B%90%EC%86%8C%EB%A7%8C-return%EB%B0%9B%EC%9C%BC%EB%A0%A4%EA%B3%A0-%ED%95%A9%EB%8B%88%EB%8B%A4

두 리스트를 비교해서 서로 없는 원소만 return받으려고 합니다

 - 정렬 후에 하나씩 비교해가면서 여벌 체육복 빌려주기

• 빌려준 경우 cnt 1개 증가, temp_reverse에서 제외 

def solution(n, lost, reserve):
    cnt = 0
    
    # 여벌 체육복 가져온 학생 도난 당했을때
    temp_lost = list(set(lost) - set(reserve))
    temp_reserve = list(set(reserve) - set(lost))
    
    temp_lost.sort()
    temp_reserve.sort()

    for i in range(len(temp_lost)):
        for j in range(len(temp_reserve)):
            if temp_lost[i] == (temp_reserve[j]-1) or temp_lost[i] == (temp_reserve[j]+1):
                cnt += 1
                del temp_reserve[j]
                break
        
    return n - (len(temp_lost) - cnt)

 

 

다른 사람들의 문제풀이

 1) lost와 reverse 같은 값 있는지 미리 비교

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

 

 2) 모든 학생을 비교하는 방법

def solution(n, lost, reserve):
    answer = 0
    for i in range(1, n+1):
        if i not in lost: #안 잃어버린 학생
            answer += 1
        else:
            if i in reserve: #잃어버렸지만 여분도 있는 학생
                answer += 1
                reserve.remove(i)
                lost.remove(i)

    for i in lost: #잃어버리고 여분도 없어서 빌려야 하는 학생
        if i-1 in reserve:
            answer += 1
            reserve.remove(i-1)

        elif i+1 in reserve:
            answer +=1
            reserve.remove(i+1)

    return answer