[Python] 프로그래머스 그리디 문제 (체육복, 단속 카메라, 큰 수 만들기, 기지국 설치)

1. 문제 - 프로그래머스 체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

 

❓해당 문제가 그리디인 근거

1) 최대한 많은 학생에게 체육복을 빌려주어야한다 --> "최대 이익" 키워드

2) 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다 --> 잃어버린 학생과 여벌이 있는 학생을 둘다 정렬함으로써, 빌려줄 수 있는 체육복을 순차적으로 빌려주는 것이 곧 최대 이익을 보장한다

def solution(n, lost, reserve):
    _reserve = sorted([r for r in reserve if r not in lost])   # 1
    _lost = sorted([r for r in lost if r not in reserve])      # 2
    
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

 

- #1, #2에서 _reserve는 lost 배열에 있는 원소 배제, _lost는 reserve 배열에 있는 원소를 배제하는 이유는

"여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있습니다. 이때 이 학생은 체육복을 하나만 도난 당햇다고 가정하며, 남은 체육복이 하나익에 다른 학생에게는 체육복을 빌려줄 수 없습니다" 라는 조건을 보면 된다.

- 여벌이 있는 학생이 잃어버리면 빌려줄 수 없으니 해당 학생은 lost, reserve 두 배열에서 모두 제외한다.

- "앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있다" 조건에서, 빌려줄 수 있는 학생이 앞서서 먼저 빌려줌으로써 최적해를 보장하기 위해 정렬한다. (sorted)

- 이후 여벌이 있는 학생의 앞번호, 뒷번호가 잃어버린 학생 목록 중 있으면 해당 학생에게 빌려줌으로써 lost 배열에서 제외한다.

- 체육수업을 들을 수 있는 학생은 전체에서 체육복을 잃어버린 학생의 수를 빼주면 된다.

 

2. 문제 - 프로그래머스 큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

 

❓해당 문제가 그리디인 근거

1) k개의 수를 제거하여 가장 큰 숫자를 만들어야한다 --> "최대값" 키워드

2) 매순간 바로 이전의 수보다 더 큰수를 선택하는 것이 최대값을 보장한다 --> 그 순간의 최선의 선택이 정답을 보장함

def solution(number, k):
    stack = [number[0]]
    number = list(number)
    
    for n in number[1:]:
        while stack and stack[-1] < n and k: # 1. 현재의 수가 이전 값들보다 가장 큰 값이 될때까지 수 제거함
            k -= 1
            stack.pop()
        stack.append(n)
    
    if k > 0:   # 2. 제거횟수 k를 모두 쓰지 않았을 경우, 앞에서부터 남은 k회를 제외한 길이만큼으로 수를 만드는 것이 최대값을 보장함
        stack = stack[:len(number)-k]
            
    return "".join(stack)

 

1) 입출력 예시 두번째인 "1231234", 3, "3234"의 케이스를 보자.

- 가장 최근의 값들과 현재의 수를 비교한다는 점에서 스택 자료구조를 떠올릴 수 있다. (스택은 선입후출 구조이므로, 값들을 넣으면서 가장 최근 값들과 비교하기 적절한 자료구조)

- 1, 2에서 2가 1보다 더 크므로 k에서 제거횟수 소진 및 1 제거, 2,3에서 3이 2보다 더 크므로 k에서 제거횟수 소진 및 2를 제거한다.

.. 이런식으로 한다음에 stack에 남아있는 수들을 모두 합친 것이 정답이다.

 

2) 예외적으로 k번을 모두 소진하지 않는 경우의 수가 있다. 테스트케이스 4의 "4321", 1을 보면 된다.

- 4321은 계속 감소하므로 위 로직에 의하면 한번도 제거하는 경우가 없다. 즉, k회 제거하지 않는다.
- 이 경우에는 이미 stack에 있는 수들이 가장 큰 수를 만드는 조건에 부합하는 수들만 존재하므로, 뒤에서 k회 자르면 된다. 즉 앞에서 len(number) - k만큼 자르는것이 최대값을 보장해주게 된다.

 

3. 문제 - 프로그래머스 기지국 설치

❓해당 문제가 그리디인 근거

1) 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값 --> "최적의 해를 보장하는 최소값" 키워드

2) 매순간 최적의 위치에 기지국을 설치함으로써 최적의 해를 보장함 (뒤의 선택에 영향을 주지 않음)

def solution(n, stations, w):
    idx = 0     # 기지국이 설치되어있는 인덱스
    location = 1   # 현재 위치
    answer = 0
    
    while location <= n:
        if idx < len(stations) and location >= stations[idx] - w:  # 전파가 닿아있는 범위를 보면 건너뛰어야함
            location = stations[idx] + w + 1
            idx += 1
        else:     # 기지국이 설치되어 있지 않은 위치인 경우
            answer += 1
            location += 2 * w + 1  # 해당 기지국을 설치함으로써 전파가 닿지않는 범위로 이동
            
    return answer

- 기지국을 최소로 설치하되 모든 아파트에 전파가 통하게 하려면, 최대한 겹치지 않게 설치하는 것이 중요하다.

- 따라서 이미 기지국이 설치되어 전파가 통하는 곳은 통하지 않는 곳으로 이동하고, 그때마다 전파를 설치하는 방식을 통해 모든 아파트가 전파가 통할 수 있도록 한다.

 

4. 문제 - 프로그래머스 단속카메라

def solution(routes):
    routes.sort(key=lambda x: x[1])  # 진출 지점 기준 정렬
    prev_camera = -30001  # 이전에 설치한 카메라 위치
    answer = 0

    for start, end in routes:
        if start > prev_camera:
            answer += 1          # 새 카메라 필요
            prev_camera = end    # 현재 차량의 진출 지점에 카메라 설치

    return answer

 

- "모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지" --> 가장 많이 겹치는 구간에 카메라를 설치해야한다.

- 그럼 겹치는지 어떻게 알까? --> 진출 시점(end)을 기준으로 정렬한 다음, 각 진입 시점이 이전 진출 시점 범위 이내에 있는지 확인하면된다.

1) 먼저 prev_camera를 -30001로 설정하는 이유는, 첫번째 차량은 비교 범위가 없으므로 먼저 하나 설치하기 위해 범위를 벗어나는 값으로 설정한다.

2) 그리고 이후 진출 시점을 갱신하면서 start 지점과 비교하게 되는데, 예시를 풀어쓰면 다음과 같다.

1. 진출 시점으로 정렬:

[[-20, -15], [-18, -13], [-14, -5], [-5, -3]]

2. 처음엔 비교 대상이 없으므로 -15 지점에 카메라 설치 (answer+1), 후 prev_camera를 -15로 갱신
3. 이후 -15와 -18 비교. 진출 시점을 기준으로 오름차순 정렬이니
start가 prev_camera보다 작거나 같을 경우 이전에 설치한 카메라 범위와 겹친다고 가정할 수 있다.
그러므로 이때는 Pass
4. 이후 -15와 -14 비교. 이 때는 카메라 범위가 닿지 않으니 [-14, -5]의 진출 시점인 -5에 카메라를 새로 설치한다. (answer+1)
그리고 prev_camera값을 진출 시점인 -5로 갱신한다.
5. 이후 -5와 -5 비교. 이때는 이전 진출 시점인 -5에 설치한 카메라의 범위에 닿으므로 pass
6. 최종적으로 answer는 2

 

새로 알게된 점

1. 배열에서 특정 원소 제거 - remove(원소), 인덱스 제거 - del 배열[인덱스] or 배열.pop(인덱스)

- pop은 반환값 있음

2. 가장 최근의 수를 비교하거나 이전의 값들을 기억하거나 처리해야하는 경우, 스택을 고려하자