[BaekJoon] 백준 1268 임시 반장 정하기 (Python / 파이썬)

BaekJoon 백준 1268 임시 반장 정하기 문제는 1학년부터 5학년까지 지내오면서 한 번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 구하는 문제다. 난이도는 Bronze 1이다.

 

BaekJoon 1268 임시 반장 정하기 문제 정보

출처

- https://www.acmicpc.net/problem/1268

알고리즘 분류

- 구현

난이도

- 브론즈 1 / Bronze 1

 

임시 반장 정하기 문제 요약

• 6학년 1반 학생 중에서 1학년부터 5학년까지 지내오면서 한 번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.
• 예를 들어, 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다.
• 그러므로 이 학급에서 4번 학생과 한 번이라도 같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다.
• 이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다.
• 각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 정하여 출력한다.
• 단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그중 가장 작은 번호만 출력한다.
• 학생 수는 3 이상 1000 이하이다. 주어지는 정수는 모두 1 이상 9 이하의 정수이다.

 

문제 풀이 과정

1. a번 학생과 b번 학생이 같은 반이 었던 적이 있나 체크하기 위해 행과 열의 인덱스를 학생의 번호로 여기는 학생수 X학생수의 크기의 이차원 리스트 same [][]을 정의하고 모든 원소를 0으로 초기화한다.
2. 학년 별로 n번 학생과 n+1번 학생의 반을 비교하여 같은 반이었던 적이 있으면 두 학생 번호의 행과 열 자리를 1로 표시한다.
3. 모든 학생들이 서로 비교할 때까지 반복한다.
4. 1의 횟수가 가장 많은 학생이 임시 반장이 되므로 해당 학생의 번호를 출력한다.

몇 학년 때 같은 반이었는지는 중요하지 않고, 한 학생과 여러 학년 동안 같은 반이었어도 1번으로 카운트해야 한다.

 

코드 및 설명

• ban [] - 학생별 1~5학년까지 속했던 반
• same [][] -  행 번 학생이 열 번 학생과 같은 반을 한 적 있는지 여부를 저장한 2차원 리스트 (1=같은 반이었음)
• cnt [] - 학생별 같은 반이었던 학생의 수

n = int(input())
ban = []  # 학생별 1~5학년까지 속했던 반
same = [0] * n  # 행 번 학생이 열 번 학생과 같은 반이었는지 여부
for i in range(n):
    ban.append(list(map(int, input().split())))
    same[i] = [0] * n

for i in range(5):  # i 학년
    for j in range(n):  # j번의 i 학년
        for k in range(j + 1, n):  # k번의 i 학년을 비교
            # j번과 k번이 i학년 때 같은 반이었으면
            if ban[j][i] == ban[k][i]:
                # same을 1로 바꾼다.
                same[k][j] = 1
                same[j][k] = 1
                # += 1을 하면 같은 반이였던 횟수가 same에 저장

cnt = []  # 학생별 같은 반이였던 학생 수
for s in same:
    cnt.append(s.count(1))

print(cnt.index(max(cnt)) + 1)

---

푸는데 꽤 오래 걸리고 까다로운 문제였다. 역시 정답 비율이 낮으면 다 그 이유가 있다.

 

BaekJoon 백준 1268 임시 반장 정하기 문제를 파이썬 python으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.