문제
해결 방안 고민
N마리의 폰켓몬 중에서 N/2 마리를 가져가도 좋음
종류에 따라 번호를 구분
- 같은 종류의 폰켓몬은 같은 번호를 가지고 있음
- 총 4마리의 폰켓몬
- 3, 1, 2, 3
- 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있음
- (3, 1), (3, 2), (3, 3), (1, 2), (1, 3), (2, 3)
- (3, 3) 을 제외한 5가지 => 5 / 2 => 2 (최댓값)
- 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2 마리를 선택하려고 함
- N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2 마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬 선택 방법 찾기
- 그때 폰켓몬 종류의 개수 리턴
- 자동 중복 제거를 위해 HashSet 사용
Markdown
복사
•
가져갈 수 있는 최대 폰켓몬 종류의 개수를 구하는 것이다.
◦
중복으로 가져가면 해당 폰켓몬의 개수는 무조건 1개이다.
◦
Set은 중복을 자동으로 제거해주기 때문에 Set을 활용하는 접근방식이 필요하다고 생각했다.
해결 방법
•
[3, 1, 2, 3]
◦
최대로 가져갈 수 있는 폰켓몬의 갯수는 2개이다.
•
[3, 3, 3, 2, 2, 2]
◦
최대로 가져갈 수 있는 폰켓몬의 갯수는 2개이다.
▪
최대 3개까지 가져갈 수 있지만, 모두 중복이다.
▪
이 경우 set의 size를 출력해주면 된다.
코드
package algo250304;
import java.util.HashSet;
public class Programmers1845 {
public int solution(int[] nums) {
int max = nums.length / 2;
// 중복 제거 위해 HashSet 선언 (자동 중복 제거)
HashSet<Integer> set = new HashSet<>();
for (int value : nums) {
set.add(value);
}
int size = set.size(); // 1, 2, 3
return (size > max) ? max : size;
}
}
Java
복사