BOJ_1057 : 토너먼트

👉 문제링크

1057번: 토너먼트

---

---

🔸 문제 분석 🔸

• n명의 참가자 중에 두 사람의 번호를 입력받는다.
  • 2명씩 경기를 진행하며 이기면 올라간다.
  • n이 홀수여서 혼자 남는 마지막 선수는 부전승으로 올라간다.
  • 참가자 수 n이 1이 될때까지 반복한다.
• 두 사람은 무조건 승리한다.
• 두 사람이 만나는 라운드 수를 출력한다.
  • 만나지 못하는 경우는 -1을 출력하지만, 그런 경우는 없다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int round = 0;

        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i == a || i == b)
                arr.add(1);
            else
                arr.add(0);
        }

        while (n > 1) {
            round++;
            boolean flag = false;
            ArrayList<Integer> temp = new ArrayList<>();

            for (int i = 0; i < n/2; i++) {
                if (arr.get(i*2) == 1 && arr.get(i*2+1) == 1) {
                    flag = true;
                    break;
                }
                else if (arr.get(i*2) == 1 || arr.get(i*2+1) == 1)
                    temp.add(1);
                else
                    temp.add(0);
            }
            if (flag)
                break;

            if (n % 2 != 0) {
                temp.add(arr.get(n-1));
                n /= 2;
                n++;
            }
            else
                n /= 2;

            arr = temp;
        }
        System.out.println(round);
    }
}

🔸 코드 해석 🔸

• ArrayList에 두 사람의 번호 인덱스는 1을 저장하고, 나머지는 0을 저장한다.
  • n이 1이 될 때까지 반복하지만 n은 최소 2가 된다.
• 임시 ArrayList인 temp에 다음 참가자 목록을 n/2개 저장한다.
  • 두 인덱스가 모두 1이면 반복을 종료하고 round를 출력한다.
  • 한 인덱스라도 1이면 temp 에 1을 저장한다.
  • 두 인덱스가 모두 0이면 temp에 0을 저장한다.
• 현재 참가자수 n이 홀수였다면 마지막 부전승 참가자를 temp에 저장한다.
  • 홀수 짝수를 생각해 다음 참가자 수 n을 변경한다.
• arr를 temp로 변경한다.

---

🔸 end 🔸

• 처음엔 ArrayList의 remove를 사용해 복사가 필요 없을것으로 생각했지만, 인덱스가 바뀌는게 추적이 복잡해질 것 같아 arr = temp; 형식으로 풀이했다.
  • 다행히 시간초과가 나지 않았다.
  • n이 10만으로 비교적 여유로운 범위어서 가능했던 것 같다.