공부해 codingTest
프로그래머스 JAVA Level 1. 폰켓몬
러쉬허쉬
2023. 2. 8. 00:09
Level 1. 폰켓몬
https://school.programmers.co.kr/learn/courses/30/lessons/1845
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 통과
2. 통과 코드
3. 문제 해석
(1) 최대한 다양한 포켓몬을 골라야 한다.
즉, 중복이 가장 적은 경우를 찾아야 한다.
(2) 한번에 고를 수 있는 포켓몬은 주어진 배열 길이의 절반까지다.
즉, 배열의 모든 요소가 중복이 없어도 고를 수 있는 포켓몬은 배열 길이의 절반까지다.
(3) 조합처럼 모든 경우의 수를 조사하는 방법은 시간초과다.
4. 풀이
(1) 주어진 배열의 요소를 HashSet 구조에 옮긴다.
그러면 중복이 제거된다.
(2) HashSet의 길이가 주어진 배열 길이의 절반보다 크다면 최대한 고를 수 있는 포켓몬의 종류는 배열 길이의 절반이다.
그렇지 않다면 HashSet의 길이가 최대한 고를 수 있는 포켓몬의 종류다.