1. 문제

백준 1057번 토너먼트

2. 고민한 내용

오랜만에 다시 알고리즘 문제 풀이를 진행하니까 머리가 잘 안 돌아갔다..
문제 상황을 직접 그려보면서 뭔가 규칙이 있는 것 같은데.. 간단한 식으로 나올 것 같았지만 생각해내지 못했다.
그래서 직접 문제 상황을 하나씩 브루트포스로 따라가는 식으로 진행했다.
(하지만 다 풀고 나서 다른 분의 풀이를 찾아보니.. 내가 너무 비효율적인 방법으로 진행했다는 것을 깨달았다. 비효율적인 방법으로 풀었더라도 일단 이 고민 과정들을 남겨두고 다음에 더 효율적인 방법을 찾아보자는 차원에서 계속 적어보겠다.)

먼저 ArrayList를 이용해서 라운드마다 빠지는 참가 번호를 ArrayList에서 제거하려고 했다.
하지만 전체 list의 크기(실제로 값이 있는 부분리스트의 size/length)를 구하려면 arrayList.toArray.length()를 이용해야 해서 결국 시간초과가 떴다.
그래서 그냥 일반 int[] 리스트를 이용하고, 라운드마다 빠지는 참가 번호를 -1로 변경하였다.
그리고 라운드 카운트 변수를 +1 해주었다.
만약 지민이와 한수가 만날 일이 없는 경우에 대해서는 (근데 실제로 찾아보면 이런 경우가 나올 수 없다..) 라운드를 -1로 설정하였다.

// 이 코드는 효율적인 코드가 아닙니다! 그냥 제가 푼 과정을 적기 위해 남깁니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int j_first = Integer.parseInt(st.nextToken());
        int h_first = Integer.parseInt(st.nextToken());

        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = i + 1;
        }
        int j = j_first;
        int h = h_first;
        int round_cnt = 1;

        while (true) {
            if ((list.length / 2) % 2 == 0) { // 현재 라운드 참가자 수가 짝수인 경우
                for (int i = list.length / 2; i < list.length; i++) {
                    list[i] = -1;
                }
            } else { // 홀수인 경우
                for (int i = list.length / 2 + 1; i < list.length; i++) {
                    list[i] = -1;
                }
            }

            if ((h % 2 == 0 && j + 1 == h) || (j % 2 == 0 && h + 1 == j)) {
                break;
            }

            j = (j % 2 == 0) ? j / 2 : j / 2 + 1;
            h = (h % 2 == 0) ? h / 2 : h / 2 + 1;

            round_cnt++;

            if (list[1] == -1) {
                round_cnt = -1;
                break;
            }
        }

        System.out.println(round_cnt);
    }
}

3. 다른 풀이 공부

시간초과는 막아서 정답입니다! 가 떴지만 뭔가 시원하게 푼 게 아닌 것 같아서 다른 분의 풀이를 찾아보았다.
진짜 짧고 명료한 코드로 완성하신 분들이 많았다..

백준 1057번 토너먼트 java
이 글을 참고했다.

규칙을 찾으면 단순한 문제다.

위와 같은 원리로 규칙이 n / 2 + n % 2로 간단하게 다음 수를 정의할 수 있다.

그래서 이 원리에 대한 풀이는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int j = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int round_cnt = 0;

        while (j != h) {
            j = j / 2 + j % 2;
            h = h / 2 + h % 2;
            round_cnt++;
        }

        System.out.println(round_cnt);
    }
}

4. 느낀 점

오랜만에 풀어서 왠지 머리가 굳은 것 같다. 내가 빙 돌아가서 푼 것을 진짜 간단하게 풀 수 있다니 왜 이 규칙을 생각해내지 못했지 싶다.. 앞으로 코딩 문제들을 꾸준히 열심히 풀어가야겠다! 파이팅하자!