[프로그래머스] 체육복 (파이썬) python

| 문제설명

|제한사항

|입출력의 예

 

|코드

def solution(n, lost, reserve):
    number = {}
    for i in range(1, n+1) :
        if i in lost :
            number[i] = 0
            if i in reserve :
                number[i] = 1
        elif i in reserve :
            number[i] = 2
        else :
            number[i] = 1
    lost = []
    for key in number:
        if number[key] == 0 :
            lost.append(key)
    reserve = []
    for key in number :
        if number[key] == 2 :
            reserve.append(key)
    for j in range(len(reserve)):
        if reserve[j] -1 > 0 and number[reserve[j] -1] == 0  :
            number[reserve[j]] = 1
            number[reserve[j]-1] = 1
        elif reserve[j] +1 <= n and number[reserve[j]+1] == 0  :
            number[reserve[j]] = 1
            number[reserve[j]+1] = 1
    answer = []
    for key in number :
        if number[key] >= 1 :
            answer.append(number[key])
        
    return len(answer)

 

|코드설명

**Greedy Algorithm 그리디 아라고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는데, 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 알고리즘 기법이다. 이렇게 각 단계에서 한 최선의 선택이 전체적으로도 최선이길 바라는 것이다.**

 

**Greedy Algorithm 문제는 처음 접해봐서 사실 아직도  어떤 개념인지는 애매모호하다.. 각 단계에서 최선을 고려하면서도 전체의 효율성을 생각해야하는데, 지금 고안한 방법이 현재 단계에서도 최선인지 어떻게 아는건지도 잘 모르겠다..**

 

내가 생각한 방법은 전체학생 리스트의 맨 왼쪽부터 시작하는 for문을 돌면서, 해당변수가 reserve의 원소일때 왼쪽->오른쪽->의 순서로 lost의 원소가 있는지 판별해서 여벌 체육복을 나누어주는 방식이다.

우선 lost와 reserve 모두에 속해있는 원소는 가지고있는 옷이 1개이기 때문에 두개의리스트에서 모두 지워야한다.

따라서 number라는 빈 딕셔너리를 선언한 뒤, 그 안에 1부터 n가지의 학생들이 가지고있는 체육복개수를 매칭해준다.

lost에 속해있으면서 reserve에 없으면 0, reserve에 속해있으면서 lost에 없으면  2, 아무것도 아니면 1이다.

다음으로 lost와 reserve의 교집합원소를 제외한 리스트를 새로 생성해준다.

다음으로 for문으로 number를 돌면서 해당하는 key의 value값이 reserve의 원소일 이고,

해당 key 왼쪽key의 value값이 0보다크고 lost에 속해있을 때,

여벌의 체육복을 나누어주고 두개의 key값의 value값을 모두 1로 바꿔준다.

만약 위의 왼쪽 조건을 만족하지 않는다면, 오른쪽 key의 value값을 확인한뒤 n보다 작거나 같고 lost에 속해있으면,

여벌의 체육복을 나누어주고 두개의 key값의 value값을 모두 1로 바꿔준다.

그리고 number의 밸류값이 1 이상인 원소의 갯수를 세어준다.