[Greedy][programmers]탐욕법 lv1 체육복

1. 문제

학생들의 번호 : 체격 순서 (바로 앞 또는 바로 뒤의 학생에게만 체육복을 빌려줄 수 있다.)

2. 이해

 

입력

 

• 전체 학생의 수 : n
• 체육복 X 학생들의 번호가 담긴 배열 : lost
• 여벌 체육복 O 학생 번호가 담긴 배열 : reserve

 

 

출력

return 체육 수업을 들을 수 있는 학생의 최댓값

 

 

조건

• 1 < n < 31 (n은 자연수)
• 1<= 체육복X 학생의 수 <= n, 중복 번호X
• 여벌 체육복O인 학생만 다른 학생에게 체육복을 빌려줄 수 있음
• 여벌 체육복O인 학생도 도난당할 수 있음. 무조건 1개만 도난당함 + 체육복 1개 남음(대여 불가상태로 변환)
  • lost와 reserve에 중복 소속 가능 (1순위 체크)

 

 

예시

n	lost	reserve	return
5	[2, 4]	[1, 3, 5]	5
5	[2, 4]	[3]	4
3	[3]	[1]	2

 

3. 접근

 

#그리디 알고리즘 -> 전수 조사
1. lost와 reserve에 중복 소속된 번호 조사 -> 중복O이면 lost, reserve에서 제거 및 lost, reserve를 갱신
2.  reserve의 모든 번호를 +-1 하여 can_rend list 만들기 (for문)
3. best can_rend list 찾기
4. answer =  n - # of lost

 

4. 구현

 

try 1: 65점, fail

 

의도 : 선택된 번호가 가장 많은 알고리즘

구현 : 

1. lost 리스트의 모든 번호에 대해서 선택되지 않는 번호 중 앞번호 선택
2. lost 리스트의 모든 번호에 대해서 선택되지 않는 번호 중 뒷번호 선택
3. choice_list가 최대인 경우의 수 찾기

실제:

뒷번호, 앞번호에게 빌리는 경우를 각각 따로 계산해서 greedy하지 않음.

 

try1 :

채점 결과

정확성: 65.0

합계: 65.0 / 100.0

 

 

def solution(n, lost, reserve):
    answer = 0
    
    # 중복 번호 검사 -> 제거
    for lnum in lost:
        for rnum in reserve:
            if lnum == rnum:
                lost.remove(lnum)
                reserve.remove(rnum)
    
    # can_rend list의 모든 경우의 수
    # len(lost)가 최소인 best_can_rend list 찾기
    
    
    
    can_rend_list = []
    before_list = []
    after_list = []
    for rnum in reserve:
        if 1 == rnum:
            before_rnum = rnum 
        else :
            before_rnum = rnum - 1
        
        if rnum == n:
            after_rnum = rnum
        else:
            after_rnum = rnum + 1
        
        # can_rend_list.append([before_rnum,after_rnum])
        before_list.append(before_rnum)
        after_list.append(after_rnum)
    
    
    # afeter/before_list의 index = 체육복 빌려주는 주체
    # afeter/before_list의 value = 체육복 빌리는 객체
    
    # index는 중복 x
    # index는 한번만 선택
    
    
    # 이건 그리디 하지 않아!! 예외없이 경우의수 전수조사하는 알고리즘 짜기!
    # 65점
    max_choice = -9999
    for lost_num in lost:
        choice_list = []
        if lost_num in before_list and lost_num not in choice_list:
            choice_list.append(before_list.index(lost_num))
        
        
        if lost_num in after_list and lost_num not in choice_list:
            choice_list.append(after_list.index(lost_num))
        
        if  len(choice_list) > max_choice:
             max_choice = len(choice_list)   

        
        answer = n - len(lost) + max_choice


    return answer

 

• 빌릴 수 있는 경우의 수를 미리 계산하는 것은 불필요
• 중복을 제거하기 위해 이미 빌린

after_list, berfore_list 제거

 

try2 :

채점 결과

정확성: 85.0

합계: 85.0 / 100.0

 

def solution(n, lost, reserve):
    answer = 0
    
    # 중복 번호 검사 -> 제거
    for lnum in lost:
        for rnum in reserve:
            if lnum == rnum:
                lost.remove(lnum)
                reserve.remove(rnum)

    choice_list = []
    # max_choice = -9999
    for lost_num in lost:
        
        print("lost_num : ",lost_num)
        print(reserve)
        print(choice_list)
        if lost_num - 1 in reserve:
            choice_list.append(lost_num)
            reserve.remove(lost_num - 1)
            print(lost_num,"이",lost_num-1,"에서 빌림")
        elif lost_num + 1 in reserve:
            choice_list.append(lost_num)
            reserve.remove(lost_num + 1)
            print(lost_num,"이",lost_num+1,"에서 빌림")
            
        
        # print(choice_list)
    answer = n -len(lost) + len(choice_list)

    return answer

 

• 중복 검사 부분에서 반복문이 돌아가는 도중에 list가 변경되면 뭔가 문제가 생길 것 같다
  • iterater 부분 공부 필요!
• 오답 : 테스트 7, 13, 14 번 

 

 

try3 : 

채점 결과

정확성: 90.0

합계: 90.0 / 100.0

 

def solution(n, lost, reserve):
    answer = 0
    
    # 중복 번호 검사 -> 제거
    for lnum in lost[:]:
        for rnum in reserve[:]:
            if lnum == rnum:
                lost.remove(lnum)
                reserve.remove(rnum)
                break
    
                
    choice_list = []
    for lost_num in lost:
        
        print("lost_num : ",lost_num)
        print(reserve)
        print(choice_list)
        if lost_num - 1 in reserve[:]:
            choice_list.append(lost_num)
            reserve.remove(lost_num - 1)
            print(lost_num,"이",lost_num-1,"에서 빌림")
        elif lost_num + 1 in reserve[:]:
            choice_list.append(lost_num)
            reserve.remove(lost_num + 1)
            print(lost_num,"이",lost_num+1,"에서 빌림")
            
        
        # print(choice_list)
    answer = n -len(lost) + len(choice_list)

    return answer

 

문자열 슬라이싱으로 배열 전체를 슬라이싱하여 복사했다.

테스트 7를 맞혔다.

• 오답 : 테스트 13, 14 번 

 

try4: pass

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

def solution(n, lost, reserve):
    answer = 0
    # 이전번호, 다음번호로 접근하기 위해선 정렬 필수
    lost = sorted(lost)
    reserve = sorted(reserve)
    # 중복 번호 검사 -> 제거
    
    # 반복문 안에서 반복하는 대상이 바뀌면 의도와 다르게 동작할 수 있음 -> copy, 리스트 슬라이싱으로 전체 복사 등

    # O(N^2)? O(NlogN)?
    for lnum in lost[:]:
        for rnum in reserve[:]:
            if lnum == rnum:
                #remove는 공간복잡도 O(N)이라 안좋음. 다른 방식 찾아보기
                lost.remove(lnum)
                reserve.remove(rnum)
                break
    
                
    choice_list = []
    for lost_num in lost:
        
        print("lost_num : ",lost_num)
        print(reserve)
        print(choice_list)
        
        #왼쪽에서 빌릴 수 있으면 빌리기
        if lost_num - 1 in reserve[:]:
            choice_list.append(lost_num)
            reserve.remove(lost_num - 1)
            print(lost_num,"이",lost_num-1,"에서 빌림")
        
        # 빌릴수 없으면 오른쪽에서 빌리기
        elif lost_num + 1 in reserve[:]:
            choice_list.append(lost_num)
            reserve.remove(lost_num + 1)
            print(lost_num,"이",lost_num+1,"에서 빌림")
            
        
        # print(choice_list)
    answer = n -len(lost) + len(choice_list)

    return answer

 

번호가 순서대로라는 조건이 없었다.

왼쪽 보고 없으면 오른쪽에서 빌린다는 조건이 성립하려면 순서대로 들어와야한다.

lost = sorted(lost)

reserve = sorted(reserve)

추가 후 통과

 

탐욕법이 성립하려면 빌릴 수 있으면 빌려야한다.

 

1. lost와 reserve를 정렬하여 '순서대로' (이전 번호, 다음 번호 관계 성립의 전제 조건)
2. lost와 reserve : 중복 제거
3. 이전 번호에서 빌릴 수 있으면 빌리기
4. 다음 번호에서 빌릴 수 없을 때, 오른쪽에서 빌릴 수 있으면 빌리기

 

팁

간단하게 도식화 할때

체육복의 개수를 사용하여 경우의 수를 고려하는 것이 유용

체육복 없음 : 0

체육복 1개 : 1

체육복 reserve : 2

 

예제 1의 n=5, lost = [2,4] , reserve = [1, 3, 5]의 경우

 

 

2 0 2 0 2 로 생각하면 다른 케이스를 생각할 때 좋다.

(번호 순서대로 1 2 3 4 5 이다.)