[algorithm] 페어 - 프로그래머스: 체육복

 

이 문제를 풀기 전에 먼저 알아두자

 

그리디 알고리즘!

greedy algorithm은 탐욕 알고리즘 또는 욕심쟁이 알고리즘

눈 앞에 보이는 단계에서 최선의 선택을한다.

= 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법

 

각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 것.

 

 

 

 

완전한 답 도출 못함: 

 

일단 풀이 작성

 

1번 풀이

def solution(n, lost, reserve):
    # 여벌옷 + 도난 검사 
    for l in lost[:]:      #lost의 요소 변화로 인한 오류
        if l in reserve: 
            lost.remove(l)

    lost.sort() 
    reserve.sort()

    for l in lost[:]: #lost의 요소 변화로 인한 오류
        if l - 1 in reserve:
            lost.remove(l)
            reserve.remove(l - 1)
        elif l + 1 in reserve:
            lost.remove(l)
            reserve.remove(l + 1)
                    
    answer = n - len(lost)
    return answer

 

2번 풀이

def solution(n, lost, reserve):
    
    # lost, reverse 에서 같은 요소 점검 및 정렬
    for l in lost[:]:
        if l in reserve: 
            lost.remove(l)
    lost.sort() 
    reserve.sort()

    # 옷 유무, 여벌 여부 점검해 list 요소 변경
    stu_list = [1 for i in range(n)]
    for idx, stu in enumerate(stu_list):  #여기서 idx는 0 ~ n-1
        if idx + 1 in lost:
            stu_list[idx] = 0
        elif idx + 1 in reserve:
            stu_list[idx] = 2

    # idx값으로 양옆을 검사하여 옷 빌릴 수 있는지 확인
    for idx in range(n):
        #맨 앞 맨 뒤 오류 예외처리
        if stu_list[idx] == 0:
            if idx == 0:
                if stu_list[idx+1] == 2:
                    stu_list[idx] = 1
                    stu_list[idx+1] = 1
            elif idx == n-1:
                if stu_list[idx-1] == 2:
                    stu_list[idx] = 1
                    stu_list[idx-1] = 1
                
            else:
                if stu_list[idx-1] == 2:
                    stu_list[idx] = 1
                    stu_list[idx-1] = 1
                elif stu_list[idx+1] == 2:
                    stu_list[idx] = 1
                    stu_list[idx+1] = 1
    stu_list = [s for s in stu_list if s > 0]
    answer = len(stu_list)
    return answer

두 풀이 모두 같은 테스트에서 실패를 겪는다.  테스트 1, 2, 3, 5, 6, 9, 10, 12, 24

 

 

 

 

 

\