[프로그래머스 2017팁스타운]예상 대진표 -Java

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

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

class Solution {
		public int solution(int n, int a, int b) {
			int answer = 0;
			int people=n;
			int range=0; 
			int group=1; 
			
			while(true) {
				answer++;
				group=people/2; //총 몇 그룹 나오는지
				range=n/group; //1부터 몇번까지 1번그룹인지 
				
				if(((a-1)/range)==((b-1)/range)) break;
				
				people/=2; //사람수 절반 씩 줄어든다 
			}
			return answer;
		}
	}

소요시간 : 30분 

 

제한사항의 숫자가 커서 어떻게 시간초과가 안나게 빠르게 풀 지 고민하는데 시간이 조금 걸렸습니다!

 

우선 로직을 살펴보겠습니다

 

1 2 3 4 5 6 7 8   번 까지 사람이 있을 때 A=4, B=7 일 때를 구해보겠습니다

 

1. 처음에는 사람이 8명입니다 8명을 토너먼트 대전으로 그룹을 나누면 총 8/2 = 4그룹이 나옵니다. 

   번호가 1~8번까지 있기 때문에 8/4=2 즉, 1~2번(1조), 3~4(2조), 5~6(3조), 7~8(4조) 이런식으로 나옵니다.

 

2. 사람이 절반 줄어서 4명이 남았습니다. 4명은 4/2 = 2그룹이 나옵니다.

   마찬가지로 번호는 1~8번까지 있기 때문에 8/2 =4 즉  1~4번(1조), 5~8번(2조) 

 

3. 사람이 더 줄어서 2명이 남았습니다. 2명은 2/2 = 1그룹이 나옵니다.

   역시 번호는 1~8번까지 있기 때문에 8/1 =8 즉, 1~8번(1조) 이렇게 나옵니다.

 

규칙은 

1. 현재 남은사람 / 2 해서 총 그룹의 수를 구해줍니다.

2. N번/ 그룹의 수 를 해서 각각 번호가 어디에 속할 수 있는지를 구해줍니다.

3. 이를 토대로 A,B가 어디 그룹에 속하는지 확인하고 이 둘의 그룹이 같다면 끝!