BOJ_1268_임시 반장 정하기

안녕하세요 이번에는 임시 반장 정하기 acm 대회 문제를 풀어보도록 하겠습니다.

문제에 중요한 개념이 들어가기 때문에 같이 정리하면서 알아보겠습니다.

문제는 다음과 같으며 이 문제를 풀기 위해서는 먼저 어떻게 문제를 접근해야 할 지 생각해야 합니다.

문제에서 묻는 것을 문장으로 풀어서 작성해보겠습니다.

 1번 학생이 1학년때부터 5학년때까지 같은 반으로 지낸 학생이 몇 명이 있는가?

 2번 학생이 1학년때부터 5학년때까지 같은 반으로 지낸 학생이 몇 명이 있는가? 

.

.

.

.

 n번 학생이 1학년때부터 5학년때까지 같은 반으로 지낸 학생이 몇 명이 있는가? 

---

여기서 중요한 것은 1번 학생이 만약 2학년때 2번 학생과 같은 반이 되었다고 가정한다면, 

2학년을 제외한 다른 학년에서 두 학생이 같은 반이 되었다고 하더라도 같은 반 학생으로 지냈다는 것을 

카운팅해서는 안된다는 것입니다.

중복되는 부분이므로 반드시 중복을 허용하지 않고 카운팅된 값을 뽑아내야 한다는 것입니다.

앞서 정의한 문장을 코드 그대로 구현하면 아래와 같습니다.

int studentMax = 0;  // 학생수가 가장 많을 때를 뽑아야 하므로 임의로 변수를 둔 뒤 체크한다.

int answer = 0;

for(int i=0;i<(학생수);i++){ // 1번 ~ n번 학생이 

set<int> studentSet

for(int j=0;j<5;j++){  // 1학년 ~ 5학년때까지

     for(int k=0;k<(학생수);k++){ // 같은 반이였던 다른 학생들을 모두 체크한다. 

if(i==k){

continue; // 자기 자신을 체크할 경우 --> 다시 반복문 조건으로 돌아가서 루프를 돌 수 있도록 

}

if(student[i][j] == student[k][j]){

// 1~n번까지의 학생이 1학년~5학년때까지 1~n번까지의 학생들을 체크한다 (같은 반이였는지)

// 1번 학생이랑 (1학년~5학년) 같은 반이였던 2~n번까지의 학생들을 Set에 넣기 

// --> Set을 사용하는 이유는 같은 반이 된 적이 있더라도 다른 학년에서 또 같은 반이 될 경우 

// 중복되는 것을 막기 위함

studentSet.insert(k); // 순서와 상관없이 중복을 제외하고 입력된다.

}

}

}

// studentSet에 추가되는 사이즈는 1~n번 학생과 같은 반인 적이 있는 학생들의 인원수와 같습니다.

if(studentMax < studentSet.size()){

studentMax = studentSet.size();

answer = i; 

} 

// 그 중 가장 큰 사이즈를 가진 사람 , 즉, 같은 반인 적이 많았던 학생들의 수일때 

// 그 때의 i (학생 (1~n번)) 를 반환하는 것이다.

}

---

SET은 Key만 있는 map 혹은 정렬된 집합으로 map과 구조가 유사한 특징을 가지고 있습니다.

key만 있고 value가 없는 map이라고 생각하면 더 편합니다.

가장 큰 특징은 중복을 허락하지 않고 순서와 관계없이 정렬된다는 것입니다. 

<set>을 include해야하며 insert를 통해서 값을 대입합니다. 

---

[전체코드]

#include <iostream>

#include <stdio.h>

#include <cstdio>

#include <set>

using namespace std;

int main()

{

int num;

cin >> num;

int arr[1002][5];

int ans = 0;

int mmax = 0;

for (int i = 0;i < num;i++) {

for (int j = 0;j < 5;j++) {

cin >> arr[i][j];

}

}

for (int i = 0;i < num;i++) {

set<int> classmates;

for (int j = 0;j < 5;j++) {

for (int k = 0;k < num;k++) {

if (i == k)

continue;

if (arr[i][j] == arr[k][j]) {

classmates.insert(k);

}

}

}

if (mmax < classmates.size()) {

mmax = classmates.size();

ans = i;

}

}

cout << ans + 1 << endl;

}

---

감사합니다1