250x250
250x250
JinSeopKim
Hello World!
JinSeopKim
전체 방문자
오늘
어제
  • 분류 전체보기 (168)
    • Artificial intelligence (14)
      • DeepDiveToAI (3)
      • Pytorch (3)
      • Etc (8)
    • Back-end (19)
      • Spring (10)
      • JPA (9)
    • Language (24)
      • Python (3)
      • Java (11)
      • Swift (10)
    • Math (4)
      • Linear Algebra (4)
    • CodingTest (79)
      • Algolithm (12)
      • Backjoon (25)
      • Programmers (42)
    • Etc (27)
      • Book Review (3)
      • Adsp (6)
      • Life (2)
      • Docker (1)
      • odds and ends (15)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • GitHub

인기 글

태그

  • JPA
  • Python
  • 자바
  • SpringMVC
  • 브루트포스
  • 파이썬
  • 프로그래머스
  • 문제풀이
  • 개발자
  • data
  • 개발
  • certificate
  • 카카오
  • BFS
  • BOJ
  • Front-end
  • JAVA8
  • ADsP
  • java
  • 구현
  • 선형대수
  • AI
  • 알고리즘
  • uArm
  • swift
  • DP
  • 백준
  • 코딩테스트
  • 머신러닝
  • ios

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
JinSeopKim

Hello World!

[PGM_12985] 예상 대진표 (java)
CodingTest/Programmers

[PGM_12985] 예상 대진표 (java)

2022. 2. 28. 18:22
728x90
728x90

문제링크

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

 

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

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N

programmers.co.kr

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 수학

1. 문제 이해

토너먼트로 경기를 진행하게 된다. 이 때 토너먼트 게임은 1 vs 2, 3 vs 4, 5 vs 6 ... 로 진행되며 1 vs 2의 승자와 3 vs 4의 승자가 다음 토너먼트에서 경기를 진행하는 방식이다.

 

토너먼트를 진행하는 사람의 수 n과 두 명의 선수의 번호 a, b가 주어졌을 때 두 선수가 토너먼트 경기의 몇번째 경기에서 만날 수 있을지를 찾는 문제이다. (몇번째 경기란, 해당 선수가 몇번의 승리만에 상대를 만날 수 있는지를 의미한다.)

 

여기서 n으로 입력되는 값이 2의 n승이 온다는 조건때문에 토너먼트에서 부전승이 없게 된다.

 

2. 접근방법

토너먼트 경기를 정확히 절반씩 나누어 문제를 접근하였다. 결승전은 절반으로 나누어 생각해보면 왼쪽 토너먼트의 최종 우승자와 오른쪽 토너먼트의 최종 우승자의 경기라고 할 수 있다. 그리고 그 둘은 완전히 대칭의 모양을 보여줄 것이다. 그리고 왼쪽의 우승자는 절대로 오른쪽의 토너먼트의 사람들과 결승전이 되기 전까지는 겨루어볼 수 없다.

 

이러한 토너먼트의 결승전의 특징을 토너먼트의 모든 경기들로 일반화하여 생각해보겠다.

1. 토너먼트는 반으로 갈랐을 때 서로 대칭이다.

2. 어느 경기를 기준으로 왼쪽에서의 우승자와 오른쪽에서의 우승자가 겨루게 된다.

3. 왼쪽의 우승자는 오른쪽의 우승자와 겨루어 볼 수 없다.

 

3. 세부 해결방안

//둘 다 같은 위치에 포함 될 때
if(inPlayer(startNumber,finishNumber,playerA) && inPlayer(startNumber,finishNumber,playerB)) {
    int partition = startNumber + (finishNumber - startNumber + 1)/2;
    int left = recursiveSolve(startNumber,  partition-1 , playerA, playerB);
    int right = recursiveSolve(partition,finishNumber,playerA,playerB);
    return left == -1 ? right : left;
}

- 만약 두명이 같은 위치에 있다면 그 부분을 다시 반으로 갈라서 반복 확인한다.

//둘 다 포함되어있지 않을 때
else if(!inPlayer(startNumber,finishNumber,playerA) && !inPlayer(startNumber,finishNumber,playerB))
    return -1;

- 둘 다 없다면 그 부분은 더 이상 확인할 필요가 없으니 더 이상 확인하지 않는다.

//다른 토너먼트로 포함되어있을 때
int count = (finishNumber - startNumber + 1);
int result = 0;

//토너먼트 진행 횟수 계산
while (count != 0){
    count /=2;
    result++;
}
return result;

- 둘 중 하나만 있다면 그 지점까지 올라갈 때 치루어지는 경기의 수를 계산해준다.

구현코드

package pgm_12985;

public class Solution {
    public int solution(int n, int a, int b)
    {
        return recursiveSolve(1,n,a,b);
    }

    public int recursiveSolve(int startNumber, int finishNumber, int playerA, int playerB){
        //둘 다 같은 위치에 포함 될 때
        if(inPlayer(startNumber,finishNumber,playerA) && inPlayer(startNumber,finishNumber,playerB)) {
            int partition = startNumber + (finishNumber - startNumber + 1)/2;
            int left = recursiveSolve(startNumber,  partition-1 , playerA, playerB);
            int right = recursiveSolve(partition,finishNumber,playerA,playerB);
            return left == -1 ? right : left;
        }
        //둘 다 포함되어있지 않을 때
        else if(!inPlayer(startNumber,finishNumber,playerA) && !inPlayer(startNumber,finishNumber,playerB))
            return -1;
        else{
            //다른 토너먼트로 포함되어있을 때
            int count = (finishNumber - startNumber + 1);
            int result = 0;

            //토너먼트 진행 횟수 계산
            while (count != 0){
                count /=2;
                result++;
            }
            return result;
        }
    }

    //구역에 플레이어가 존재하는지 확인
    public boolean inPlayer(int startNumber, int finishNumber, int player){
        return player >= startNumber && player <= finishNumber;
    }
}
잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)

 

728x90
728x90
저작자표시 비영리 (새창열림)

'CodingTest > Programmers' 카테고리의 다른 글

[PGM_42890] 후보키 (java)  (0) 2022.03.03
[PGM_72412] 순위 검색 (java)  (0) 2022.03.02
[PGM_42577] 전화번호 목록 (java)  (0) 2022.02.27
[PGM_87946] 피로도 (java)  (0) 2022.02.26
[PGM_1844] 게임 맵 최단거리 (java)  (0) 2022.02.23
    'CodingTest/Programmers' 카테고리의 다른 글
    • [PGM_42890] 후보키 (java)
    • [PGM_72412] 순위 검색 (java)
    • [PGM_42577] 전화번호 목록 (java)
    • [PGM_87946] 피로도 (java)
    JinSeopKim
    JinSeopKim
    기록📚

    티스토리툴바