[JS 백준] 11652.카드

https://www.acmicpc.net/problem/11652

11652번: 카드

해시와 관련된 검색 문제다.

얼마나 빠르게 검색하느냐가 관건인데.

병합정렬을 통해 정렬 후 카운팅으로 정답을 알아가는 문제다.

 

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';

const [N,...numbers] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim().split('\n');

let number = numbers.map(v=>v.trim())

// console.log(number)


const mergeSort = (arr) => {
if(arr.length === 1){
    return arr;
}

let mid = Math.floor(arr.length/2);
let first = mergeSort(arr.slice(0,mid));
let last = mergeSort(arr.slice(mid));

let i = 0; let j = 0 ;
const sorted = [];

while(i<first.length && j < last.length){
    if(first[i] < last[j]){
        sorted.push(first[i]);
        i++;
    }else{
        sorted.push(last[j]);
        j++;
    }
}

if(i < first.length){
    sorted.push(...first.slice(i));
}
if(j < last.length){
    sorted.push(...last.slice(j)); 
}

return sorted;

}

const result = mergeSort(number.map(v=>BigInt(v)));
let MAX = 0;
let currenCount = 0;
let answer = 2**62;;
let previous = '';

// console.log(result);

for(let  i = 0; i < result.length; i++){
    if(result[i] != previous){
        previous = result[i];
        currenCount = 0;
    }
    currenCount++;
    if(currenCount > MAX || currenCount === MAX && answer > result[i]){
        MAX = currenCount;
        answer = result[i];
    }
}
console.log(String(answer));

 

병합정렬을 활용한 방법이다.

1. 배열을 반으로 자른다.

2. 자르기위해 배열의 크기/2에 반내림을 한다.

3. 반내림을 한 수를 기준으로 배열을 앞뒤로 자르고

4. 자른 배열을 병합정렬함수에 담아서 보낸다.

5. 예를들어 first에 담은 함수는 잘게잘게 잘려서 2을 반환하고

6. last에 담은 함수는 잘게잘게 잘려서 1,5를 반환한다

7. sorted에는 1,2,5 가 담겨서 반환이 될 것이고 이 모든 과정들이 합쳐져서 정렬이 된다.

 

 

 

 

같은 수일 경우 더 작은 수를 출력해야하기에 answer > result[i] 이다