[Java] 프로그래머스(level-2) - 예상 대진표
입출력 예시
Input
N=8, A=4, B=7
Output
3
문제 풀이
이 문제는 토너먼트에서 경쟁자인 a와 b가 몇번째 라운드에서 만나는지 구해야 한다.
2명씩 대전해가며 특정 라운드에서 서로 만나려면 a가 b보다 1크거나, 1작아야 한다.
어떤 상황에서 a가 b보다 1이 작거나, 1이 클수가 있을까?
- a가 짝수라면 a-1의 수가 b이어야 한다.
- a가 홀수라면 a+1의 수가 b이어야 한다.
a가 짝수라면, a의 이전 자리에 b가 와야 하고, a가 홀수라면, a의 다음자리에 b가 와야 서로 대전이 매칭될 수 있다.
그렇다면 a와 b를 인접한 수가 될 때까지 변경해야 한다. 그런데 a와 b값을 어떻게 변경할까?
예를 들어 예시처럼 a가 4, b는 7이라 하자. a와 b를 인접한 수로 만들기 위해서 간단하게 생각하면 2로 나누면 된다.
그런데, 2로 나눠 떨어지지 않는 수의 경우는 반올림을 해야하니 1을 더해준다.
1
2
3
a=4,b=7 -> 1라운드
(a/2)=2, (b/2)+1=4 -> 2라운드(인접한 수가 아니기에 다음 라운드 진행)
(a/2)=1, (b/2)+1=2 -> 3라운드
이와 같이 라운드를 진행하면서 라운드마다 a와 b가 인접한 수가 됐는지 검증하고 인접한 수가 아니라면, 다음 라운드에서 다시 확인하는 식으로 진행하면 된다.
바로 코드를 작성해보자.
1
2
3
4
5
6
7
8
9
10
11
12
int answer = 1;
while(true) {
if((a%2)==0 && (a-1)==b) {
break;
}else if((a%2)==1 && (a+1)==b) {
break;
}
a = half(a);
b = half(b);
answer++;
}
1라운드부터 시작해서 while 반복문을 순회햐며 a가 짝수이면서 이전 수가 b일 경우, a가 홀수이면서 다음 수가 b일 경우가 될 때까지 a와 b값을 바꿔준다.
1
2
3
4
public static int half(int num) {
if(num%2 == 0) return num/2;
else return (num/2)+1;
}
그리고 half() 함수를 통해 a나 b의 값을 받아서 짝수면 2로 나눈 몫을, 홀수면 2로 나눈 몫에 1을 더하면 반환한다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
long start = System.currentTimeMillis();
solution(n,a,b);
long end = System.currentTimeMillis();
System.out.println("\n수행시간 = " + (end-start));
}
public static int solution(int n, int a, int b) {
int answer = 1;
while(true) {
if((a%2)==0 && (a-1)==b) {
break;
}else if((a%2)==1 && (a+1)==b) {
break;
}
a = half(a);
b = half(b);
answer++;
}
return answer;
}
public static int half(int num) {
if(num%2 == 0) return num/2;
else return (num/2)+1;
}
}
회고
- a와 b를 인접한 수로 만들기 위해 짝수, 홀수일 경우를 구분지어 2로 나누는 등의 연산식을 생각해내는게 힘들었다.