백준(BOJ) 11652: 카드

🙋‍♀️ 문제 정보

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다.
준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

입력

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

출력

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

테스트 케이스

입력 1

5
1
2
1
2
1

출력 1

1

입력 2

6
1
2
1
2
1
2

출력 2

1

🔥 시도 과정

소스 코드

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => Number(v));

const [testCase, ...numbers] = input;
const max = Math.max(...numbers);
let min = Math.min(...numbers);
let isNegative = false;
const numArray = min >= 0 ? new Array(max + 1).fill(0) : new Array(-min + max + 1).fill(0);

if (min >= 0) {
  for (let i = 0; i < testCase; i++) {
    numArray[numbers[i]]++;
  }
} else {
  min = Math.abs(min);
  isNegative = true;
  for (let i = 0; i < testCase; i++) {
    numArray[numbers[i] + min]++;
  }
}

const answer = isNegative
  ? numArray.findIndex((v) => v === Math.max(...numArray)) - min
  : numArray.findIndex((v) => v === Math.max(...numArray));

console.log(answer);

메모리/시간

• 런타임 에러 (RangeError)

해결 방법

처음에는 단순히
1. 입력값에서 max, min을 판별해서 max+min 만큼의 0을 채운 array를 만든 뒤
2. 해당 인덱스를 1씩 증가시켜
3. 가장 큰 값을 가진 수의 인덱스를 찾아 출력하는 방식으로 풀었다.
틀렸길래 살펴보니 입력 범위가 -2^62부터 2^62까지인 것을 간과했다.
해당 범위이면 BigInt를 사용해서 풀어야 하기 때문에 max, min값을 판별해서 array를 생성하는 방법은 사용할 수 없다.
또한, 해당 방법은 메모리 낭비가 있기 때문에 방식을 바꾸어 입력 값을 모두 정렬한 후 투포인터로 해결해보기로 했다.

✨ 풀이

소스 코드

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => BigInt(v));

const [, ...numbers] = input;
numbers.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));

let count = 1;
let maxValue = numbers[0];
let maxCount = 0;

numbers.forEach((v, i) => {
  next = numbers[i + 1];
  if (v === next) {
    count++;
  } else {
    count = 1;
  }

  if (count > maxCount) {
    maxCount = count;
    maxValue = v;
  }
});

console.log(String(maxValue));

메모리/시간

• 메모리: 35260KB
• 시간: 380ms

해결 방법

입력값을 정렬 후 투포인터로 count

1. 입력값을 오름차순으로 정렬

numbers.sort((a, b) => a - b);

기존에는 오름차순으로 정렬할 때 위의 방식을 많이 사용했는데 해당 문제에서는 BigInt이기 때문에 숫자 뒤에 n이 붙어있어 해당 방법은 작동되지 않았다.

해당 방식의 기본적인 개념은 아래와 같다.
Array.prototype.sort()

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

a가 b보다 작은 경우 낮은 색인으로 정렬
a가 b와 같은 경우 서로에 대해 변경하지 않음
a가 b보다 큰 경우 b를 a보다 낮은 색인으로 정렬

numbers.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));

따라서, 위와 같이 해결하였다.

2. 투포인터

정렬된 배열을 forEach로 순회하면서 해당 index의 값과 다음 index의 값을 비교하고, 값이 같다면 count를 늘리고 다르다면 count를 초기화 하는 식의 방식이다.
count는 매 순회마다 maxCount 값과 비교하여, count가 maxCount보다 크다면 maxCount의 값을 갱신하고 maxValue의 값 또한 해당 index의 값으로 갱신하는 방식이다.

➕ 더 나아가서

해당 풀이에서는 sort 메서드를 사용했지만 mergeSort 등과 같은 정렬 알고리즘을 직접 적용하여 해결하는 방법도 있겠다.