[백준 3230/자바(java)] 금메달, 은메달, 동메달은 누가?

백준 3230 자바

금메달, 은메달, 동메달은 누가?

문제

2018년에 대한민국 평창에서 동계올림픽이 개최된다. 그 중에서도 스키는 동계올림픽의 꽃이지만 유독 우리나라에선 인기가 좀 없는 것 같다. 그래서 이번 평창올림픽에선 새로운 스키 경기 규칙이 적용 되었다. 새로 적용된 규칙은 다음과 같다.

스키 경기는 두 번의 경주로 이루어져 있다. 총 N명의 선수가 첫 번째 경주에 참가하고 각각 번호를 부여받는다. 1번 선수부터 N번 선수까지 순서대로 한 명씩 산을 타고 내려간다. 산을 다 내려오면 내려온 선수의 현재 순위가 정해질 것이다. 첫 번째 경주가 끝나고 난 뒤 최종적으로 정해진 순위에 따라서 1등부터 M등까지의 선수들에게만 두 번째 경주에 나갈 수 있는 자격이 주어진다. 

두 번째 경주에서는 첫 번째 경주에서 늦게 들어온 순서대로(M등부터 시작해서 1등까지) 한 명씩 산을 타고 내려간다. 산을 다 내려오면 내려온 선수의 현재 순위가 정해질 것이다. 두 번째 경주가 끝나고 난 뒤 최종적으로 정해진 순위에 따라서 1등, 2등 그리고 3등에게 각각 금메달, 은메달, 동메달이 수여 될 것이다.

이때 메달을 얻은 선수들의 번호를 구하는 프로그램을 작성해야 한다.(경주에 참가한 모든 선수들은 한 명도 빠짐없이 경주를 완주한다. 두 명 이상의 선수가 동시에 들어오는 경우는 없다.)

입력

첫 번째 줄에는 정수 N과 M이 주어진다. (3 ≤ M ≤ N ≤ 100)

이 후 N개의 줄에는 첫 번째 경주에서 각각의 선수들이 내려왔을 때 정해진 현재 순위가 주어진다.

이 후 M개의 줄에는 두 번째 경주에서 각각의 선수들이 내려왔을 때 정해진 현재 순위가 주어진다.

출력

첫 번째 줄에는 금메달을 딴 선수의 번호를, 두 번째 줄에는 은메달을 딴 선수의 번호를, 세 번째 줄에는 동메달을 딴 선수의 번호를 출력한다.

 

오늘 프로젝트를 하다가 머리를 식힐 겸 백준 실버 문제 중 가볍게 풀만한 문제가 없나 찾아보다가 제목이 끌려서 이 문제를 골랐다.

그런데 생각보다 가벼운 문제가 아니었다.

 

많은 시도를 하고 실패한 결과 문제를 풀었다.

실패 시도

1. hashMap을 이용하여 풀 수 있을까 생각해서 hashMap을 사용했다가 정렬하고 반환하는 과정에서 막혀서 실패
2. 첫 번째 경주에서는 순서대로, 두 번째 경주에서는 첫 번째 경주에서 낮은 순서대로에서 스택을 떠올려 스택을 시도하였으나 값과 순위 두 가지를 넣지 못하여 실패
3. 기초적인 방법으로 돌아가서 기본 배열을 사용하여 한참을 고민한 후에 겨우 성공

정답 코드

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()); // 입력으로 주어진 n 값
        int m = Integer.parseInt(st.nextToken()); // 입력으로 주어진 m 값

        int[] arr = new int[101]; // 순위를 저장하는 배열
        int[] ans = new int[101]; // 정렬된 결과를 저장하는 배열

        // 첫 번째 루프: 입력을 받고 순위를 정렬하는 부분
        for (int i = 1; i <= n; i++) {
            int rank = Integer.parseInt(br.readLine()); // 순위 입력 받기

            // 만약 순위가 이미 존재하고 첫 번째 입력이 아닌 경우, 뒤로 밀어서 순위를 조정
            if (arr[rank] != 0 && i != 1) {
                for (int j = i - 1; j >= rank; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[rank] = i;
            } else {
                arr[rank] = i; // 순위를 저장
            }
        }

        // 두 번째 루프: 정렬된 결과를 다시 순위에 맞게 저장
        for (int i = 1; i <= m; i++) {
            int rank = Integer.parseInt(br.readLine()); // 정렬할 순위 입력 받기
            int player = arr[m - i + 1]; // 해당 순위에 맞는 선수 찾기

            // 만약 순위가 이미 존재하고 첫 번째 입력이 아닌 경우, 뒤로 밀어서 순위를 조정
            if (ans[rank] != 0 && i != 1) {
                for (int j = i - 1; j >= rank; j--) {
                    ans[j + 1] = ans[j];
                }
                ans[rank] = player;
            } else {
                ans[rank] = player; // 순위에 맞게 선수 저장
            }
        }

        // 결과 출력: 상위 3명의 선수를 출력
        for (int i = 1; i <= 3; i++) {
            System.out.println(ans[i]);
        }
    }
}

 코드에 대한 설명은 주석을 통해 기재하였다.

알고리즘 설명

기본 구조

• 3<= M <= N <= 100 이므로, M과 N의 최대 범위를 포함할 수 있는 크기가 101(0을 포함)인 배열 arr, ans를 선언한다.
• 배열의 인덱스가 순위이고, 해당 인덱스에 할당된 값이 선수 번호이다.

첫 번째 경주

• 순위가 존재하지 않거나 첫 번째 입력인 경우 입력받은 순위를 인덱스로 하여 배열에 값을 할당한다.
• 그리고 해당 순위의 값이 이미 존재하고 첫 번째 선수가 아닌 경우, 기존의 순위를 한 칸씩 뒤로 밀어서 순위를 조정한다.
  이유: 입력받은 순위는 내려온 선수의 현재 순위이기에 예를 들어 첫 번째 선수는 처음으로 내려왔으므로 무조건 1등이고, 두 번째 선수의 순위가 1등이라면, 첫 번째 선수의 순위를 한 칸 뒤로 밀어서 2등으로 만들어야 한다.
• 위와 같은 방법을 반복문을 통하여 반복하여 첫 번째 경주를 마친 arr을 반환한다.

두 번째 경주

• 첫 번째 루프와 진행과정은 똑같지만 두 번째 경주에서는 첫 번째 경주에서 1등부터 m등까지 역순으로(m등부터 1등까지) 출발
• 따라서 선수 번호를 저장하는 player을 선언하고 첫 번째 경주에서 m등부터 1등까지 대입할 수 있게 arr[m - i + 1]을 할당한다.
• 첫 번째 경주와 마찬가지로 순위가 존재하지 않거나 첫 번째 입력인 경우 입력받은 순위를 인덱스로 하여 배열에 값을 할당한다.
• 해당 순위의 값이 이미 존재하고 첫 번째 선수가 아닌 경우, 기존의 순위를 한 칸씩 뒤로 밀어서 순위를 조정한다.

출력

• 금메달, 은메달, 동메달을 딴 선수의 번호를 출력해야 하기에 ans[1] ~ ans[3]까지 출력한다.

 

최근에 학습했었던 여러 자료구조 형태를 적용해야 할 것이라고 생각하고 접근해서 더 오래 걸린 문제였다.

또한, 이 정도 문제는 코딩테스트에 출제된다면 충분히 풀 수 있어야 하는 문제인데, 생각보다 많은 시간을 소모해서 아직 나의 알고리즘 실력이 많이 부족하다는 것을 느꼈다.

좀 더 분발해야겠다.