[백준 1268번 알고리즘] 임시 반장 정하기 파이썬 풀이 및 반례

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

 

 

 

 

우선 반례 제공드리겠습니다.

6
1 2 3 4 4
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
9 8 7 6 5
9 8 7 6 5

위의 반례의 정답은 1입니다. 겹치는 학생 수 가 많아야해요..! 

 

두번째 반례입니다.

11
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
6 7 8 8 8
9 9 9 9 9
10 10 10 10 10
6 11 11 11 11

 

위의 반례의 정답은 8입니다.

 

 

5
1 1 1 1 1
1 1 1 1 1
1 3 4 5 5
3 3 3 3 3
4 4 4 4 4

위의 반례의 정답은 3입니다.

3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3

위의 반례의 정답은 1입니다.

이 부분이 좀 짜증났을텐데요 아무도 겹치지 않으면 1이 나와야해요

가장 작은 수 가 임시반장을 해야한다고 쓰여져 있기 때문입니다.

 

 

# 학생 수 입력
n = int(input().strip())

# 각 학생의 반 정보를 저장할 리스트 초기화
ban = []

# 학생들의 반 정보 입력
for _ in range(n):
    stu = list(map(int, input().strip().split()))
    ban.append(stu)

# 각 학생에 대해 다른 학생들과 같은 반을 한 횟수를 계산
max_shared_classes = 0
president = 0

for i in range(n):
    shared_classes_count = 0
    for j in range(n):
        if i != j:
            for k in range(5):
                if ban[i][k] == ban[j][k]:
                    shared_classes_count += 1
                    break #한 학생이랑 여러번 겹쳤을때 수가 추가되는것을 막기 위해 break함
    # 최대 같은 반 학생 수와 임시 반장 번호 갱신
    if shared_classes_count > max_shared_classes:
        max_shared_classes = shared_classes_count
        president = i + 1 
        

# 임시 반장 번호 출력
if president == 0:
    print(1)
else:
    print(president)

정답 코드입니다.

 

    if shared_classes_count > max_shared_classes:
        max_shared_classes = shared_classes_count
        president = i + 1

이 부분에서 >=이 아닌 > 만 사용해서 클 때만 업데이트를 해줍니다.

우리가 처음부터 업데이트를 해주고 있기 때문에 동일한 경우에는 작은 수를 출력하기 위함입니다.