문제

오늘은 기초컴퓨터그래픽스의 퀴즈가 있는 날이다. 기다란 교실 안에는 N개의 책상이 한 줄로 늘어서 있는데, 각 책상당 두 명의 학생이 앉도록 되어있다.

모든 학생들은 그래픽스를 열심히 공부했지만, 말도 안되는 난이도에 질려 포기하고 말았다. 한편 교수님은 각 학생들의 얼굴만 보고도 이 학생이 받아야 할 그레이드를 정확히 알아낼 수 있다.

교수님은 그래픽스 과목을 가르치는 만큼 자신의 미적 감각을 살리기 위해 각 그레이드를 다른 색을 이용해서 표시한다(예를 들어 A를 빨강으로 칠하면, B,C,D는 빨강으로 표시하지 않는다).

또, 퀴즈의 방식은 교수님이 수업이 시작할 때 어떤 두 책상을 선택하고, 두 책상과 그 사이에 있는 모든 책상에서 각각 한 명씩 지목해서 질문을 하고, 학생의 대답을 듣는 것이다.

오늘 교수님은 바쁜 나머지 한 가지 색의 색연필만 가지고 왔고, 결국 자신의 미학을 지키기 위해 퀴즈에서 지목한 모두에게 같은 그레이드를 주려고 한다. 교수님이 채점할 수 있는 학생의 수는 최대 몇 명일까?

입력

입력의 첫 번째 줄에는 정수 N이 주어진다(1 ≤ N ≤ 100,000).

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

출력

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

만약 답이 여러 가지라면, 가장 작은 그레이드를 출력한다.

예제 입력 1

1
1 5

예제 출력 1

1 1

예제 입력 2

예제 출력 2

2 5

예제 입력 3

예제 출력 3

2 2

Solution

[문제 이해]

처음보는 유형의 문제로 검색을 통해 누적 합(Prefix Sum) 알고리즘으로 풀이를 진행했습니다.

입력값 2개 중에 1개 임의로 선택하여 누적 합을 계산
→ 받을 등급이 같은 학생 수를 누적 합으로 계산
누적 합의 수가 동일하면, 등급이 낮은게 우선

이해한 내용을 바탕으로 코드를 작성했습니다.

[코드]

from collections import defaultdict
import sys
input = sys.stdin.readline

def solution():
    n = int(input())
    grades = defaultdict(dict)
    for i in range(n+1):
        for j in range(6):
            grades[i][j] = 0
    max_num = 0
    max_grade = 0

    # dictionary 구조로 누적합 사용
    def prefix_sum(i, num):
        nonlocal max_num, max_grade, grades
        grades[i][num] = grades[i-1][num] + 1
        if grades[i][num] > max_num:
            max_num = grades[i][num]
            max_grade = num
        elif grades[i][num] == max_num and max_grade > num:
            max_grade = num

    for i in range(1, n+1):
        a, b = map(int, input().split())
        prefix_sum(i, a)
        if a != b:
            prefix_sum(i, b)

    print(max_num, max_grade)

solution()

아래의 코드는 다른 사람의 풀이로, 리스트 자료구조를 사용하여 처리 효율을 높힌 케이스입니다.

[처리 효율이 좋은 코드]

# 처리 효율 좋아서 추가
import sys

n = int(sys.stdin.readline())
res = dict().fromkeys([i for i in range(1, 6)])
for i in res:
    res[i] = []
arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))
for k in range(1, 6):
    size = 0
    for i in range(n):
        if arr[i][0] == k or arr[i][1] == k:
            size += 1
        else:
            res[k].append(size)
            size = 0
    if size > 0:
        res[k].append(size)

ans = []
for i in res:
    ans.append((i, max(res[i])))
ans.sort(key=lambda x : (-x[1], x[0]))
print(ans[0][1], ans[0][0])

[과정]

누적 합 알고리즘을 먼저 이해하기 위해서 예제를 작성해봤습니다.

그리고 2개의 입력중 임의의 값이라는 처리를 위해서 dictionary 구조를 사용하여 누적 합 알고리즘을 작성했습니다.