πŸ… ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 12985 : μ˜ˆμƒ λŒ€μ§„ν‘œ - Javascript

문제 μ„€λͺ…

β–³β–³ κ²Œμž„λŒ€νšŒκ°€ κ°œμ΅œλ˜μ—ˆμŠ΅λ‹ˆλ‹€. 이 λŒ€νšŒλŠ” Nλͺ…이 μ°Έκ°€ν•˜κ³ , ν† λ„ˆλ¨ΌνŠΈ ν˜•μ‹μœΌλ‘œ μ§„ν–‰λ©λ‹ˆλ‹€. Nλͺ…μ˜ μ°Έκ°€μžλŠ” 각각 1λΆ€ν„° Nλ²ˆμ„ μ°¨λ‘€λŒ€λ‘œ λ°°μ •λ°›μŠ΅λ‹ˆλ‹€. 그리고, 1λ²ˆβ†”2번, 3λ²ˆβ†”4번, … , N-1λ²ˆβ†”N번의 μ°Έκ°€μžλΌλ¦¬ κ²Œμž„μ„ μ§„ν–‰ν•©λ‹ˆλ‹€. 각 κ²Œμž„μ—μ„œ 이긴 μ‚¬λžŒμ€ λ‹€μŒ λΌμš΄λ“œμ— μ§„μΆœν•  수 μžˆμŠ΅λ‹ˆλ‹€. μ΄λ•Œ, λ‹€μŒ λΌμš΄λ“œμ— μ§„μΆœν•  μ°Έκ°€μžμ˜ λ²ˆν˜ΈλŠ” λ‹€μ‹œ 1λ²ˆλΆ€ν„° N/2λ²ˆμ„ μ°¨λ‘€λŒ€λ‘œ λ°°μ •λ°›μŠ΅λ‹ˆλ‹€. λ§Œμ•½ 1λ²ˆβ†”2번 끼리 κ²¨λ£¨λŠ” κ²Œμž„μ—μ„œ 2번이 μŠΉλ¦¬ν–ˆλ‹€λ©΄ λ‹€μŒ λΌμš΄λ“œμ—μ„œ 1λ²ˆμ„ λΆ€μ—¬λ°›κ³ , 3λ²ˆβ†”4λ²ˆμ—μ„œ κ²¨λ£¨λŠ” κ²Œμž„μ—μ„œ 3번이 μŠΉλ¦¬ν–ˆλ‹€λ©΄ λ‹€μŒ λΌμš΄λ“œμ—μ„œ 2λ²ˆμ„ λΆ€μ—¬λ°›κ²Œ λ©λ‹ˆλ‹€. κ²Œμž„μ€ μ΅œμ’… ν•œ λͺ…이 남을 λ•ŒκΉŒμ§€ μ§„ν–‰λ©λ‹ˆλ‹€.

μ΄λ•Œ, 처음 λΌμš΄λ“œμ—μ„œ Aλ²ˆμ„ 가진 μ°Έκ°€μžλŠ” 경쟁자둜 μƒκ°ν•˜λŠ” B번 μ°Έκ°€μžμ™€ λͺ‡ 번째 λΌμš΄λ“œμ—μ„œ λ§Œλ‚˜λŠ”μ§€ κΆκΈˆν•΄μ‘ŒμŠ΅λ‹ˆλ‹€. κ²Œμž„ μ°Έκ°€μž 수 N, μ°Έκ°€μž 번호 A, 경쟁자 번호 Bκ°€ ν•¨μˆ˜ solution의 λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§ˆ λ•Œ, 처음 λΌμš΄λ“œμ—μ„œ Aλ²ˆμ„ 가진 μ°Έκ°€μžλŠ” 경쟁자둜 μƒκ°ν•˜λŠ” B번 μ°Έκ°€μžμ™€ λͺ‡ 번째 λΌμš΄λ“œμ—μ„œ λ§Œλ‚˜λŠ”μ§€ return ν•˜λŠ” solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄ μ£Όμ„Έμš”. 단, A번 μ°Έκ°€μžμ™€ B번 μ°Έκ°€μžλŠ” μ„œλ‘œ λΆ™κ²Œ 되기 μ „κΉŒμ§€ 항상 이긴닀고 κ°€μ •ν•©λ‹ˆλ‹€.


μ œν•œμ‚¬ν•­

  • N : 21 이상 220 μ΄ν•˜μΈ μžμ—°μˆ˜ (2의 μ§€μˆ˜ 승으둜 μ£Όμ–΄μ§€λ―€λ‘œ λΆ€μ „μŠΉμ€ λ°œμƒν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.)
  • A, B : N μ΄ν•˜μΈ μžμ—°μˆ˜ (단, A β‰  B μž…λ‹ˆλ‹€.)

μž…μΆœλ ₯ 예

N A B
8 4 7
  • 예제 #1 첫 번째 λΌμš΄λ“œμ—μ„œ 4번 μ°Έκ°€μžλŠ” 3번 μ°Έκ°€μžμ™€ λΆ™κ²Œ 되고, 7번 μ°Έκ°€μžλŠ” 8번 μ°Έκ°€μžμ™€ λΆ™κ²Œ λ©λ‹ˆλ‹€. 항상 이긴닀고 κ°€μ •ν–ˆμœΌλ―€λ‘œ 4번 μ°Έκ°€μžλŠ” λ‹€μŒ λΌμš΄λ“œμ—μ„œ 2번이 되고, 7번 μ°Έκ°€μžλŠ” 4번이 λ©λ‹ˆλ‹€. 두 번째 λΌμš΄λ“œμ—μ„œ 2λ²ˆμ€ 1번과 λΆ™κ²Œ 되고, 4λ²ˆμ€ 3번과 λΆ™κ²Œ λ©λ‹ˆλ‹€. 항상 이긴닀고 κ°€μ •ν–ˆμœΌλ―€λ‘œ 2λ²ˆμ€ λ‹€μŒ λΌμš΄λ“œμ—μ„œ 1번이 되고, 4λ²ˆμ€ 2번이 λ©λ‹ˆλ‹€. μ„Έ 번째 λΌμš΄λ“œμ—μ„œ 1번과 2번으둜 두 μ°Έκ°€μžκ°€ λΆ™κ²Œ λ˜λ―€λ‘œ 3을 return ν•˜λ©΄ λ©λ‹ˆλ‹€.

풀이 κ³Όμ • - μ‹œλ„ 1 : μ‹€μ œλ‘œ λΌμš΄λ“œ 진행 (성곡)

κ°€μž₯ λ‹¨μˆœν•˜κ²Œ μ£Όμ–΄μ§„λŒ€λ‘œ λͺ¨λ“  λΌμš΄λ“œλ₯Ό 직접 진행해 κ²°κ³Όλ₯Ό μ°ΎλŠ” λ°©μ‹μœΌλ‘œ κ΅¬ν˜„ν–ˆμŠ΅λ‹ˆλ‹€. ꡉμž₯히 λΉ„νš¨μœ¨μ μ΄μ§€λ§Œ μ‹€μ œλ‘œ 잘 μž‘λ™ν•˜κ³ , ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€λ„ λͺ¨λ‘ ν†΅κ³Όν–ˆμŠ΅λ‹ˆλ‹€.

function solution(n, a, b) {
  //λŒ€μ§„ν‘œ μž‘μ„±
  //a와 bλŠ” 1, λ‚˜λ¨Έμ§€λŠ” 0으둜 μ €μž₯
  const table = [];
  for (let i = 0; i < n; ++i) {
    table[i] = Number(a - 1 === i || b - 1 === i);
  }

  //0λΆ€ν„° nκΉŒμ§€μ˜ λŒ€μ§„ν‘œλ₯Ό μˆœνšŒν•œ ν›„ n을 반으둜 λ‚˜λˆ„λ©° 반볡 진행
  let round = 0;
  for (let i = n; n > 1; n /= 2) {
    round++;

    //λΌμš΄λ“œ κ²°κ³ΌλŠ” λ§μ…ˆμœΌλ‘œ κ°„λ‹¨ν•˜κ²Œ 계산
    for (let j = 0; j < n; j += 2) {
      table[j / 2] = table[j] + table[j + 1];

      //λΌμš΄λ“œ κ²°κ³Όκ°€ 2인 경우 a와 bκ°€ λ§Œλ‚œ κ²ƒμ΄λ―€λ‘œ λΌμš΄λ“œλ₯Ό λ°˜ν™˜
      if (table[j / 2] === 2) {
        return round;
      }
    }
  }
}
n=8,a=4,b=7n=8, a=4, b=7 의 경우 진행 방식
round table μ„€λͺ…
0 [0, 0, 0, 1, 0, 0, 1, 0] table λ°°μ—΄ 생성
1 [0, 1, 0, 1] λΌμš΄λ“œ 진행
2 [1, 1] λΌμš΄λ“œ 진행
3 [2] 2κ°€ λ˜μ–΄ round λ°˜ν™˜

(table λ°°μ—΄μ˜ 1은 각각 a와 bλ₯Ό μ˜λ―Έν•©λ‹ˆλ‹€)


풀이 κ³Όμ • - μ‹œλ„ 2 : A와 Bλ₯Ό 2둜 λ‚˜λˆ„λ©° 비ꡐ

μ‹œλ„ 1의 λ°©μ‹μ—μ„œλŠ” λΌμš΄λ“œκ°€ 진행 될 λ•Œλ§ˆλ‹€ 배열이 반으둜 쀄어듀긴 ν•˜μ§€λ§Œ μ˜λ―Έμ—†λŠ” 0값듀에 λŒ€ν•œ 연산이 반볡되기 λ•Œλ¬Έμ— ꡉμž₯히 λΉ„νš¨μœ¨μ μž…λ‹ˆλ‹€. 사싀상 λͺ¨λ“  0은 μ˜λ―Έκ°€ μ—†λŠ” 값이기 λ•Œλ¬Έμ— 배열없이 효율적으둜 a와 b만 μ΄μš©ν•΄ λΌμš΄λ“œ 값을 찾을 방법을 κ³ λ―Όν•΄λ΄€μŠ΅λ‹ˆλ‹€.

λ¨Όμ € μ‹œλ„1μ—μ„œ a와 bκ°€ ν¬ν•¨λ˜μ§€ μ•Šμ€ λͺ¨λ“  λΌμš΄λ“œ 계산이 μ˜λ―Έκ°€ μ—†κΈ° λ•Œλ¬Έμ— μƒλž΅ν•  ν•„μš”κ°€ μžˆμŠ΅λ‹ˆλ‹€. 이λ₯Ό μœ„ν•΄ a와 bκ°€ μ–΄λ–»κ²Œ μ΄λ™ν•˜λŠ”μ§€λ₯Ό νŒŒμ•…ν•΄λ³΄λ©΄ μ•„λž˜μ™€ κ°™μŠ΅λ‹ˆλ‹€.

n=8,a=4,b=7n=8, a=4, b=7 의 경우 a와 b의 인덱슀 λ³€ν™”
round a b
0 3 (4번째 μ„ μˆ˜) 6 (7번째 μ„ μˆ˜)
1 1 (2번째 μ„ μˆ˜) 3 (4번째 μ„ μˆ˜)
2 0 (1번째 μ„ μˆ˜) 1 (2번째 μ„ μˆ˜)
3 0 (1번째 μ„ μˆ˜) 0 (1번째 μ„ μˆ˜)

a와 bκ°€ λΌμš΄λ“œκ°€ 진행 될 λ•Œλ§ˆλ‹€ 2둜 λ‚˜λˆˆ κ°’μ˜ 올림으둜 λ³€κ²½λ˜κ³ , 이 값이 κ°™μ•„μ§ˆ λ•Œ λΌμš΄λ“œ κ²°κ³Όλ₯Ό λ°˜ν™˜ν•˜κ²Œ λœλ‹€λŠ” 것을 νŒŒμ•…ν–ˆμŠ΅λ‹ˆλ‹€. κ·Έ ν›„ 이 λ°©μ‹λŒ€λ‘œ μž‘λ™ν•˜λ„λ‘ μˆ˜μ •ν•΄ μ½”λ“œλ₯Ό κ°œμ„ ν–ˆμŠ΅λ‹ˆλ‹€.

κ·Έ κ²°κ³Ό ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€ μ‹€ν–‰ μ‹œκ°„μ΄ 평균 11.92msμ—μ„œ 0.04ms둜 μ›”λ“±νžˆ λΉ¨λΌμ‘ŒμŠ΅λ‹ˆλ‹€. λ˜ν•œ, 배열을 μ‚¬μš©ν•œ 탓에 27~34번 ν…ŒμŠ€νŠΈμΌ€μ΄μŠ€μ—μ„œ λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰μ΄ 30λ©”κ°€ 더 μ¦κ°€ν•˜λ˜ 증상이 μ‚¬λΌμ‘ŒμŠ΅λ‹ˆλ‹€.

function solution(n, a, b) {
  let round = 0;
  while (a !== b) {
    //a와 bκ°€ κ°™μ•„μ§ˆ λ•ŒκΉŒμ§€ 반볡
    round++; //λΌμš΄λ“œ 진행

    //a와 bλ₯Ό 2둜 λ‚˜λˆ„κ³  올림
    a = Math.ceil(a / 2);
    b = Math.ceil(b / 2);
  }
  return round;
}