๐Ÿ… ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 1845 : ํฐ์ผ“๋ชฌ - Javascript

๋ฌธ์ œ ์„ค๋ช…

๋‹น์‹ ์€ ํฐ์ผ“๋ชฌ์„ ์žก๊ธฐ ์œ„ํ•œ ์˜ค๋žœ ์—ฌํ–‰ ๋์—, ํ™ ๋ฐ•์‚ฌ๋‹˜์˜ ์—ฐ๊ตฌ์‹ค์— ๋„์ฐฉํ–ˆ์Šต๋‹ˆ๋‹ค. ํ™ ๋ฐ•์‚ฌ๋‹˜์€ ๋‹น์‹ ์—๊ฒŒ ์ž์‹ ์˜ ์—ฐ๊ตฌ์‹ค์— ์žˆ๋Š” ์ด N ๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ ์ค‘์—์„œ N/2๋งˆ๋ฆฌ๋ฅผ ๊ฐ€์ ธ๊ฐ€๋„ ์ข‹๋‹ค๊ณ  ํ–ˆ์Šต๋‹ˆ๋‹ค.

ํ™ ๋ฐ•์‚ฌ๋‹˜ ์—ฐ๊ตฌ์‹ค์˜ ํฐ์ผ“๋ชฌ์€ ์ข…๋ฅ˜์— ๋”ฐ๋ผ ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์—ฌ ๊ตฌ๋ถ„ํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ๊ฐ™์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์€ ๊ฐ™์€ ๋ฒˆํ˜ธ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์—ฐ๊ตฌ์‹ค์— ์ด 4๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ์ด ์žˆ๊ณ , ๊ฐ ํฐ์ผ“๋ชฌ์˜ ์ข…๋ฅ˜ ๋ฒˆํ˜ธ๊ฐ€ [3๋ฒˆ, 1๋ฒˆ, 2๋ฒˆ, 3๋ฒˆ]์ด๋ผ๋ฉด ์ด๋Š” 3๋ฒˆ ํฐ์ผ“๋ชฌ ๋‘ ๋งˆ๋ฆฌ, 1๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ, 2๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ๊ฐ€ ์žˆ์Œ์„ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. ์ด๋•Œ, 4๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ ์ค‘ 2๋งˆ๋ฆฌ๋ฅผ ๊ณ ๋ฅด๋Š” ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด 6๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

  1. ์ฒซ ๋ฒˆ์งธ(3๋ฒˆ), ๋‘ ๋ฒˆ์งธ(1๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒ
  2. ์ฒซ ๋ฒˆ์งธ(3๋ฒˆ), ์„ธ ๋ฒˆ์งธ(2๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒ
  3. ์ฒซ ๋ฒˆ์งธ(3๋ฒˆ), ๋„ค ๋ฒˆ์งธ(3๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒ
  4. ๋‘ ๋ฒˆ์งธ(1๋ฒˆ), ์„ธ ๋ฒˆ์งธ(2๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒ
  5. ๋‘ ๋ฒˆ์งธ(1๋ฒˆ), ๋„ค ๋ฒˆ์งธ(3๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒ
  6. ์„ธ ๋ฒˆ์งธ(2๋ฒˆ), ๋„ค ๋ฒˆ์งธ(3๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒ

์ด๋•Œ, ์ฒซ ๋ฒˆ์งธ(3๋ฒˆ) ํฐ์ผ“๋ชฌ๊ณผ ๋„ค ๋ฒˆ์งธ(3๋ฒˆ) ํฐ์ผ“๋ชฌ์„ ์„ ํƒํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ํ•œ ์ข…๋ฅ˜(3๋ฒˆ ํฐ์ผ“๋ชฌ ๋‘ ๋งˆ๋ฆฌ)์˜ ํฐ์ผ“๋ชฌ๋งŒ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์ง€๋งŒ, ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•๋“ค์€ ๋ชจ๋‘ ๋‘ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์œ„ ์˜ˆ์‹œ์—์„œ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์€ 2๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

๋‹น์‹ ์€ ์ตœ๋Œ€ํ•œ ๋‹ค์–‘ํ•œ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ๊ฐ€์ง€๊ธธ ์›ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ํฌํ•จํ•ด์„œ N/2๋งˆ๋ฆฌ๋ฅผ ์„ ํƒํ•˜๋ ค ํ•ฉ๋‹ˆ๋‹ค. N๋งˆ๋ฆฌ ํฐ์ผ“๋ชฌ์˜ ์ข…๋ฅ˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด nums๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, N/2๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ์„ ์„ ํƒํ•˜๋Š” ๋ฐฉ๋ฒ• ์ค‘, ๊ฐ€์žฅ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ์„ ํƒํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ฐพ์•„, ๊ทธ๋•Œ์˜ ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜ ๋ฒˆํ˜ธ์˜ ๊ฐœ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.


์ œํ•œ์‚ฌํ•ญ

  • nums๋Š” ํฐ์ผ“๋ชฌ์˜ ์ข…๋ฅ˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด 1์ฐจ์› ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค.
  • nums์˜ ๊ธธ์ด(N)๋Š” 1 ์ด์ƒ 10,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋ฉฐ, ํ•ญ์ƒ ์ง์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
  • ํฐ์ผ“๋ชฌ์˜ ์ข…๋ฅ˜ ๋ฒˆํ˜ธ๋Š” 1 ์ด์ƒ 200,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜๋กœ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
  • ๊ฐ€์žฅ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ์„ ํƒํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์—ฌ๋Ÿฌ ๊ฐ€์ง€์ธ ๊ฒฝ์šฐ์—๋„, ์„ ํƒํ•  ์ˆ˜ ์žˆ๋Š” ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜ ๊ฐœ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’ ํ•˜๋‚˜๋งŒ return ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

nums result
[3,1,2,3] 2
[3,3,3,2,2,4] 3
[3,3,3,2,2,2] 2
  • ์˜ˆ์ œ #1
    ๋ฌธ์ œ์˜ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #2
    6๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ์ด ์žˆ์œผ๋ฏ€๋กœ, 3๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ์„ ๊ณจ๋ผ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ๊ณ ๋ฅด๊ธฐ ์œ„ํ•ด์„œ๋Š” 3๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ, 2๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ, 4๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ๋ฅผ ๊ณ ๋ฅด๋ฉด ๋˜๋ฉฐ, ๋”ฐ๋ผ์„œ 3์„ return ํ•ฉ๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #3
    6๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ์ด ์žˆ์œผ๋ฏ€๋กœ, 3๋งˆ๋ฆฌ์˜ ํฐ์ผ“๋ชฌ์„ ๊ณจ๋ผ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ๊ณ ๋ฅด๊ธฐ ์œ„ํ•ด์„œ๋Š” 3๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ์™€ 2๋ฒˆ ํฐ์ผ“๋ชฌ ๋‘ ๋งˆ๋ฆฌ๋ฅผ ๊ณ ๋ฅด๊ฑฐ๋‚˜, ํ˜น์€ 3๋ฒˆ ํฐ์ผ“๋ชฌ ๋‘ ๋งˆ๋ฆฌ์™€ 2๋ฒˆ ํฐ์ผ“๋ชฌ ํ•œ ๋งˆ๋ฆฌ๋ฅผ ๊ณ ๋ฅด๋ฉด ๋ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ตœ๋Œ€ ๊ณ ๋ฅผ ์ˆ˜ ์žˆ๋Š” ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜์˜ ์ˆ˜๋Š” 2์ž…๋‹ˆ๋‹ค.


ํ’€์ด ๊ณผ์ •

๋จผ์ € ๋ชจ๋“  ํฐ์ผ“๋ชฌ์˜ ์ข…๋ฅ˜๊ฐ€ ๋‹ค๋ฅด์ž๋ฉด N/2๋งˆ๋ฆฌ๋ฅผ ๊ฐ€์ง€๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ๊ณ ๋ฅด๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ํฐ์ผ“๋ชฌ์˜ ์ข…๋ฅ˜ ์ˆ˜๊ฐ€ N/2๋งˆ๋ฆฌ๋ณด๋‹ค ์ ๋‹ค๋ฉด ๋ชจ๋“  ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜๋ฅผ ์„ ํƒํ•˜๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ๋งŽ์€ ์ข…๋ฅ˜์˜ ํฐ์ผ“๋ชฌ์„ ๊ณ ๋ฅด๋Š” ๋ฐฉ๋ฒ•์ด ๋ฉ๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ N/2์™€ ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜์˜ ์ˆ˜ ์ค‘ ๋” ์ž‘์€ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์‹œ๋„ 1

๋ชจ๋“  ํฐ์ผ“๋ชฌ์„ ํ•ด์‰ฌ๋งต์— ๋‹ด์•„ ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.

function solution(nums) {
  const map = {};
  for (const num of nums) {
    map[num] = true;
  }

  const max = nums.length / 2;
  const types = Object.values(map).length;

  return Math.min(max, types);
}

์‹œ๋„ 2

๋ชจ๋“  ํฐ์ผ“๋ชฌ Set์— ๋‹ด์•„ ๋น ๋ฅด๊ฒŒ ํฐ์ผ“๋ชฌ ์ข…๋ฅ˜์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.

  • Set์€ ๊ฐ™์€ ๊ฐ’์€ ํ•˜๋‚˜๋งŒ ๊ฐ–๋Š” ์ปฌ๋ ‰์…˜ ๊ฐ์ฒด์ž…๋‹ˆ๋‹ค.
function solution(nums) {
  const max = nums.length / 2;
  const types = new Set(nums).size;

  return Math.min(max, types);
}

์ˆ์ฝ”๋”ฉ (CodeGolf)

์กฐ๊ธˆ ๋” ์ฝ”๋“œ๋ฅผ ๊ฐ„๊ฒฐํ•˜๊ฒŒ ๋ฐ”๊พธ๊ธฐ ์œ„ํ•ด ๋žŒ๋‹ค์‹์œผ๋กœ ๋ณ€๊ฒฝํ•ด ์•„๋ž˜์™€ ๊ฐ™์ด ์ •๋ฆฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

const solution = (nums) => Math.min(nums.length / 2, new Set(nums).size);

๋งˆ์ง€๋ง‰์œผ๋กœ ๊ฐ€๋…์„ฑ์„ ํฌ๊ธฐํ•˜๊ณ  ๋ชจ๋“  ์ด๋ฆ„์„ ํ•œ๊ธ€์ž๋กœ ์ˆ˜์ •ํ•˜๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ์ˆ์ฝ”๋”ฉ ์ฝ”๋“œ๊ฐ€ ์™„์„ฑ๋ฉ๋‹ˆ๋‹ค.

solution=n=>Math.min(n.length/2,new Set(n).size)