백준 1268 - 임시 반장 정하기

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

실버 5 / 구현

1. 문제

학생 수는 3~1000명

반은 1~9반

1학년부터 5학년까지 같은 반이었던 사람이 가장 많은 사람을 찾아야한다.

동점이라면 앞 번호를 출력한다.

2. 아이디어

1) 같은 반이었던 학생이 중복되면 안된다.

예를 들어, 1번과 2번 학생이 1~5학년 때까지 항상 같은 반이었다면 한 번만 카운트를 해야한다.

2) 반의 수가 1~9인데, 반이 몇 반까지 있냐는 문제 풀이에 중요하지 않다. 같은 반이었냐가 중요한 것.

3) 학생이 1번부터 차례대로 있는 걸보면, 인덱스로 활용할 수 있겠다.

3) 동점이 나오면 앞 번호를 출력해야하는데, 최솟값을 찾을 필요없다. index()를 쓰면 제일 앞 인덱스를 출력한다.

 

처음에 학생이 중복되면 안되고, 반이 몇반이냐가 중요한 게 아니라는 것을 간과해서 한참 헤맸다.

3. 코드

# 입력 받기
n = int(input()) # 학생 수
table = [] # 입력표

for _ in range(n):
    row = list(map(int, input().split()))
    table.append(row)

# 학생별로 같은 반이었던 학생 수를 저장할 리스트
equalClass = [0] * n

# 같은 반이었던 학생을 찾기 위한 2중 반복문
for i in range(n):
    for j in range(i + 1, n):
        # 1학년부터 5학년까지 각 학년을 검사
        for grade in range(5):
            if table[i][grade] == table[j][grade]:
                equalClass[i] += 1
                equalClass[j] += 1
                break

# 최대값을 가진 학생의 인덱스 찾기
max_count = max(equalClass)
leader = equalClass.index(max_count) + 1

print(leader)

 

j의 반복 범위를 i+1부터 반복하도록 해서 학생 중복 카운트를 방지한다.

1번과 2번을 비교하고 나면, 2번은 1번과 비교할 일이 없기때문에 중복이 발생하지 않는다.