알고리즘/프로그래머스 Programmers

[프로그래머스] 체육복 (Python)

한비 2023. 9. 4. 22:51
반응형
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

  • 전체 학생의 수는 2명 이상 30명 이하입니다.
  • 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
  • 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

입출력 예

n lost reserve answer
5 [2, 4] [1, 3, 5] 5
5 [2, 4] [3] 4
3 [3] [1] 2

 

입출력 예 설명

예제 #1

1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2

3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

풀이

이 문제의 키 포인트는 2개다.

  1. lost와 reserve에 중복되는 번호는 없음
  2. 여벌 체육복이 있는 학생이 체육복을 도난당했을수도 있음 → lost와 reserve에 동시에 속해있는 학생은 수업에 참여할 수는 있지만 다른 학생에게 체육복을 빌려줄 수는 없음

따라서 탐색 전에 lost와 reserve에 대해 동시에 속해 있는 번호를 제거해주어야 하고, 이때 각 집합은 중복되는 번호가 없으므로 set 자료형의 차집합으로 구할 수 있다.

lost와 remove의 교집합을 제거했다면, reserve를 순회하며 왼쪽 혹은 오른쪽에 있는 학생에게 체육복을 빌려줄 수 있는지 탐색하고 빌려줄 수 있다면 해당 학생을 lost set에서 제거한다. 참고로 set의 remove는 시간 복잡도가 O(1)이다 (list는 O(n)).

reserve가 빌려줄 수 있는 학생을 lost에서 모두 제거한 후 n에서 lost에 남아 있는 학생(체육복을 빌릴 수 없는 학생)의 수를 빼주면 정답이 된다.

def solution(n, lost, reserve):
    _lost = set(lost) - set(reserve)
    _reserve = set(reserve) - set(lost)
    for r in _reserve:
        if r-1 in _lost:
            _lost.remove(r-1)
        elif r+1 in _lost:
            _lost.remove(r+1)
    return n - len(_lost)

 

set 자료형 대신 list 자료형을 사용하여 차집합을 구하고 싶다면 다음과 같이 할 수 있다. 대신 이 경우 모든 테스트케이스를 통과하기 위해서는 정렬해줘야 하고, remove의 시간복잡도가 더 높아진다는 문제가 있다.

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    _reserve.sort()
    _lost.sort()
    for r in _reserve:
        if r-1 in _lost:
            _lost.remove(r-1)
        elif r+1 in _lost:
            _lost.remove(r+1)
    return n - len(_lost)

 

문제를 풀면서 헷갈렸던 것은 다음 3가지다.

 

1. lost와 reserve의 교집합을 꼭 미리 삭제해줘야 하나?

 처음에는 reserve에 대해 -1, 0, 1을 순차적으로 조회하는 코드를 작성했지만 에러가 났다. 먼저 다른 사람에게 체육복을 빌려줬는데 이후에 자신을 만난다거나 하는 등 순서가 꼬일 수 있기 때문이다.

 예를 들어 n/lost/reserve가 5/1, 2/2, 3이라면 2가 1에게 자신의 체육복을 빌려주는 문제가 발생한다. 2는 여분의 체육복이 있지만 체육복을 도난 당한 경우이므로 타인에게 체육복을 빌려줄 수 없기 때문에 문제가 된다.

 또한 아래 코드의 경우 list 자료형을 활용했기 때문에 정렬을 해줘야 하고 remove의 시간 복잡도가 O(n)이 되는 등의 성능 문제가 있다.

 따라서 교집합을 미리 삭제하고 (차집합을 구하고) 연산을 시작하는 것이 맞다.

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()
    answer = n - len(lost)
    for r in reserve:
        for j in range(-1, 2):
            if r+j in lost:
                answer += 1
                lost.remove(r+j)
                print(r, j, lost)
                break
    return answer
n = int(input())
lost = list(map(int, input().split()))
reserve = list(map(int, input().split()))
print(solution(n, lost, reserve))

 

2. 어떤 방향으로 빌려줘야 하는가?

 왼쪽에 있는 학생을 먼저 빌려줘야 할지 오른쪽에 있는 학생을 먼저 빌려줘야 할지 순서가 상관이 없는지 초반에 헷갈렸다.

 결론은 왼쪽에 있는 학생부터 빌려줘야 빌려줄 수 있는 경우를 최대한으로 처리할 수 있다. 오른쪽부터 빌려주면 빌릴 수 있는데도 빌리지 못하고 순서가 꼬이는 경우가 발생한다.

 다음 블로그 글에서 예시와 함께 이유를 확인할 수 있다.

 

3. lost 기준으로 순회해야 하는가 reserve 기준으로 순회해야 하는가?

 reserve가 자신이 빌려줄 수 있는 학생을 lost에서 모두 찾은 후 lost에 남아 있는 학생의 수를 n에서 빼야 하므로 reserve 기준으로 순회하는 것이 편하다. lost 기준으로 순회하려면 answer 로직 처리를 다르게 해야한다.

반응형