: 모든 경우의 수에 대해 N/2를 순회한다. 순회하면서 새로운 종류의 폰켓몬일 경우 카운팅하며 이를 바탕으로 선택할 수 있는 최대 폰켓몬의 종류를 알아낸다.
int[] g_poncket = new int[200001]; //순회한 폰켓몬의 종류는 1로 저장, 0일경우 순회하지 않은 폰켓몬 종류임을 의미
int[] g_visit = new int[10001]; //DFS탐색시 인덱스 방문 여부를 저장(0:방문안함, 1:방문)
int maxCnt = 0; //선택할 수 있는 최대 폰켓몬의 종류를 저장
/**
* 재귀호출을 통해 N/2마리의 폰켓몬을 순회한다
* @param nums 입력으로 받은 폰켓몬
* @param idx 현재 방문할 인덱스
* @param cnt 여태까지 순회한 폰켓몬의 수 ( 호출시 순회하는 폰켓몬을 포함함 )
* @param kindsCnt 순회하면서 선택한 폰켓몬의 종류 수
*/
void get_max_kinds(int[] nums, int idx, int cnt, int kindsCnt) {
g_visit[idx] = 1;
int flag = 0; //원래 순회했던 포켓몬 종료이면 1로 저장
if(g_poncket[nums[idx]] == 0) { //해당 포켓몬 종류를 순회한적 없으면
g_poncket[nums[idx]] = 1;
kindsCnt += 1; //폰켓몬 종류수를 +1
} else { //이미 해당 폰켓몬 종류를 순회한적 있으면
flag = 1;
}
int N = nums.length;
if(cnt < N/2) { //재귀호출부(순환부)
for(int i=idx+1; i<N; i++) {
if(g_visit[i] == 0) {
get_max_kinds(nums, i, cnt+1, kindsCnt);
}
}
} else { //종료부
if(cnt == N/2) {
if (kindsCnt > maxCnt) { //최대 폰켓몬의 종류로 업데이트
maxCnt = kindsCnt;
}
}
}
if(flag == 0) { //이번 재귀호출로 폰켓몬 종류수가 +1 되었다면 원상복구한다
g_poncket[nums[idx]] = 0;
}
g_visit[idx] = 0; //방문처리 원상복구
}
: N/2의 폰켓몬을 방문하는 get_max_kinds 메소드를 호출하고 정답을 출력한다
public int solution(int[] nums) {
int answer = 0;
for(int i=0; i<nums.length; i++) {
get_max_kinds(nums, i, 1, 0);
}
answer = maxCnt;
return answer;
}
: 프로세스 오류는 없으나 시간초과. DFS순회가 아닌 다른 방식으로 문제를 접근해야함을 느꼈음.
1) 입력으로 들어온 폰켓몬들의 종류에 대해, 종류당 몇마린지 카운팅하는 배열을 사용했다.
Ex) nums = [3,3,3,2,2,4] 일 경우
값\인덱스(폰켓몬종류) | 0 | 1 | 2 | 3 | 4 | 5 | ... |
---|---|---|---|---|---|---|---|
0 | 0 | 2 | 3 | 1 | 0 |
2) 배열을 위와 같이 저장하고 내림차순 정렬하면 최소 한마리 이상인 종류들의 값이 배열의 앞에 위치하게 된다. (이때 인덱스는 폰켓몬 종류와 상관없게 됨을 주의)
값\인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | ... |
---|---|---|---|---|---|---|---|
3 | 2 | 1 | 0 | 0 | 0 | 0 |
3) 선택할 수 있는 최대 폰켓몬의 수를 구하면 되므로 앞에서부터 N/2개까지(인덱스: 0~(N/2-1)) 값이 0이 아니면 카운팅한 것이 정답이된다.
public int solution(int[] nums) {
int answer = 0;
Integer[] cntArr = new Integer[200001];
Arrays.fill(cntArr, 0);
//각 종류당 몇마리 있는지 저장
for(int i=0; i<nums.length; i++) {
cntArr[(nums[i])]++;
}
//내림차순으로 정렬
Arrays.sort(cntArr, Collections.reverseOrder());
for(int i=0; i<nums.length/2; i++) {
if(cntArr[i] == 0) { break;}
answer++;
}
return answer;
}
배열을 내림차순으로 정렬하기 위해 Integer형으로 배열을 만들고 Collections.reverseOrder() 메소드를 사용함. Integer는 기본 자료형이 아닌 객체이기 때문에 Arrays.fill(cntArr, 0); 을 사용해 반드시 값을 저장해야 한다. (안할경우 nullpointerexception 발생)
이와 관련된 Wrapper 클래스 내용은 추후에 정리할 예정