프로그래머스, 체육복(greedy algorithm)

https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3

체육복을 도둑맞은 상황에서 체육복이 2개인 사람들이 체육복을 빌려주어서 체육 수업을 들을 수 있는 최대 학생 수를 구하는 문제다.

번호의 앞뒤로 빌려주는것만이 가능한 상황이라 조건문을 짜기 굉장히 까다로웠는데 이것을 어떻게 간단하게 바꿀 수 있을지 고민해봤다.
모든 경우의 수를 조건문으로 짜지 않고, 각 위치에서 앞에 사람이 빌려줄수있는 경우에 받기만 하면 그것이 최대값이 될 수 있다고 생각이 들어 코딩을 시작했다.

나의 코드

인덱스를 이용한 정직한 방법이다.

	cloth = [1 for _ in range(n)]
    for i in lost:
        cloth[i-1]-=1
    for i in reserve:
        cloth[i-1]+=1
    for i in range(1,n):
        if (cloth[i]==2 and cloth[i-1]==0) or (cloth[i]==0 and cloth[i-1]==2):
            cloth[i] = cloth[i-1] = 1
    answer = [c for c in cloth if c>0]
    return len(answer)

다른 사람의 풀이

파이썬의 효율적인 내장함수를 사용한 풀이이다. 좀 더 Pythonic 하지만 reserve 리스트가 정렬된 상태에서 작동하는 코드이므로 내 코드가 시간복잡도 면에서는 이득이지 않나 싶다...

	reserve.sort()
    new_reserve = [r for r in reserve if r not in lost]
    new_lost = [l for l in lost if l not in reserve]
    for r in new_reserve:
        front = r-1
        back = r+1
        if front in new_lost:
            new_lost.remove(front)
        elif back in new_lost:
            new_lost.remove(back)
    return n-len(new_lost)

좋은 웹페이지 즐겨찾기