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

아이디어 : 바로 앞뒤만 빌려줄 수 있음.reserve와 lost에 겹치는 사람있는지를 먼저 체크.

일단 한쪽 방향으로만 체크하는걸 생각했다.

 

# 첫 번째 시도

def solution(n, lost, reserve):
    for i in range(len(lost)-1,-1,-1):
        if lost[i] in reserve:
            reserve.remove(lost[i])
            del lost[i]
    for j in range(len(reserve)):
        if reserve[j]-1 in lost:
            lost.remove(reserve[j]-1)
        elif reserve[j]+1 in lost:
            lost.remove(reserve[j]+1)

    answer = n-len(lost)
    return answer

 

18번 20번을 제외하고 나머지는 통과이다.

 

# 두 번째 시도

 

어떤 경우를 빼먹은 걸까?

 

왼쪽or오른쪽부터 탐색하는 경우에 빠뜨릴 수 있는 경우가 발생한다. 예를 들면, 오른쪽으로 먼저 탐색한다고 하였을 때 5,[2,4],[3,5]였을 경우, 3일때에 4를 먼저 제외하게 되고, 5일 경우에는 제외할 수 있는 경우가 사라지게 된다. 따라서 실제로 답은 5임에도 불구하고 이 경우 4인 것으로 잘못 나올 수 있다.

 

그럼 어떻게 해결할까?

 

def solution(n, lost, reserve):
    for i in range(len(lost)-1,-1,-1):
        if lost[i] in reserve:
            reserve.remove(lost[i])
            del lost[i]
    
    remove_list = []
    for j in range(len(reserve)):
        if reserve[j]-1 in lost:
            remove_list.append(reserve[j]-1)
        if reserve[j]+1 in lost:
            remove_list.append(reserve[j]+1)

    remove_list = set(remove_list)
    count = min(len(remove_list),len(reserve))
    answer = n-len(lost)+count
    return answer

 

# 세 번째 시도 (성공)

 

양쪽에 lost가 있는 경우와 한 쪽에만 있는 경우를 고려했다.

def solution(n, lost, reserve):
    for i in range(len(lost)-1,-1,-1):
        if lost[i] in reserve:
            reserve.remove(lost[i])
            del lost[i]
    
    remove_list = []
    remove_only = []
    for j in range(len(reserve)):
        if reserve[j]-1 in lost and reserve[j]+1 in lost:
            remove_list.append(reserve[j])
        elif reserve[j]-1 in lost:
            remove_only.append(reserve[j])
            lost.remove(reserve[j]-1)
        elif reserve[j]+1 in lost:
            remove_only.append(reserve[j])
            lost.remove(reserve[j]+1)

    for x in remove_only:
        reserve.remove(x)

    remove_set = set(remove_list)
    count = min(len(remove_set),len(reserve))
    answer = n-len(lost)+count
    
    return answer