Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- heap정렬
- 카카오코딩테스트
- 백준 1000번 java
- java
- 백준 1924번 java
- 자바
- 카카오1차
- 코테준비
- 카카오코테
- 자바문자열
- 공부정리
- 힙정렬자바
- 자료구조힙
- 백준 1924번
- 코딩테스트기출
- 카카오기출
- java method
- 프로그래머스
- 자료구조 트리
- 객체프로그래밍이란
- 백준
- 개발상식
- 프렌즈4블록java
- heap
- 백준 1000번
- 프렌즈4블록
- 알고리즘
- 객체프로그래밍
- Java heap
- 문자열포맷
Archives
- Today
- Total
일단 시작해보는 블로그
[알고리즘_풀이] 프로그래머스 - 예상 대진표 java 본문
문제
https://programmers.co.kr/learn/courses/30/lessons/12985?language=java
코딩테스트 연습 - 예상 대진표 | 프로그래머스
△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라
programmers.co.kr
생각
홀수인 사람은 항상 자신+1인 짝수와 대결을 하고
짝수인 사람은 항상 자신-1인 홀수와 대결을 한다.
또, 이긴다면 다음 라운드는 (속해 있는 팀의 짝수인 사람/2)번째로 참가하게 될 것이다.
따라서 무조건 짝수로 만들어 준 다음에 2로 나누고 둘이 겹치지 않을 때까지 반복(재귀 or loop)한다.
풀이
재귀
class Solution
{
static int answer = 0;
public static void recursion(int n, int a, int b) {
if(a == b) return;
if(a%2 == 1) {
a += 1;
}
if(b%2 == 1) {
b += 1;
}
answer += 1;
recursion(n, a/2, b/2);
}
public int solution(int n, int a, int b){
recursion(n, a, b);
return answer;
}
}
loop (반복문)
class Solution
{
public int solution(int n, int a, int b){
int answer = 0;
while(a != b) {
a = a%2 == 1 ? (a+1)/2 : a/2;
b = b%2 == 1 ? (b+1)/2 : b/2;
answer+=1;
}
return answer;
}
}
Comments