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

문제내용

https://programmers.co.kr/learn/courses/30/lessons/12985

코딩테스트 연습 - 예상 대진표

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

---

문제 접근 방법

문제는 토너먼트식으로 라운드를 하나씩 진행해나가는 식이다. 처음 문제를 보고 '한라운드 = 반복문 한번' 이라고 생각하고 풀었다. 그리고 나서 반복문 코드를 두 가지 경우를 생각했다.

 

1. a,b가 대진표 중간값(mid) 기준으로 갈라진 경우.
예를들어 1 2 3 4 5 6 7 8 의 대진표에서 a=3, b=8 일때는 mid(4)값 기준으로 갈라진 경우이다.

이때 mid = n/2 로 표현 할 수 있다.

a,b가 mid기준으로 나눠진경우는 무조건 토너먼트 마지막(결승)에서 만나게 된다.

 

2. a,b가 mid값 기준으로 한쪽에 쏠린 경우

예를들어 1 2 3 4 5 6 7 8 의 대진표에서 a=5, b=8 일때 mid(4)값 기준으로 한쪽에 쏠린 경우이다.

이경우는 중간에 a,b가 만나게 돼서 a,b의 값을 재할당 해주는 과정이 필요하다. 그래서

분기문을 통해 a,b가 홀수이면 짝수로 증가시키고 만약 a==b 가 되는 시점이 온다면 a와 b는 1차이가 나는것으로 서로 만난다는 의미이고 이때 함수를 종료시키는 조건으로 풀었다.

그리고 만약 a!=b라면 a와 b를 2로 나눈값으로 재할당해주고 위의 과정을 반복해준다.

이 풀이는 문제에서 무조건 (홀수,짝수)가 한라운드를 치룬다는 특징을 이용했다.

 

위의 두가지 경우를 통해 문제를 풀었고 자세한 내용은 풀이를 보자.

 

---

풀이

public class Solution {
	public static int solution(int n, int a, int b) {
		int answer=1; 
		int mid = n/2;//중간값
		
		//예외처리
		if(a==mid && b!=mid+1 && Math.abs(a-b)==1) return answer;
		if(b==mid && a!=mid+1 && Math.abs(a-b)==1) return answer;		
				
		//mid값 기준으로 a,b가 왼쪽 오른쪽으로 나눠져있을때
		if((a<=mid && b>mid) || (b<=mid && a>mid)) {
			while(mid>1) {//어찌됐든 무조건 마지막 라운드까지 가야됨.
				answer++;
				mid /= 2;
			}
		}
		//a,b가 한곳에 쏠려있을때
		else if((a<=mid && b<=mid) || (a>mid && b>mid)){
			while(mid>1) {
				//홀수일경우 1증가 시켜서 짝수로 만듦
				if(a%2!=0) a+=1;
				if(b%2!=0) b+=1;
				if(a==b) return answer;//a,b가 같아지면 1차이나는거
				a/=2;
				b/=2;
				mid/=2;
				answer++;
			}
		}
		return answer;
	}
}

---

마치며

다른 사람들의 풀이를 보면 훨씬 간단한 풀이도 많다. 특히 mid값 기준으로 경우를 나누지않고 바로 a,b의 값을 재할당하여 반복문을 돌리는 풀이도 간단하게 돼있기 때문에 다른 풀이도 보는것을 추천한다.