[백준] 그래픽스 퀴즈 - 2876

1. 문제

 

 

2. 접근

입력값이 최대 10만이고 그래이드는 5개이므로 O(5n)으로 풀면 되지 않을까 생각했다.

처음 접근은 이전의 그레이드와 현재 그레이드를 비교해서 연속하면 누적 카운트를 더해주고, 연속이 끊기면 누적 카운트를 맥스값과 비교해서 갱신한 후 누적값을 초기화 시키는 것이었다.

 

하지만 틀렸다!

 

더 좋은 방법은 2차원 배열로  student[6][N]를 만들어서 진행하는 것이다. 처음 student 배열을 0으로 모두 초기화한 후, 차례대로 N번 루프를 돈다. 이때 n은 책상의 수로 입력으로 주어지는 n책상에 대한 그레이드 정보를 이용한다.

 

grage1, grade2를 알아낸 후 이전의 값에 1을 더한다. 누적값을 알아야 하므로 이렇게 하면 변수 하나로 누적값을 관리할 수 있다. 그리고 연결이 끊겼을 경우에 student 배열을 모두 0으로 초기화했으므로 별다른 로직이 없어도 잘 작동된다.

for(int i=0; i<N; i++){
    String [] nums = br.readLine().split(" ");
    int grade1 = Integer.parseInt(nums[0]);
    int grade2 = Integer.parseInt(nums[1]);

    grade[grade1][i] = grade[grade1][i-1] + 1;
    grade[grade2][i] = grade[grade2][i-1] + 1;
}

 

 

 

전체코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {


    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int grade [][] = new int [6][N];


        for(int i=0; i<N; i++){
            String [] nums = br.readLine().split(" ");
            int grade1 = Integer.parseInt(nums[0]);
            int grade2 = Integer.parseInt(nums[1]);

            if(i == 0){
                grade[grade1][i] = 1;
                grade[grade2][i] = 1;
                continue;
            }
            grade[grade1][i] = grade[grade1][i-1] + 1;
            grade[grade2][i] = grade[grade2][i-1] + 1;
        }


        int maxCount = 0;
        int maxGrage = 1;
        // max 구하기
        for(int i=0; i<N; i++){
            for(int g = 1; g <=5; g++){
                if(grade[g][i] > maxCount){
                    maxCount = grade[g][i];
                    maxGrage = g;
                }
            }
        }


        System.out.println(maxCount +" " + maxGrage);

    }






}