๐Ÿ… ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 42576 : ์™„์ฃผํ•˜์ง€ ๋ชปํ•œ ์„ ์ˆ˜ - Javascript

๋ฌธ์ œ ์„ค๋ช…

์ˆ˜๋งŽ์€ ๋งˆ๋ผํ†ค ์„ ์ˆ˜๋“ค์ด ๋งˆ๋ผํ†ค์— ์ฐธ์—ฌํ•˜์˜€์Šต๋‹ˆ๋‹ค. ๋‹จ ํ•œ ๋ช…์˜ ์„ ์ˆ˜๋ฅผ ์ œ์™ธํ•˜๊ณ ๋Š” ๋ชจ๋“  ์„ ์ˆ˜๊ฐ€ ๋งˆ๋ผํ†ค์„ ์™„์ฃผํ•˜์˜€์Šต๋‹ˆ๋‹ค.

๋งˆ๋ผํ†ค์— ์ฐธ์—ฌํ•œ ์„ ์ˆ˜๋“ค์˜ ์ด๋ฆ„์ด ๋‹ด๊ธด ๋ฐฐ์—ด participant์™€ ์™„์ฃผํ•œ ์„ ์ˆ˜๋“ค์˜ ์ด๋ฆ„์ด ๋‹ด๊ธด ๋ฐฐ์—ด completion์ด ์ฃผ์–ด์งˆ ๋•Œ, ์™„์ฃผํ•˜์ง€ ๋ชปํ•œ ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.


์ œํ•œ์‚ฌํ•ญ

  • ๋งˆ๋ผํ†ค ๊ฒฝ๊ธฐ์— ์ฐธ์—ฌํ•œ ์„ ์ˆ˜์˜ ์ˆ˜๋Š” 1๋ช… ์ด์ƒ 100,000๋ช… ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • completion์˜ ๊ธธ์ด๋Š” participant์˜ ๊ธธ์ด๋ณด๋‹ค 1 ์ž‘์Šต๋‹ˆ๋‹ค.
  • ์ฐธ๊ฐ€์ž์˜ ์ด๋ฆ„์€ 1๊ฐœ ์ด์ƒ 20๊ฐœ ์ดํ•˜์˜ ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์ฐธ๊ฐ€์ž ์ค‘์—๋Š” ๋™๋ช…์ด์ธ์ด ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

participant completion return
[โ€œleoโ€, โ€œkikiโ€, โ€œedenโ€] [โ€œedenโ€, โ€œkikiโ€] โ€œleoโ€
[โ€œmarinaโ€, โ€œjosipaโ€, โ€œnikolaโ€, โ€œvinkoโ€, โ€œfilipaโ€] [โ€œjosipaโ€, โ€œfilipaโ€, โ€œmarinaโ€, โ€œnikolaโ€] โ€œvinkoโ€
[โ€œmislavโ€, โ€œstankoโ€, โ€œmislavโ€, โ€œanaโ€] [โ€œstankoโ€, โ€œanaโ€, โ€œmislavโ€] โ€œmislavโ€
  • ์˜ˆ์ œ #1
    โ€œleoโ€๋Š” ์ฐธ์—ฌ์ž ๋ช…๋‹จ์—๋Š” ์žˆ์ง€๋งŒ, ์™„์ฃผ์ž ๋ช…๋‹จ์—๋Š” ์—†๊ธฐ ๋•Œ๋ฌธ์— ์™„์ฃผํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #2
    โ€œvinkoโ€๋Š” ์ฐธ์—ฌ์ž ๋ช…๋‹จ์—๋Š” ์žˆ์ง€๋งŒ, ์™„์ฃผ์ž ๋ช…๋‹จ์—๋Š” ์—†๊ธฐ ๋•Œ๋ฌธ์— ์™„์ฃผํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.

  • ์˜ˆ์ œ #3
    โ€œmislavโ€๋Š” ์ฐธ์—ฌ์ž ๋ช…๋‹จ์—๋Š” ๋‘ ๋ช…์ด ์žˆ์ง€๋งŒ, ์™„์ฃผ์ž ๋ช…๋‹จ์—๋Š” ํ•œ ๋ช…๋ฐ–์— ์—†๊ธฐ ๋•Œ๋ฌธ์— ํ•œ๋ช…์€ ์™„์ฃผํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค.


ํ’€์ด ๊ณผ์ •

์ „์ฒด ์„ ์ˆ˜(participant) ์ค‘ ์™„์ฃผํ•œ ์„ ์ˆ˜(completion) ๋ชฉ๋ก์— ์กด์žฌํ•˜์ง€ ์•Š๋Š” ์„ ์ˆ˜ ํ•œ ๋ช…์„ ์ฐพ์•„๋‚ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


์‹œ๋„ 1

splice์™€ indexOf๋ฅผ ์ด์šฉํ•ด ์™„์ฃผํ•œ ์„ ์ˆ˜(completion)๋ฅผ ์ „์ฒด ์„ ์ˆ˜(participant)์—์„œ ํ•˜๋‚˜์”ฉ ์†Œ๊ฑฐํ•œ ๋’ค, ๋‚จ์€ ํ•œ ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ํ’€์–ด๋ดค์Šต๋‹ˆ๋‹ค.

function solution(participant, completion) {
  // ์ „์ฒด ์„ ์ˆ˜ ๋ชฉ๋ก์—์„œ ์™„์ฃผํ•œ ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ํ•˜๋‚˜์”ฉ ์†Œ๊ฑฐ
  for (name of completion) {
    participant.splice(participant.indexOf(name), 1);
  }

  // ์ „์ฒด ์„ ์ˆ˜ ๋ชฉ๋ก์—์„œ ๋‚จ์•„์žˆ๋Š” ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ๋ฐ˜ํ™˜
  return participant[0];
}

ํ•˜์ง€๋งŒ ์ •ํ™•๋„ ํ…Œ์ŠคํŠธ๋Š” ํ†ต๊ณผํ•˜๊ณ  ์‹œ๊ฐ„ ์ดˆ๊ณผ๋กœ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ๋Š” ํ†ต๊ณผํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ๋ฐฐ์—ด์„ ์ˆ˜์ •ํ•˜๋Š” splice๊ฐ€ ๋Š๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ์ƒ๊ธด ๋ฌธ์ œ์ธ ๋“ฏ ํ•ฉ๋‹ˆ๋‹ค.


์‹œ๋„ 2

์•„๋ž˜์™€ ๊ฐ™์ด ํ•ด์‰ฌ๋ฅผ ์ด์šฉํ•ด ๋ฌธ์ œ๋ฅผ ๋‹ค์‹œ ํ’€์—ˆ๊ณ , ์„ฑ๊ณต์ ์œผ๋กœ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ๊นŒ์ง€ ํ†ต๊ณผํ–ˆ์Šต๋‹ˆ๋‹ค.

function solution(participant, completion) {
  // ์™„์ฃผํ•œ ์„ ์ˆ˜์˜ ์ด๋ฆ„์˜ ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•  ๋ณ€์ˆ˜ ์„ ์–ธ
  const counts = {};

  // ์™„์ฃผํ•œ ์„ ์ˆ˜์˜ ์ด๋ฆ„์˜ ๊ฐœ์ˆ˜๋ฅผ `counts` ๋ณ€์ˆ˜์— ๋‹ด๊ธฐ
  for (name of completion) {
    if (counts[name]) {
      counts[name]++;
    } else {
      counts[name] = 1;
    }
  }

  for (name of participant) {
    if (counts[name]) {
      counts[name]--; // ์„ ์ˆ˜ ์ด๋ฆ„์ด ์žˆ์œผ๋ฉด ๊ฐœ์ˆ˜ 1 ๊ฐ์†Œ
    } else {
      return name; // ์„ ์ˆ˜ ์ด๋ฆ„์ด ์—†๊ฑฐ๋‚˜ 0์ด๋ฉด ํ•ด๋‹น ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ๋ฐ˜ํ™˜
    }
  }
}

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

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

function solution(participant, completion) {
  const counts = {};
  for (name of completion) counts[name] = (counts[name] | 0) + 1;
  for (name of participant) if (!counts[name]--) return name;
}
counts์— name์ด ์—†์„ ์ˆ˜๋„ ์žˆ๋Š”๋ฐ !counts[name]--์ด ์™œ ์ œ๋Œ€๋กœ ์ž‘๋™ํ•˜๋‚˜์š”?
  1. counts[name]๊ฐ€ ๋น„์–ด์žˆ์„ ๊ฒฝ์šฐ ์ ‘๊ทผํ•˜๋ฉด undefined๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.
  2. undefined๊ฐ€ ์‚ฐ์ˆ  ์—ฐ์‚ฐ์ž์™€ ๋งŒ๋‚˜๋ฉด ์˜ค๋ฅ˜ ์—†์ด NaN์œผ๋กœ ๋ฐ”๋€Œ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.
  3. NaN์€ ๋…ผ๋ฆฌ๊ฐ’ ๊ฑฐ์ง“์œผ๋กœ ๋ณ€ํ™˜๋˜๊ธฐ ๋•Œ๋ฌธ์—, !NaN์€ true๋กœ ๋ณ€ํ™˜๋ฉ๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ counts[name]์ด ์กด์žฌํ•˜์ง€ ์•Š์„ ๋•Œ, !counts[name]--๋Š” true์œผ๋กœ ๋ณ€ํ™˜๋ฉ๋‹ˆ๋‹ค.

์ด๋Ÿฌํ•œ ๊ณผ์ •์„ ํ†ตํ•ด ๋งคํ•‘๋œ ๊ฐ’์ด ์—†๋Š” ๊ฒฝ์šฐ์—๋„ ์„ ์ˆ˜์˜ ์ด๋ฆ„์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋กœ์ง์ด ์ •์ƒ์ ์œผ๋กœ ์ž‘๋™ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.


์ถ”๊ฐ€๋กœ counts ๊ฐ์ฒด ์ƒ์„ฑ ๋ผ์ธ์„ ์ œ๊ฑฐํ•˜๊ณ  completion ๋ฐฐ์—ด์„ ํ•ด์‰ฌ๋งต ์šฉ๋„๋กœ ์žฌ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.

function solution(participant, completion) {
  for (name of completion) completion[name] = (completion[name] | 0) + 1;
  for (name of participant) if (!completion[name]--) return name;
}
completion๋Š” ๋ฐฐ์—ด์ธ๋ฐ ์–ด๋–ป๊ฒŒ ํ‚ค๊ฐ’์„ ์ธ๋ฑ์Šค๋กœ ์‚ฌ์šฉ ํ•  ์ˆ˜ ์žˆ๋‚˜์š”?
  • ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ์—์„œ๋Š” ๋ฐฐ์—ด ๋˜ํ•œ Array๋ผ๋Š” ๊ฐ์ฒด์ด๊ธฐ ๋•Œ๋ฌธ์— ์†์„ฑ(property)์„ ์ถ”๊ฐ€ํ•  ์ˆ˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ completion[name]์ด๋ผ๋Š” ์ฝ”๋“œ๊ฐ€ ์ •์ƒ์ ์œผ๋กœ ์ž‘๋™ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

for-of๋ฅผ map()๊ณผ find() ๋ฉ”์†Œ๋“œ๋กœ ๋ฐ”๊พธ๊ณ  ํ•œ์ค„์˜ ์ฝ”๋“œ๋กœ ํ•ฉ์นฉ๋‹ˆ๋‹ค.

function solution(participant, completion) {
  completion.map((name) => (completion[name] = (completion[name] | 0) + 1));
  return participant.find((name) => !completion[name]--, completion);
}
solution = (participant, completion) =>
  participant.find(
    (name) => !completion[name]--,
    completion.map((name) => (completion[name] = (completion[name] | 0) + 1))
  );

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

solution=(p,c)=>p.find(n=>!c[n]--,c.map(n=>(c[n]=(c[n]|0)+1)))