Home πŸ„πŸ»β€β™€οΈ [μžλ°”μŠ€ν¬λ¦½νŠΈ] 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°
Post
Cancel

πŸ„πŸ»β€β™€οΈ [μžλ°”μŠ€ν¬λ¦½νŠΈ] 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°

πŸ“„ 문제

ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 2022 KAKAO TECH INTERNSHIP 두 큐 ν•© κ°™κ²Œ λ§Œλ“€κΈ°

κ΅¬ν˜„ν•΄μ•Ό ν•˜λŠ” 것은

주어진 두 개의 배열에 μžˆλŠ” μš”μ†Œλ“€μ˜ 합이 κ°™μ•„μ•Ό ν•œλ‹€. 각 λ°°μ—΄ μš”μ†Œμ˜ 총합이 같지 μ•ŠμœΌλ©΄, λ°°μ—΄ κ°„ μš”μ†Œλ“€μ„ μ΄λ™ν•˜μ—¬ 합을 μΌμΉ˜μ‹œν‚¨λ‹€.

이 λ•Œ, 이동 κ·œμΉ™μ€ λ‹€μŒκ³Ό κ°™λ‹€.

  • 본인 λ°°μ—΄μ˜ 총합이 크닀고 νŒλ‹¨λ˜μ–΄ μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  싢을 λ•ŒλŠ” 본인 λ°°μ—΄μ˜ 첫 번째 μš”μ†ŒλΆ€ν„° μ œκ±°ν•΄μ•Ό ν•œλ‹€.
  • 본인 λ°°μ—΄μ˜ 총합이 μž‘λ‹€κ³  νŒλ‹¨λ˜μ–΄ μƒλŒ€ λ°°μ—΄μ˜ μš”μ†Œλ₯Ό μΆ”κ°€ν•˜κ³  싢을 λ•ŒλŠ” μƒλŒ€ λ°°μ—΄μ˜ 첫 번째 μš”μ†Œλ₯Ό μ œκ±°ν•˜κ³  κ·Έ 값을 본인 λ°°μ—΄μ˜ λ§ˆμ§€λ§‰ μš”μ†Œλ‘œ μ‚½μž…ν•œλ‹€.

단, μ–΄λ–€ λ°©λ²•μœΌλ‘œλ„ 각 λ°°μ—΄μ˜ μ›μ†Œ 합을 κ°™κ²Œ λ§Œλ“€ 수 μ—†λŠ” κ²½μš°λ„ μ‘΄μž¬ν•œλ‹€.

κ°„λ‹¨ν•˜κ²Œ μƒκ°ν•˜λ©΄ ν•˜λ‚˜μ˜ 배열을 κΈ°μ€€μœΌλ‘œ μƒλŒ€ λ°°μ—΄μ˜ shift(λ°°μ—΄μ˜ 첫 번째 μš”μ†Œλ₯Ό μ œκ±°ν•œλ‹€.) μš”μ†Œλ₯Ό push(λ°°μ—΄μ˜ λ§ˆμ§€λ§‰ μš”μ†Œλ‘œ μ‚½μž…ν•œλ‹€.)ν•˜κ³  μƒˆλ‘œμš΄ 합을 κ΅¬ν•˜κΈ° μœ„ν•΄ reduce(배열을 λ°˜λ³΅ν•˜λ©° μ‚¬μš©μž μ •μ˜ ν•¨μˆ˜μ— 따라 값을 λˆ„μ ν•œλ‹€.)둜 합을 κ΅¬ν•˜λ©΄ λœλ‹€. ν•˜μ§€λ§Œ shift와 reduceλŠ” μ‹œκ°„ λ³΅μž‘λ„κ°€ 큰 ν•¨μˆ˜λ“€μ΄λ‹€. λ”°λΌμ„œ 이 λ¬Έμ œμ—μ„œ μ‚¬μš©ν•˜λ©΄ μ‹œκ°„μ΄ˆκ³Όκ°€ λ°œμƒν•œλ‹€.

ν•˜λ‚˜μ˜ λ°°μ—΄λ‘œ λ§Œλ“  ν›„, (인덱슀 λ³€μˆ˜λ‘œ μ‹œμž‘μ κ³Ό 끝점을 μˆ˜μ •ν•˜λ©° ν•΄λ‹Ή μ˜μ—­μ— ν¬ν•¨λœ μš”μ†Œλ“€μ˜ ν•©)κ³Ό (κ·Έ μ™Έ μš”μ†Œλ“€μ˜ ν•©)을 λΉ„κ΅ν•˜λ©΄ λœλ‹€. 각 μ˜μ—­μ˜ 총합이 κ°™μ•„μ§€κ±°λ‚˜ λ°°μ—΄μ˜ λκΉŒμ§€ λ°˜λ³΅ν•  λ•ŒκΉŒμ§€ μ‹œμž‘μ  λ˜λŠ” 끝점을 μˆ˜μ •ν•˜λ©° μ˜μ—­λ³„ 합을 λΉ„κ΅ν•˜λ©° μ΅œμ’… 결과값인 μž‘μ—… 횟수λ₯Ό λˆ„μ ν•œλ‹€.

1️⃣ νŒŒλΌλ―Έν„°λ‘œ μ „λ‹¬λœ 두 배열을 ν•˜λ‚˜λ‘œ ν•©μΉœλ‹€.

ꡬ쑰 λΆ„ν•΄ ν• λ‹Ή ꡬ문을 μ‚¬μš©ν•΄μ„œ 두 배열을 합쳐 μƒˆλ‘œμš΄ λ°°μ—΄ totalQueueλ₯Ό μ„ μ–Έν•œλ‹€.

그리고 totalQueue μš”μ†Œλ“€μ˜ ν•©μ˜ 절반 값을 κ΅¬ν•΄μ•Όν•œλ‹€. 두 개의 λ°°μ—΄ 각자의 총합이 κ°™μ•„μ•Ό ν•˜λ―€λ‘œ μ‹œμž‘μ κ³Ό 끝점을 μ΄μš©ν•˜μ—¬ μ§€μ •ν•œ μ˜μ—­ λ‚΄ μš”μ†Œλ“€μ˜ 합이 총합 / 2이 λ˜λŠ” μ˜μ—­μ„ 찾을 것이기 λ•Œλ¬Έμ΄λ‹€.

두 개의 λ°°μ—΄ 합은 같은 값을 κ°€μ Έμ•Όν•˜κΈ° λ•Œλ¬Έμ— 총합 / 2의 값이 ν™€μˆ˜λΌλ©΄ μ–΄λ–€ λ°©λ²•μœΌλ‘œλ„ 각자의 합을 κ°™κ²Œ λ§Œλ“€ 수 μ—†μœΌλ―€λ‘œ μ’…λ£Œν•œλ‹€.

1
2
3
4
5
6
const solution = (queue1, queue2) => {
  const totalQueue = [...queue1, ...queue2];
  const halfOfSum = totalQueue.reduce((acc, cur) => acc + cur, 0) / 2;

  if (halfOfSum % 1 !== 0) return -1;
};

2️⃣ μ‹œμž‘μ κ³Ό 끝점을 μ΄ˆκΈ°ν™”ν•˜κ³  배열을 μˆœνšŒν•˜λ©° μš”μ†Œλ“€μ˜ 합이 β€˜μ΄ν•© / 2β€™μ˜ 값인 μ˜μ—­μ„ μ°ΎλŠ”λ‹€.

μ‹œμž‘μ  startλŠ” λ°°μ—΄μ˜ μ‹œμž‘ 인덱슀인 0으둜 μ΄ˆκΈ°ν™”ν•œλ‹€. 끝점 endλŠ” νŒŒλΌλ―Έν„°λ‘œ μ „λ‹¬λ°›μ•˜λ˜ νλ“€μ˜ 길이둜 μ΄ˆκΈ°ν™”ν•œλ‹€. 전달받을 λ‹Ήμ‹œμ˜ 2개의 νλŠ” 길이가 κ°™κΈ° λ•Œλ¬Έμ— μ–΄λŠ ν•œ μͺ½μ˜ 값을 할당해도 λ™μΌν•˜λ‹€.

그러면 처음 합을 ꡬ할 μ˜μ—­μ˜ 합을 κ΅¬ν•˜κ³  이 값에 따라 μ˜μ—­μ˜ 기쀀점듀을 μˆ˜μ •ν•΄μ•Ό ν•œλ‹€.

  • start ~ endμ˜μ—­μ˜ 합이 총합 / 2κ°€ κ°™λ‹€λ©΄ ν•œμͺ½ μ˜μ—­μ€ 합이 같아지기 μœ„ν•œ 쑰건을 λ§Œμ‘±μ‹œν‚€λ―€λ‘œ start ~ endμ˜μ—­ 이 μ™Έμ˜ λ‚˜λ¨Έμ§€ μš”μ†Œλ“€μ˜ 합을 ꡬ해야 ν•œλ‹€.
    • λ‚˜λ¨Έμ§€ μš”μ†Œλ“€μ˜ 합이 start ~ end μ˜μ—­μ˜ ν•©κ³Ό κ°™λ‹€λ©΄ μž‘μ—… 횟수λ₯Ό λ¦¬ν„΄ν•œλ‹€.
    • λ‚˜λ¨Έμ§€ μš”μ†Œλ“€μ˜ 합이 start ~ end μ˜μ—­μ˜ ν•©κ³Ό 같지 μ•Šλ‹€λ©΄ 각 λ°°μ—΄μ˜ 합은 κ°™κ²Œ λ§Œλ“€ 수 μ—†μŒμ„ μ˜λ―Έν•œλ‹€. κ·ΈλŸ¬λ―€λ‘œ -1을 λ¦¬ν„΄ν•œλ‹€.
  • start ~ endμ˜μ—­μ˜ 합이 총합 / 2보닀 크면 값을 쀄여야 ν•œλ‹€. κ·ΈλŸ¬λ―€λ‘œ startλ₯Ό 1만큼 μ¦κ°€μ‹œν‚¨λ‹€. μ΄λŠ” 이동 κ·œμΉ™ 쀑 μš”μ†Œλ₯Ό κΊΌλ‚Ό λ•Œμ—λŠ” 본인 λ°°μ—΄μ˜ 첫 번째 μš”μ†Œλ₯Ό 선택해야 ν•œλ‹€λŠ” 것을 λ§Œμ‘±ν•œλ‹€.
  • start ~ endμ˜μ—­μ˜ 합이 총합 / 2보닀 μž‘μœΌλ©΄ 값을 μΆ”κ°€ν•΄μ•Ό ν•œλ‹€. κ·ΈλŸ¬λ―€λ‘œ endλ₯Ό 1만큼 μ¦κ°€μ‹œν‚¨λ‹€. μ΄λŠ” 이동 κ·œμΉ™ 쀑 μš”μ†Œλ₯Ό μΆ”κ°€ν•  λ•Œμ—λŠ” μƒλŒ€ λ°°μ—΄μ˜ 첫 번째 μš”μ†Œλ₯Ό 선택해야 본인 λ°°μ—΄μ˜ λ§ˆμ§€λ§‰ μš”μ†Œλ‘œ μ‚½μž…ν•œλ‹€λŠ” 것을 λ§Œμ‘±ν•œλ‹€.

문제 μ„€λͺ…μ—μ„œ 주어진 μ˜ˆμ‹œλ‘œ λ‹€μ‹œ μ •λ¦¬ν•΄λ³΄μž.

queue1 = [3,2,7,2], queue2 = [4,6,5,1]둜 길이가 4인 두 개의 큐가 주어진닀. λ”°λΌμ„œ startλŠ” 0으둜, endλŠ” 4둜 μ΄ˆκΈ°ν™”ν•œλ‹€.

그리고 두 개의 큐λ₯Ό ν•©ν•˜μ—¬ [3,2,7,2,4,6,5,1]λΌλŠ” μƒˆλ‘œμš΄ 배열을 μƒμ„±ν•œλ‹€. λ°°μ—΄μ˜ 총합은 30이며 그의 절반 값은 15이닀. 즉, μš”μ†Œμ˜ 합이 15κ°€ λ˜λŠ” ꡬ간을 μ°Ύμ•„μ•Ό ν•œλ‹€.

start와 end에 따라 처음 합을 ꡬ할 μ˜μ—­μ€ [3,2,7,2]λ‹€. 합은 14둜 절반 값보닀 μž‘λ‹€. κ·ΈλŸ¬λ―€λ‘œ μ˜μ—­μ„ λ„“ν˜€μ•Ό ν•œλ‹€. κ·œμΉ™μ— 따라 λμ μ—μ„œ 였λ₯Έμͺ½μœΌλ‘œ 1만큼 μ΄λ™ν•œλ‹€.

이제 startλŠ” 0, endλŠ” 5이닀.

endκ°€ 4μž„μ—λ„ totalQueue[3]κΉŒμ§€λ§Œ μ˜μ—­μ„ μ§€μ •ν•˜λŠ” 이유

λ°°μ—΄μ˜ μΌλΆ€λΆ„λ§Œ κ°€μ Έμ˜€κΈ° μœ„ν•΄ slice ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•œλ‹€. sliceλŠ” μ‹œμž‘ μΈλ±μŠ€λΆ€ν„° μ’…λ£Œ 인덱슀 μ „κΉŒμ§€λ§Œ λ°˜ν™˜ν•˜κΈ° λ•Œλ¬Έμ΄λ‹€. (substringκ³Ό λ™μΌν•˜λ‹€κ³  μƒκ°ν•˜μž.)

즉, λ°°μ—΄μ˜ slice ν•¨μˆ˜μ˜ μ‹œμž‘μ κ³Ό 끝점을 κΈ°μ€€μœΌλ‘œ start와 endλ₯Ό μ„€μ •ν•˜μ˜€λ‹€λŠ” 것을 λͺ…μ‹¬ν•˜μž.

합을 ꡬ할 μ˜μ—­μ€ ν•œ μΉΈ λŠ˜μ–΄μ„œ [3,2,7,2,4]λ‹€. 합은 18둜 절반 값보닀 크닀. κ·ΈλŸ¬λ―€λ‘œ μ˜μ—­μ„ 쀄여야 ν•œλ‹€. κ·œμΉ™μ— 따라 μ‹œμž‘μ μ—μ„œ μ™Όμͺ½μœΌλ‘œ 1만큼 μ΄λ™ν•œλ‹€.

이제 startλŠ” 1, endλŠ” 5이닀.

합을 ꡬ할 μ˜μ—­μ€ ν•œ μΉΈ 쀄어듀어 [2,7,2,4]λ‹€. 합은 15둜 절반 값보닀 μ •ν™•νžˆ μΌμΉ˜ν•œλ‹€! 이제 ν•΄λ‹Ή μ˜μ—­μ΄ μ•„λ‹Œ λ‚˜λ¨Έμ§€ μš”μ†Œλ“€μ˜ 합을 확인해야 ν•œλ‹€.

각 큐의 합이 κ°™μ•„μ§€λŠ” ꡬ간은 [2,7,2,4], [3,6,5,1]이닀.


두 번째 μ˜ˆμ œλŠ” queue1 = [1,2,1,2], queue2 = [1,10,1,2]둜 주어진닀. μœ„μ˜ 과정을 거치며 μ΅œμ’…μ μœΌλ‘œ μ•„λž˜μ™€ 같이 μ˜μ—­μ΄ λΆ„λ¦¬λœλ‹€.

🏹 μ½”λ“œ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const solution = (queue1, queue2) => {
  const totalQueue = [...queue1, ...queue2];
  const halfOfSum = totalQueue.reduce((acc, cur) => acc + cur, 0) / 2;

  if (halfOfSum % 1 !== 0) return -1;

  let start = 0,
    end = queue1.length;
  let result = 0;
  let sum = totalQueue.slice(start, end).reduce((acc, cur) => acc + cur, 0);

  while (end <= totalQueue.length) {
    if (sum < halfOfSum) {
      sum += totalQueue[end++];
      result++;
    } else if (sum > halfOfSum) {
      sum -= totalQueue[start++];
      result++;
    } else {
      const a = totalQueue
        .splice(start, end - start)
        .reduce((acc, cur) => acc + cur, 0);
      const b = totalQueue.reduce((acc, cur) => acc + cur, 0);

      if (a === b) return result;
      else return -1;
      break;
    }
  }

  return -1;
};
This post is licensed under CC BY 4.0 by the author.

🌈 μž¬λ―ΈμžˆλŠ” μžλ°”μŠ€ν¬λ¦½νŠΈ 세계 - ν”„λ‘œν† νƒ€μž…

πŸ“Έ 2022-11-07