본문 바로가기
Python/알고리즘문제

[프로그래머스][탐욕법(그리디)] 체육복

by 붕어사랑 티스토리 2021. 4. 1.
반응형

programmers.co.kr/learn/courses/30/lessons/42862

 

코딩테스트 연습 - 체육복

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번

programmers.co.kr

해설

  • 각 학생이 가지고 있는 체육복의 수를 dictionary를 이용하여 만든다
  • 각 요소를 오른쪽 방향으로 순회한다.
  • 체육복을 한개 이상 들고 있을시 왼쪽 학생먼저 체육복이 없을경우 빌려주고 그다음으로 오른쪽 학생을 체크 한다.
def solution(n, lost, reserve):
    answer = n
    mydict = {}
    for i in range(1,n+1):
        mydict[i] = 1
    for i in reserve:
        mydict[i] += 1
    for i in lost:
        mydict[i] -= 1
        if mydict[i] == 0:
            answer -= 1
    for i in reserve:
        left = i - 1
        right = i + 1
        if mydict[i] > 1 and left > 0 and mydict[left] == 0:
            mydict[left]+=1
            mydict[i]-=1
            answer += 1
        if mydict[i] > 1 and right < n and mydict[right] == 0:
            mydict[right]+=1
            mydict[i]-=1
            answer+=1
    
    return answer

 

 

반응형

댓글