{}연습장
대시보드학습스킬 경로문제모의고사라이브 코테복습데이터
문제 목록〉해시〉굿즈 부스 방문 계획← 이전다음 →
#047 · 해시쉬움해시 / Set

굿즈 부스 방문 계획

문제

전시회장에는 부스가 여러 개 있고, 부스마다 나눠 주는 굿즈가 하나씩 정해져 있습니다. booths[i]는 i번 부스에서 받을 수 있는 굿즈의 종류 코드이며, 같은 코드는 같은 굿즈를 뜻합니다.

관람 시간이 빠듯해 부스는 정확히 k곳만 방문할 수 있고, 같은 부스를 두 번 방문할 수는 없습니다. 방문한 부스에서 굿즈를 하나씩 받을 때, 모을 수 있는 서로 다른 굿즈 종류의 최대 가짓수를 반환하세요.

function solution(booths: number[], k: number): number

예시

booths k 반환 설명
[7,7,4,9,4,9,9] 3 3 7·4·9 부스를 하나씩 방문
[5,5,5,5] 2 1 굿즈가 한 종류뿐
[2,8,6,1,3] 2 2 두 곳만 가므로 최대 2종
[11,11,4,4,6,6,6] 5 3 다섯 곳을 가도 종류는 3종이 한계

제약 조건

  • 1 ≤ booths.length ≤ 100,000
  • 1 ≤ k ≤ booths.length
  • 1 ≤ booths[i] ≤ 1,000,000
  • booths.length가 짝수라는 보장은 없습니다

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

테스트 케이스

예시 1: 3종을 하나씩 → 3
입력: booths = [7,7,4,9,4,9,9], k = 3
출력: 3
예시 2: 한 종류뿐 → 1
입력: booths = [5,5,5,5], k = 2
출력: 1
예시 3: 방문 수가 종류 수보다 적음 → 2
입력: booths = [2,8,6,1,3], k = 2
출력: 2
예시 4: 종류 수가 상한 → 3
입력: booths = [11,11,4,4,6,6,6], k = 5
출력: 3
엣지: 부스 한 곳 → 1
입력: booths = [12], k = 1
출력: 1
홀수 길이 배열, 종류 3종 → 3
입력: booths = [3,9,3,9,5], k = 4
출력: 3
전부 방문해도 중복 굿즈가 있어 3
입력: booths = [1,2,2,3], k = 4
출력: 3
엣지: 한 곳만 방문 → 1
입력: booths = [6,6,1,1,8,8,4,4], k = 1
출력: 1
solution.ts
에디터 로딩 중…

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