[백준 10816] 숫자 카드 2
February 13, 2023
문제
https://www.acmicpc.net/problem/10816
아이디어 1 (해쉬 이용)
- 상근이가 가지고 있는 숫자 카드를 한번씩 순회하면서, 같은 카드의 갯수를 세고 해쉬에 저장한다.
- 상근이가 몇 개나 가지고 있는 숫자 카드인지를 해쉬 맵에서 꺼내서 확인한다.
소스코드 1
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const cards = {};
input[1].split(" ").forEach(e => cards[e] = cards[e] ? cards[e] + 1 : 1);
const m = Number(input[2]);
const questions = input[3].split(" ").map(e => Number(e));
// 문제
function solution() {
const result = [];
questions.forEach(q => result.push(cards[q] ? cards[q] : 0));
console.log(result.join(" "));
}
// 실행
solution();아이디어 2 (이분탐색 이용)
- 상근이가 가지고 있는 숫자 카드를 오름차순으로 정렬한다.
-
상근이가 몇 개나 가지고 있는 숫자 카드인지를 구해야 하는 문제 배열을 순회하면서 다음 로직을 수행한다.
- 데이터 내 특정 K값보다 같거나 큰 값이 처음 나오는 위치를 구한다. (Lower Bound)
- 데이터 내 특정 K값보다 큰 값이 처음 나오는 위치를 구한다. (Upper Bound)
- Upper Bound 값에서 Lower Bound 값을 빼면 해당 원소가 몇 개 존재하는지를 알 수 있다.
참고
https://sangwoo0727.github.io/algorithm/Algorithm-Ublb/
소스코드 2
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const cards = input[1].split(" ").map(e => Number(e)).sort((a, b) => a - b);
const m = Number(input[2]);
const questions = input[3].split(" ").map(e => Number(e));
// 문제
function lower_bound(value) {
let start = 0;
let end = cards.length;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (value <= cards[mid]) end = mid;
else start = mid + 1;
}
return start;
}
function upper_bound(value) {
let start = 0;
let end = cards.length;
while (start < end) {
let mid = Math.floor((start + end) / 2);
if (value < cards[mid]) end = mid;
else start = mid + 1;
}
return start;
}
function solution() {
const result = [];
questions.forEach(q => result.push(upper_bound(q) - lower_bound(q)));
console.log(result.join(" "));
}
// 실행
solution();