프로그래머스/Level2(JS)

[프로그래머스] 예상 대진표 - JS

2023. 6. 1. 19:21
목차
  1. 예상 대진표
  2. ❓ 문제설명
  3. 🚫 제한조건
  4. ✔ 입출력 예
  5. 💡 풀이
  6. 📝 해설
728x90
반응형

예상 대진표

❓ 문제설명

△△ 게임대회가 개최되었습니다. 이 대회는 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 answer
8 4 7 3

💡 풀이

function solution(n,a,b) {
  // n/2 를 기준으로 서로 반대쪽에 있으면 마지막 라운드에서 만난다.
  if (Math.min(a,b) <= n/2 && Math.max(a,b) > n/2) {
    return n.toString(2).length - 1
  }

  // 절반 크기의 토너먼트로 셋팅해서 재귀하여 답을 구한다.
  return solution(n/2, ((a-1)%(n/2))+1, ((b-1)%(n/2))+1)
}

📝 해설

N 이 2의 지수로만 존재하므로 항상 절반씩 토너먼트가 진행된다. 따라서 재귀로 계속 토너먼트를 반복해여 만나는 경우를 찾는 방식으로 풀이하였다.

 

728x90
반응형
저작자표시 (새창열림)
  1. 예상 대진표
  2. ❓ 문제설명
  3. 🚫 제한조건
  4. ✔ 입출력 예
  5. 💡 풀이
  6. 📝 해설
'프로그래머스/Level2(JS)' 카테고리의 다른 글
  • [프로그래머스] N개의 최소공배수 - JS
  • [프로그래머스] 점프와 순간 이동 - JS
  • [프로그래머스] 구명보트 - JS
  • [프로그래머스] 카펫 - JS
KimBY
KimBY
웹개발과 관련된 개발지식 모음
KimBY
B.Y Kim의 개발노트
KimBY
전체
오늘
어제
  • 분류 전체보기 (99)
    • 사소한 개발지식 (49)
      • PHP (2)
      • JavaScript (15)
      • NodeJS (0)
      • JAVA (2)
      • 잡?지식 (4)
      • 로드맵(FE) (22)
      • React (4)
    • 개발노트 (6)
      • 포트폴리오사이트 (6)
    • 프로그래머스 (33)
      • Level1(JS) (0)
      • Level2(JS) (33)
    • 백준알고리즘 (11)
      • 단계별로 풀어보기3(for문) (11)
    • 잡담 (0)

인기 글

최근 글

최근 댓글

태그

  • FE로드맵
  • 로드맵
  • frontend
  • Level2
  • 단계별로풀어보기
  • 프로그래머스
  • 백준알고리즘
  • react
  • CSS
  • javascript
hELLO · Designed By 정상우.
KimBY
[프로그래머스] 예상 대진표 - JS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.