참고
문제해설
NOTE
•
입력값 ⇒ 정수배열
•
반환값 ⇒ 정수배열에 가장 많은(절반 이상을 차지) 요소
•
O(1) ⇒ 한번의 탐색으로 가장 많이차지하고 있는값을 알아내야한다.
문제 로직고민
NOTE
•
어떻게 가장 많이 들어가있는 값을 O(1)의 값으로 구하는가?
◦
요소의 범위 -10^9 <= nums[i] <= 10^9
◦
정수배열로 요소의 개수를 기록하며 하기에는 범위가 너무 넓다.
◦
map을 활용해도 될것같지만 Array/String 문제이므로 사용하지 않겠다.
•
가장 많은 요소는 최소 n/2만큼이 포함되어 있다.
◦
n의 범위가 1~5000인만큼 생각보다 작아서 이 문제에서 가장 핵심이라 생각했다.
◦
이 조건이 O(1)을 통한 가장 많은 값을 탐색하게 해주는 중요한 조건이라 생각해 고민하고있다.
◦
30분정도 고민했는데, 도저히 모르겠다… O(1)이 아니거나, Map을 활용한다면 쉬울거같은데, 배열만으로 이를 해결하는 방법이 없는가?
•
O(1)을 일단 제외하고 문제풀이를 도전
◦
O(1)이 문제에서 권장되는 풀이이지만, 일단 문제를 푸는데 먼저 도전한다.
◦
값이 절반이상이 존재한다는 의미는, 배열을 정렬했을때, n/2 idx에서 가장 대표적인 값이 무조건 포함된다는 의미이다.
작성코드
NOTE
import java.util.*;
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
Java
복사
통과는 했지만.. 문제의도와 너무 벗어난거같다
정답코드
NOTE
class Solution {
public int majorityElement(int[] nums) {
HashMap<Integer,Integer> mp = new HashMap<>();
int n = nums.length;
int maxnum = 0;
int ans = nums[0];
for(int i = 0; i<n; i++){
if(mp.containsKey(nums[i])){
int num = mp.get(nums[i])+1;
mp.put(nums[i],num);
if(num>maxnum) {
ans = nums[i];
maxnum = num;
}
}else{
mp.put(nums[i],1);
}
}
return ans;
}
}
Java
복사
Map을 사용하는 코드
•
문제 유형이 Array/String이라 Map을 사용하지 않았는데, Map을 푸는게 정석방법이라 좀 당황했다.
•
Map 방식은 내가 초기에 생각했던것과 비슷하게 O(1)의 방식으로 해결되는것 같다.
•
또한 Map 방식이 아니라면 보이어 무어 과반수 투표알고리즘으로 해결이 가능하다고 하는데 이는 추후에 공부해보겠다.