{}연습장
대시보드학습스킬 경로문제모의고사라이브 코테복습데이터
문제 목록〉그리디〉보조배터리 돌려쓰기← 이전다음 →
#046 · 그리디중간그리디

보조배터리 돌려쓰기

문제

무박 해커톤 행사장에는 1번부터 n번까지 번호가 붙은 자리가 한 줄로 놓여 있고, 각 자리에 참가자가 한 명씩 앉아 있습니다.

일부 참가자는 노트북 배터리가 방전돼 보조배터리를 받아야 작업할 수 있습니다. 한편 여분 보조배터리를 챙겨 온 참가자들도 있는데, 한 명이 최대 2개까지 가지고 있습니다.

빌려주는 규칙은 다음과 같습니다.

  • 케이블이 짧아 바로 앞 번호(자리 - 1) 또는 바로 뒷 번호(자리 + 1) 참가자에게만 빌려줄 수 있습니다.
  • 여분을 가진 참가자 본인이 방전됐다면 여분 하나를 자기가 써야 하고, 남은 개수만 빌려줄 수 있습니다.
  • 방전된 참가자는 보조배터리 하나만 받으면 작업할 수 있습니다.

작업할 수 있는 참가자의 최대 인원수를 반환하세요.

function solution(n: number, drained: number[], lenders: number[][]): number
  • drained: 배터리가 방전된 참가자의 자리 번호 목록
  • lenders: [자리 번호, 여분 개수] 목록. 여분 개수는 1 또는 2

예시

n drained lenders 반환
6 [2,3,5] [[3,2],[6,1]] 6
5 [1,2,4] [[2,2]] 4
5 [2,4] [[3,1]] 4
4 [2,3] [[3,1],[4,1]] 3
  • 첫 번째 예시: 3번은 여분 2개 중 하나를 자기가 쓰고 남은 하나를 2번에게 빌려줍니다. 6번이 5번에게 빌려주면 전원이 작업합니다.
  • 세 번째 예시: 3번의 여분은 하나뿐이라 2번과 4번 중 한 명만 받을 수 있습니다.
  • 네 번째 예시: 3번은 자기 여분을 자기가 써야 하므로 2번은 아무에게도 받지 못합니다.

제약 조건

  • 1 ≤ n ≤ 100
  • 0 ≤ drained.length ≤ n, 자리 번호는 서로 겹치지 않습니다
  • 0 ≤ lenders.length ≤ n, 자리 번호는 서로 겹치지 않습니다
  • 모든 자리 번호는 1 이상 n 이하이며, 배열이 번호순으로 정렬돼 있지 않을 수 있습니다
  • 여분 개수는 1 또는 2

시간 복잡도 목표: O(N)

테스트 케이스

예시 1: 여분 2개 보유자가 자기 몫 쓰고 한 명에게 빌려줌 → 6
입력: n = 6, drained = [2,3,5], lenders = [[3,2],[6,1]]
출력: 6
예시 2: 4번 옆에 여분 보유자가 없음 → 4
입력: n = 5, drained = [1,2,4], lenders = [[2,2]]
출력: 4
예시 3: 여분 1개라 둘 중 한 명만 → 4
입력: n = 5, drained = [2,4], lenders = [[3,1]]
출력: 4
예시 4: 방전된 보유자는 자기 여분을 써야 함 → 3
입력: n = 4, drained = [2,3], lenders = [[3,1],[4,1]]
출력: 3
여분 2개로 앞뒤 모두 지원 → 5
입력: n = 5, drained = [2,4], lenders = [[3,2]]
출력: 5
거리가 멀어 빌려줄 수 없음 → 3
입력: n = 4, drained = [4], lenders = [[1,2]]
출력: 3
여분 2개 중 하나는 본인용, 나머지 하나만 지원 → 2
입력: n = 3, drained = [1,2,3], lenders = [[2,2]]
출력: 2
엣지: 혼자 방전, 여분 없음 → 0
입력: n = 1, drained = [1], lenders = []
출력: 0
solution.ts
에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.