[백준/2876] 그래픽스 퀴즈 - Java 자바

https://www.acmicpc.net/problem/2876

문제 출처: COCI 2010/2011, Contest #1

 

문제

교실에는 N개의 책상이 일렬로 놓여있고, 한 책상에 학생 2명이 앉는다.

교수는 퀴즈를 채점할때 점수 등급마다 다른 색상의 연필로 채점한다. 

오늘 교수는 한 가지 색연필만 가져왔기 때문에 아래와 같은 방법으로 채점하려고 한다.

• 책상 2개를 선택하여 해당 범위 내 책상마다 한 명의 학생을 선택한다. 이때 양끝의 책상 또한 포함한다.
• 한 가지 색연필만 가져왔기 때문에 고른 학생들 모두 같은 점수를 가져야 한다.

교수가 한 가지 색만을 이용해 채점할 수 있는 최대 학생 수와 그때의 점수 등급을 출력한다.

만약 답이 여러 가지라면, 가장 작은 점수 등급을 출력한다.

 

입력의 첫 번째 줄에는 정수 N이 주어진다(1 ≤ N ≤ 100,000).
다음 N개의 줄에는 i번째 책상에 앉은 두 학생이 받아야 할 그레이드 Ai와 Bi(1 ≤ Ai, Bi ≤ 5)가 주어진다.

---

입출력 예시

입력	출력
3 3 5 4 5 1 3	2 5
4 2 1 3 2 5 3 2 5	2 2

---

풀이

모든 경우의 수를 탐색하기에는 N이 너무 크기 때문에 교수가 점수 등급 1을 줄때, 2를 줄때, .... 가정한다.

책상에 앉아있는 학생들을 순회하며 점수 등급과 같은 점수를 가진 학생이 연달아 몇명 있는지 확인한다.

해당 점수 등급을 가진 학생들이 최대로 연속으로 앉아있는 경우의 수를 출력한다.

import java.io.*;
import java.util.*;

public class Main {
    static int max = 100001;
    static int n, numOfStudents, grade;
    static int[] A = new int[max];
    static int[] B = new int[max];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            A[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

        for (int score = 1; score <= 5; score++) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (A[i] == score || B[i] == score) count++;
                else count = 0;
                if (numOfStudents < count) {
                    numOfStudents = count;
                    grade = score;   
                }
            }
        }

        System.out.println(numOfStudents + " " + grade);
    }
}