문제
접근 방식
한 책상마다 2 학생이 존재합니다.
그리고 책상의 개수를 입력으로 받고 있습니다.
학생 2명중 한명을 선택하고 책상 전체를 확인해야 하므로 시간 복잡도는 2^N입니다.
N이 최대 100,000이므로 완전탐색은 불가능합니다.
다만, 문제에서 검사할 성적 등급이 1 ~ 5이므로 연속된 등급들이 최대 몇개 인지만 확인하면 됩니다.
이렇게하면 시간 복잡도는 O(N)입니다.
만약 연속된 학생수가 동일한 경우, 먼저 찾은 등급을 출력하는 것으로 보아 등급별로 학생수가 동일하다면 먼저 등장한 등급을 답으로 설정하는 것으로 유추할 수 있습니다.
코드
typedef struct _ {
int stu1;
int stu2;
} table;
bool contains(const table& table1, int num) {
return table1.stu1 == num || table1.stu2 == num;
}
vector<table> tables;
int maxCnt = 0;
int resGrade = -1;
void sol() {
for (int grade = 1; grade <= 5; ++grade) {
int cnt = 0;
int temp = 0;
for (auto table : tables) {
if (contains(table, grade)) {
temp++;
} else {
cnt = max(temp, cnt);
temp = 0;
}
}
if (cnt > maxCnt) {
maxCnt = cnt;
resGrade = grade;
}
}
}
int main() {
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
int grade1, grade2;
cin >> grade1 >> grade2;
tables.emplace_back(table{grade1, grade2});
}
sol();
cout << maxCnt << ' ' << resGrade;
}