문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/142085
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
enemy 길이가 최대 백만이기 때문에 시간 복잡도 O(nlogn) 안에 풀어야 하는 것이 자명한 문제였습니다.
O(nlogn)이라고 하면 제일 먼저 떠오르는 자료구조가 힙이였는데 다행히도 최소 힙으로 풀 수 있는 문제였습니다.
알고리즘은 아래와 같습니다.
1. 최소힙을 선언하고 enemy를 순서대로 넣어줍니다.
1.1 무적권은 k개이기 때문에 최소 힙의 크기는 k개 이하로 유지해줘야 하므로 최소 힙의 크기가 k개를 넘을 때마다 최소 힙을 pop 해주고 해당 값을 sum에 더해줍니다.
1.2 sum 값이 n을 넘을 경우 더 이상 다음 라운드로 못 가므로 해당 라운드 값을 반환해주고 프로그램을 종료합니다.
2. 1번 과정을 다 거쳤는데도 프로그램 종료가 안되었다면 모든 라운드를 통과했다는 뜻이므로 enemy 벡터의 크기를 반환해줍니다.
개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
| [Programmers] 택배상자 (0) | 2022.12.29 |
|---|---|
| [Programmers] 테이블 해시 함수 (2) | 2022.12.25 |
| [Programmers] 할인 행사 (0) | 2022.12.03 |
| [Programmers] 숫자 타자 대회 (2) | 2022.11.20 |
| [Programmers] 숫자 짝궁 (0) | 2022.10.10 |