[백준] # 1268. 임시 반장 정하기 (파이썬)

 

문제 링크

 

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

1268번: 임시 반장 정하기

 

문제 내용

 

오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기 반 학생 중에서 1학년부터 5학년까지 지내오면서 한 번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.

그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자.

 1학년2학년3학년4학년5학년

	1학년	2학년	3학년	4학년	5학년
1번 학생	2	3	1	7	3
2번 학생	4	1	9	6	8
3번 학생	5	5	2	4	4
4번 학생	6	5	2	6	7
5번 학생	8	4	2	2	2

위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한 번이라도 같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다. 이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다.

각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 정하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다. 둘째 줄부터는 1번 학생부터 차례대로 각 줄마다 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 5개의 정수가 빈칸 하나를 사이에 두고 주어진다. 주어지는 정수는 모두 1 이상 9 이하의 정수이다.

출력

첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다. 단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그중 가장 작은 번호만 출력한다.

 

IDEA

2차원 배열을 사용해서 학생마다 같은 반을 해왔던 학생을 담고, 그 수가 가장 많은 학생의 번호를 출력한다.

 

 

CODE

 

n = int(input())
same_class = [[] for _ in range(n+1)]    # index : 학생번호, element : 같은 반을 해봤던 학생들 번호
matrix = [[0,0,0,0,0]]
for _ in range(n):
    matrix.append(list(map(int,input().split())))
for i in range(1,n+1):
    for k in range(i+1,n+1):
        for j in range(0,5):
            # 반이 같다면 같은 반 학생이었던 학생의 번호를 same_class에 저장
            if matrix[i][j] == matrix[k][j]:
                if k not in same_class[i]: 
                    same_class[i].append(k)
                if i not in same_class[k]:
                    same_class[k].append(i)
# for i, friends in enumerate(same_class):
#     print(f'{i}번 학생과 같은 반이였던 친구들: ', friends)

# 임시 반장 정하기    
most_friendliest = 1 # 아무도 같은 반이었던 적이 없는 경우를 대비해 1로 초기화
friends = 0
for i in range(1,n+1):
    if len(same_class[i]) > friends:
        most_friendliest = i
        friends = len(same_class[i])
print(most_friendliest)

 

사용 알고리즘

 

구현 문제

 

풀이 평

 

구현은 오래 안 걸렸는데 아무도 같은 반이었던 적이 없는 경우에 대해 생각을 하지 못해 오류를 해결하느라 1시간 정도 걸렸다..