문제
문제 해석
가장 많이 발생하는 인자를 찾아 반환하라 이때 인자는 전체 길이의 절반 이상이다.
이 문제를 보자마다 딱 떠오른건 정렬 때려서 n/2 번지의 값을 찾아야겠다 라는 것이다.
Why?
정렬을 먼저 하는 이유는 값을 뭉쳐두기 위해서다.
정렬을 통해 값들을 모두 뭉쳐두고 여기서 n/2번지의 값을 찾으면 이것은 무조건 최빈값이 되기 때문이다.간단하게 문제를 해석하고 끝낼 수 있지만 2번째 방법을 생각해 봤다.
2번째 방법은 정렬을 하지 않고 문제를 푸는 방법을 고민했다.
이유는 단순하게 정렬을 하게 된다면 위의 방법이 가장 빠른 방법이라고 판단했기 때문이다.
- 정렬을 하지 않고 문제를 풀기 위한 문제 해석
이중 for문을 사용해서 문제의 해결을 고민할 수 있다.
- 첫번째 for문 : 전체 루프를 보는 것 index = i
- 두번째 for문 : 첫번째 for문의 i번지까지 검증할 루프
- 두번째 for문이 끝난 이후 저장된 값이 n/2보다 크거나 같은지 검증
이 때 n/2가 홀수라면 +1 을 해줘야한다.
ex) n = 3 -> n/2 = 2 이어야한다.
n = 5 -> n/2 = 3 이어야한다.
이를 수도 코드로 만들면
조건 체크
length 가 1이면 0번지 반환
길이 = 홀수면 n/2 + 1 , 짝수면 n/2
count = 1;
for(전체 루프 i)
for(i 번지까지의 루프)
if(i번지와 같다면)
count 증가
else
if(length <= count)
return num[i];
count = 1;
if문이 너무 많기는 하지만 내가 만든 정렬을 하지 않고 사용할 수 있는 코드다.
코드 1
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];간단하게 정렬해서 중간 값을 찾은 것이다.
이를 통해 쉽게 값을 얻을 수 있다.
코드 2
class Solution {
public int majorityElement(int[] nums) {
if(nums.length == 1)
return nums[0];
int length = nums.length % 2 ==0 ? nums.length / 2 : nums.length / 2 + 1;
int count = 1;
for(int i = 1 ; i < nums.length ; i++){
for(int j = 0; j < i; j++){
if(nums[i] == nums[j])
count++;
}
if(count >= length)
return nums[i];
count = 1;
}
return -1;
}
}코드를 그냥 확인하기에도 조금 지저분하다.
일단 length에서 if문을 사용
총 if문이 4번 정도의 if문이 사용되었고 코드가 간단히 보기 복잡해졌다.
물론 시간복잡도 또한 어마무시하게 올라간다.
추청 시간 복잡도는 O(nlogn)이다.
이중 for문을 사용해야되기 때문에 연산이 상당히 늘어나기 때문이다.
다른 사람이 만든 코드
브루스포스
code
int majorityElement(int nums[], int n){
int maxCount = 0;
int index = -1;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (nums[i] == nums[j])
count++;
}
if (count > maxCount) {
maxCount = count;
index = i;
}
}
if (maxCount > n / 2)
return nums[index];
else
return -1;
}이 문제를 해석하기 전에 브루스포트 알고리즘에 대해 먼저 확인해야한다.
브루스 포스
모든 경우를 다 따지며 해를 찾는 방식
이 방법을 사용하면 무조건 예외 없이 정답을찾을 수 있다.
위의 코드는 나의 2번째 코드와 유사하다 찾을 수 있는 모든 방법을 이용해서 문제를 해결해낸다.
물론 이렇게 풀게 되면 시간 복잡도는 위의 방식에 비해 많이 느리다.
분할 정복 Divide and Conquer (Binary Search Tree)
하나의 문제를 작은 여러개의 문제로 쪼갠 뒤 재귀적으로 문제를 해결한 뒤 이를 합쳐 원래 문제를 해결하는 방법
문제는 주로 2개 이상의 하위 문제로 구분된다.
이 방법을 이용 시 장점은 간단하며 빠르다(큰 문제를 재귀적으로 나누어 병렬적 문제 해결)
단점은 스텍오버플로우의 발생 가능성이 있고, 메모리의 사용이 비효율적이다.
이진 검색 트리의 기본은 노드를 만들어서 트리 구조를 만든 뒤 최대 값을 찾는 것이다.
이 것은 솔루션을 보고 내가 다시 직접 수도코드를 작성하고 코드를 구현한 것이다.
수도코드
각 노드에 데이터 삽입
for(전체 반복)
노드 insert()
노드에서 값을 찾아오기 메서드
int num = 노드를 뒤지면서 값을 찾아온다.
return num;
각각의 노드를 나타낼 Node class
int key;
int count = 1; 노드 생성 시 무조건 하나 이상의 생성 그것을 가지고 있어야한다.
Node left, right;
생성자로는 key 받게 함
전역 변수
1. size : 전체 길이를 나타내는 변수
2. max : max값의 key를 삽입할 변수 (max 값이 존재한다면 바로 로직을 탈출 시키기 위한 조건으로 사용하는 코드)
각각의 노드를 삽입 시킬 수 있는 insert 메서드 구현
void insert(Node node int num)
node null 이면
new Node(num)
node의 key 값이 num 보디 더 크면
node.left = insert(node.left, num)
작으면
node.right = insert(node.right, num)
같으면
node.count++;
노드에서 값을 찾아오는 메서드 구현
Node select (Node node)
if max가 not min
탈출
if node != null
select(node.left)
if(node.count size /2 보다 크다)
max = node.key
오른쪽 뒤지기 시작가장 먼저 어떻게 할 것인지 찾아봐야겠다.
내가 함수에서 해줄 것은 간단하게
- 트리 구현
- 트리에서 값을 빼옴
이 두가지다.
1번을 수행하기 위해 for문으로 루프를 돌리면서 insert라는 메서드를 만든다.
2번을 수행하기 위해 select라는 메서드를 만들 것이다.
간단하게 일단 트리의 노드를 구성하기 위한 노드 클래스를 만들어 주고 해당 노드에 인자를 하나하나 넣어주려고한다.
그러기 위해 Node라는 클래스를 만들었다.
그리고 전역 변수로 사용할 것들을 체크했다.
전역 변수는 반복되는 적으로 많이 사용되는 것들 2개로 사용했다.
전역 변수 사용을 통해 파라미터를 줄였다.
이제 각각의 메서드를 만들어 줄 것이다.
코드
class Solution {
int size ;
int maxKey = Integer.MIN_VALUE;
public int majorityElement(int[] nums) {
size = nums.length / 2;
Node root = null;
for (int i = 0; i < nums.length; i++)
root = insert(root, nums[i]);
select(root);
return maxKey;
}
public Node insert(Node node, int num){
if(node == null)
return new Node(num);
if(node.key > num)
node.right = insert(node.right,num);
else if (node.key < num) {
node.left = insert(node.left, num);
}else
node.count++;
return node;
}
public void select (Node node){
if(maxKey != Integer.MIN_VALUE)
return;
if (node != null) {
select(node.left);
if (node.count > size)
maxKey = node.key;
select(node.right);
}
}
}
class Node{
int key;
int count;
Node left, right;
public Node(int num) {
this.key = num;
this.count = 1;
}
}코드를 보면 수도 코드를 그대로 만들었다.
위의 코드에서 내가 생각했던 것 보다 시간 복잡도가 적게 나왔다.
모든 방법의 시간 복잡도는 가장 마지막에 사진으로 첨부할 예정이다.
Moore’s Voting Algorithm
과반수 투표 알고리즘이다.
배열에 포함된 원소 중 절반 이상이 포함된 원소를 찾는 알고리즘이다.
대표적인 스트리밍 알고리즘으로 내가 찾는 원소가 배열 내 과반수 이상의 원소를 보장 할 경우 결과 값은 항상 과반수 원소가 되는 것이다.
이 알고리즘을 처음 코드로 보고 진짜 감탄을 했다.
위에 있는 이진 트리를 이용한 것은 보고 트리를 이용할 수 있구나 라는 정도로 끝났고, 배열의 정렬은 머리속에서 딱 떠올랐던 거라 크게 멋지다 라는 생각 자체가 없었는데 이 알고리즘은 와~ 이런 방식으로 풀수가 있네 신기하다!! 할정도로 신기했다.
이 코드는 바로 코드로 확인해 보자.
코드
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int majority = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0 && majority != nums[i]) {
majority = nums[i];
count = 1;
} else if (majority == nums[i]) {
count++;
} else {
count--;
}
}
}
}이 코드는 과반수 이상을 가지고 있다는 전제가 필수다.
코드의 로직을 보면 쉽게 이해할 수 있는데
처음에 count == 0 이고, majority 는 현재 인덱스의 요소가 아닐 경우에만 majority의 값이 변경된다.
그렇지 않을 경우 현재 인덱스의 요소가 majority가 아닐 경우에는 그냥 count를 줄여준다.
이를 통해 마지막에 남은 majority가 과반수 이상의 값을 가지는 요소가 된다.
이건 O(n)의 속도를 가질 것이라는 생각이 든다.
실제로 속도도 지금까지 테스트 한 것 중 가장 빨랐다.
'코테' 카테고리의 다른 글
| 121. Best Time to Buy and Sell Stock JAVA (0) | 2023.08.25 |
|---|---|
| 리트코드 189. Rotate Array JAVA (0) | 2023.08.25 |
| 리트코드 80. Remove Duplicates from Sorted Array II JAVA (0) | 2023.08.24 |
| 리트코드 26. Remove Duplicates from Sorted Array JAVA (0) | 2023.08.24 |
| 리트코드 27.Remove Element JAVA (0) | 2023.08.24 |