프로그래머스 그리디 문제입니다.실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (해결X)

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

    clothes = []
    for i in range(n):
        if lost:
            if lost[0] == i+1:
                clothes.append(0)
                lost.pop(0)
                continue
        clothes.append(1)

    check_clothes = []

    for idx,cloth in enumerate(clothes):

        if cloth == 0:
            if reserve:
                if reserve[0] == idx+2 or reserve[0] == idx+1 or reserve[0] == idx:
                    check_clothes.append(1)
                    reserve.pop(0)

                elif reserve[0] < idx+1:
                    reserve.pop(0)

                check_clothes.append(0)
                continue
            check_clothes.append(0)
            continue
        else:
            check_clothes.append(1)


    return answer

문제를 이해하는데는 어렵지 않았지만 구현할 때 일부 케이스에서 실패하였습니다. closhes라는 객체에 현재 체육복을 가지고 있는 사람과 아닌 사람을 0과1로 표현하였습니다. 이후 reserve(여분의 체육복)을 확인하며 앞사람먼저 빌려주는 방식인데 여러 케이스에 대해 구현하기 어려워 다른 풀이를 참고하였습니다.🐸🐸🐸

[다른사람의 풀이1]

def solution(n, lost, reserve):

    new_lost = set(lost) - set(reserve)
    new_reserve = set(reserve) - set(lost)

    for i in new_lost:
        print(new_reserve)
        if i - 1 in new_reserve:
            new_reserve.remove(i + 1)
        elif i + 1 in new_reserve:
            new_reserve.remove(i - 1)
        else:
            n-=1

    return n

첫번째 포인트는 문제에서 언급하듯, 체육복을 잃어버렸을 때 자신의 체육복 여분이 있다면 스스로에게 우선적으로 채워넣는 다는 점입니다. 이를 set()-set()연산으로 자신의 여분으로 채웠을때 lost 리스트, reserve 리스트를 다시 만들어 준다는 점입니다.

두번째 포인트로, 저의 접근방식은 체육복을 갖고 있는 사람의 수를 세는 것이였다면 위 코드는 lost 리스트 (체육복을 잃어버린 사람들)에서 체육복을 빌릴 수 없을 때 전체 사람수-1씩 해주어 답을 도출해내는 점입니다. ( set() 객체를 for문으로 도는 점도 자주 쓰는 방식이 아니라 신기했습니다.)🐭🐭🐭

[다른사람의 풀이2]

def solution(n, lost, reserve):
    # 정렬
    lost.sort()
    reserve.sort()
	
    # lost, reserve에 공통으로 있는 요소 제거
    for i in reserve[:]:
        if i in lost:
            reserve.remove(i)
            lost.remove(i)
	
    # 체육복 빌려주기(나의 앞 번호부터 확인)
    for i in reserve:
        if i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
    
    return n-len(lost)

'다른사람의 풀이1'과 같은 방식이되 set()대신 list()객체로 구현한 모습입니다.

체육복 유무를 첫번째 사람부터 체크하기 위해 sort()를 해주었고, 체육복을 잃어버린 사람이 스스로 채워넣을 수 있을 때는 채워넣고, 체육복 빌려주는 상황이 가능할 때 잃어버린 사람 목록에서 제거하는 형태입니다.🐻🐻🐻

감사합니다.