[탐욕법(Greedy)] Level 1 체육복 - 파이썬

전에 c++로 풀었던 적이 있는 문제여서 파이썬으로만 풀어보았다

근데 알고리즘이 또 생각이 안나서 결국 내가 구현한 코드를 참고해서 풀었다,,,씨,,,

다른 사람들 풀이를 보니까 다들 엄청 깔끔하게 풀었던데,,,

난 내 코드가 직관적이라 좋다ㅠㅠ

 

 

def solution(n, lost, reserve):
    answer = 0
    student = [1 for i in range(n)]
    
    for i in range(len(lost)):
        student[lost[i]-1] -= 1
        
    for i in range(len(reserve)):
        student[reserve[i]-1] += 1
        
    for i in range(n):
        if student[i]==2:
            if i != 0 and student[i-1]==0:
                student[i-1] = 1
                student[i] = 1
                
        if student[i]==2:
            if i != n-1 and student[i+1]==0:
                student[i+1] = 1
                student[i] = 1
    
    for i in range(n):
        if student[i] >= 1:
            answer += 1
    return answer

나는 일단 학생 수 만큼 배열을 만들고, 리스트를 모두 1로 초기화한다 -> 체육복 개수

그리고 lost와 reserve 리스트 크기만큼 반복하면서 lost는 -1, reserve는 +1해준다

그리고 다시 학생 수만큼 반복하면서 만약 현재 학생이 체육복이 2개면 앞에 먼저 확인해서 앞에 없으면 빌려주고, 다시 또 확인해서 2개면 뒤에 없는 학생이 있으면 빌려주는 식으로 구현했다

그리고 다시 반복문을 돌면서 체육복이 1개 이상 있는 학생 수를 센다

대충 시간복잡도가 O(3n)정도 드는 것 같다,,

사실 이것도 결국 O(n)이라 효율성은 나쁘진 않을지도..?

다른 사람 코드는 이해가 가지 않는다,,

걍 나만의 코드를 짜는게 중요한 것 같다!

처음부터 안된다고 실망하지 말고 꾸준히 해보자!!