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

프로그래머스

---

n 명의 학생이 있고, 학생들은 고유 번호가 있다. 근데 학생들 중 몇 명은 체육복을 도난당했다. 여벌이 있는 학생은 체육복을 빌려 줄 수 있다.

근데 체육복을 빌려주는 것은 바로 앞번호(i - 1) 또는 뒷번호(i + 1)만 빌려줄 수 있다. 체육복이 있어야 체육 수업을 들을 수 있다고 했을 때, 최대 몇 명까지 들을 수 있을까?

---

아이디어

학생 번호를 인덱스로 하는 리스트를 1로 초기화해 준다. 

그리고 여벌이 있는 학생은 +1, 도난당한 학생은 -1 해준다. 

 

그리고 반복문으로 리스트를 순회하며 도난당한 학생 양 옆에 여분이 있는 학생이 있는지 체크해 준다.

있으면 두 사람의 체육복 개수를 1로 바꿔 준다.

 

마지막에 리스트의 체육복 개수가 0개인 학생 수를 count 해서 n값에서 빼주고 정답을 return 해준다.

---

전체 코드

def solution(n, lost, reserve):
    
    Arr = [1] * (n + 2)
    
    for r in reserve:
        Arr[r] += 1
    
    for l in lost:
        Arr[l] -= 1
    
    for i in range(1, n + 1):
        if Arr[i - 1] == 0 and Arr[i] == 2:
            Arr[i - 1], Arr[i] = 1, 1
        elif Arr[i] == 2 and Arr[i + 1] == 0:
            Arr[i], Arr[i + 1] = 1, 1
    
    answer = n - Arr.count(0)
    return answer

---

코드 설명

Arr = [1] * (n + 2)
    
for r in reserve:
    Arr[r] += 1

for l in lost:
    Arr[l] -= 1

먼저 학생의 체육복 개수를 담을 리스트 Arr를 선언해 준다. default값은 1로 설정해 준다. 그리고 나중에 있을 연산의 편의성을 위해 1번과 n번 양 끝에 하나씩 추가해 리스트 크기를 n + 2로 선언해 준다. (0, 1, 2, 3... n - 1, n, n + 1) 

 

그리고 reserve와 lost에 있는 학생 번호를 확인하여 Arr에 있는 체육복 개수를 조절해 준다.

 

    for i in range(1, n + 1):
        if Arr[i - 1] == 0 and Arr[i] == 2:
            Arr[i - 1], Arr[i] = 1, 1
        elif Arr[i] == 2 and Arr[i + 1] == 0:
            Arr[i], Arr[i + 1] = 1, 1
    
    answer = n - Arr.count(0)

for문으로 Arr를 순회하며 여별의 체육복을 빌려주는 조건을 확인해 준다. 조건을 만족하면 값을 1로 바꿔준다.

 

최종적으로 Arr에 있는 원소중 값이 0인 것들을 count 해서 n값에서 빼주면, 문제에서 요구하는 정답이 된다.

 

---

다른 방법 - set 이용

def solution(n, lost, reserve):
    
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    
    for k in sorted(r):
        if (k - 1) in l:
            l.remove(k - 1)
        elif (k + 1) in l:
            l.remove(k + 1)
    
    return n - len(l)

도난이랑 여벌은 상쇄된다. 이를 바탕으로 집합을 활용해 문제를 해결할 수 있다.

 

문제에서 주어진 lost와 reserve의 교집합 s를 구해준다.

그리고 lost와 reserve 집합에서 s의 원소들을 제외시켜 준다. 

 

그리고 여벌이 있는 학생들의 집합 r을 순회하며 앞뒤(k - 1, k + 1)에 도난당한 학생이 있는지 확인해 준다.

있으면 그 학생은 집합 l에서 제외시켜준다. 

 

앞의 풀이와 유사하게 n에서 집합 l의 원소 개수를 빼주면 된다.