[프로그래머스] JavaScript Lv2 - 예상 대진표(12985)

개요

문제 이름: 예상 대진표 (12985)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12985
플랫폼: 프로그래머스
알고리즘 분류: 일반
소요 시간: 30분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 토너먼트 형식의 대회에서 두 참가자가 몇 번째 라운드에서 만나는지를 찾는 문제입니다. 문제를 해결하기 위해서는 라운드를 진행하면서 A와 B의 위치를 업데이트하는 방식을 사용할 수 있습니다.

 

문제에서 주어진 조건은 다음과 같습니다.

1. N명의 참가자는 1부터 N번까지 번호를 배정받습니다.
2. 1번 <-> 2번, 3번 <-> 4번, ... , N-1번<->N번의 참가자끼리 게임을 진행합니다.
3. 각 게임에서 이긴 사람은 다음 라운드에 진출합니다.
4. 다음 라운드에 진출할 참가자의 번호는 1번부터 N/2번까지 다시 배정받습니다.
5. A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

 

문제 해결을 위해 다음과 같은 접근 방식을 사용할 수 있습니다.

1. 초기 라운드 수를 0으로 설정합니다.
2. A와 B가 서로 다른 동안 반복합니다.
   1. 라운드 수를 1 증가시킵니다.
   2. A와 B의 다음 라운드 위치를 계산합니다.
      1. 짝수인 경우: 현재 위치를 2로 나눕니다.
      2. 홀수인 경우: 현재 위치에 1을 더하고 2로 나눕니다.
3. A와 B가 같아지면 반복을 종료하고 현재 라운드 수를 반환합니다.

 

시도

1차 시도  (성공)

function solution(N, A, B) {
	let round = 0;

	// A와 B가 다른 동안 계속 반복
	while (A !== B) {
		round = round + 1; // 라운드 수 증가

		// A의 다음 라운드 위치 계산
		if (A % 2 === 0) {
			// A가 짝수면
			A = A / 2;
		} else {
			// A가 홀수면
			A = (A + 1) / 2;
		}

		// B의 다음 라운드 위치 계산
		if (B % 2 === 0) {
			// B가 짝수면
			B = B / 2;
		} else {
			// B가 홀수면
			B = (B + 1) / 2;
		}
	}

	return round; // 최종 라운드 수 반환
}

이 코드에서는 A와 B가 서로 다른 동안 반복하면서 라운드 수를 증가시키고, A와 B의 다음 라운드 위치를 계산합니다. A와 B의 위치는 짝수인 경우 2로 나누고, 홀수인 경우 1을 더한 후 2로 나눕니다. 이 과정을 A와 B가 같아질 때까지 반복하고, 최종 라운드 수를 반환합니다.

 

시간복잡도: O(log N) - 매 라운드마다 참가자 번호가 대략 절반으로 줄어듦

공간복잡도: O(1) - 추가적인 자료구조를 사용하지 않고 몇 개의 변수만 사용

 

2차 시도  (성공)

function solution(N, A, B) {
	let round = 0;

	// 라운드를 진행하면서 A와 B의 위치를 업데이트
	while (A !== B) {
		round++;
		// A와 B를 다음 라운드의 위치로 업데이트
		A = Math.ceil(A / 2);
		B = Math.ceil(B / 2);
	}

	return round;
}

2차 시도에서는 Math.ceil() 메서드를 사용하여 A와 B의 다음 라운드 위치를 계산합니다. Math.ceil() 메서드는 주어진 숫자보다 크거나 같은 가장 작은 정수를 반환하므로, 홀수인 경우에도 올바른 다음 라운드 위치를 계산할 수 있습니다. 이를 통해 1차 시도에서의 조건문을 제거하고 코드를 간결하게 만들 수 있습니다.

시간복잡도: O(log N)

공간복잡도: O(1)

 

사용된 메서드

Math.ceil(4.2) // 결과: 5
Math.ceil(4.7) // 결과: 5
Math.ceil(-4.2) // 결과: -4

• Math.ceil(x): 주어진 숫자 x보다 크거나 같은 가장 작은 정수를 반환합니다. 즉, 소수점 이하를 올림합니다.