[백준(Baekjoon)] 1268 임시 반장 정하기

문제

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

그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 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 이하의 정수이다.

 

출력

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

 

예제 입력 1

5

2 3 1 7 3

4 1 9 6 8

5 5 2 4 4

6 5 2 6 7

8 4 2 2 2

 

예제 출력 1

4

 

---

나의 풀이

[Python(파이썬)]

 

풀이 1 -> 시간 초과 코드

s_num = int(input())
students, sameclass = [], []
for _ in range(s_num):
    students.append([*map(int, input().split())])
    sameclass.append([])

for i in range(s_num):
    for grade in range(5):
        for k in range(i+1, s_num):
            if k not in sameclass[i] and students[i][grade] == students[k][grade]:
                sameclass[i].append(k)
                sameclass[k].append(i)
    sameclass[i] = len(sameclass[i])

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

 

풀이 2 -> 풀이1 수정 후 정답

s_num = int(input())
students, sameclass = [], []
for _ in range(s_num):
    students.append([*map(int, input().split())])
    sameclass.append([])

for i in range(s_num):
    for k in range(i+1, s_num):
            for grade in range(5):
                if students[i][grade] == students[k][grade]:
                    sameclass[i].append(k)
                    sameclass[k].append(i)
                    break
    sameclass[i] = len(sameclass[i])

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

 

풀이 3 -> 다른 방식으로 구현

s_num = int(input())
students, sameclass = [], []
for _ in range(s_num):
    students.append([*map(int, input().split())])
    sameclass.append([])

for grade in range(5):
    classcheck, check = [[],[],[],[],[],[],[],[],[]], []
    for j in range(s_num):
        ban = students[j][grade] - 1   
        classcheck[ban].append(j) 
        if len(classcheck[ban]) == 2:  
            check.append(ban)
    for k in check:
        for l in classcheck[k]:
            sameclass[l] += classcheck[k]

for cnt in range(s_num):
    sameclass[cnt] = len(set(sameclass[cnt]))
print(sameclass.index(max(sameclass))+1)

 

---

풀이 과정

1. 풀이 1 -> 시간 초과 코드
2. 풀이 2 -> 풀이 1 수정 후 정답
3. 풀이 1과 2의 차이점
2. 풀이 3 -> 다른 방식으로 구현

 

1. 풀이 1 -> 시간 초과 코드

 

풀이 1 구현 방식은 학생을 기준으로 같은 반 된 학생이 있는지 체크해 나가는 방식이다. 

 

for i in range(s_num):	# 현재 기준이 되고 있는 학생
    for grade in range(5):	# 학년
        for k in range(i+1, s_num):	# 비교 대상 학생
            if k not in sameclass[i] and students[i][grade] == students[k][grade]:
                sameclass[i].append(k)
                sameclass[k].append(i)
    sameclass[i] = len(sameclass[i])

 

첫번째 for문 : i -> 현재 기준이 되고 있는 학생 번호 (인덱스는 0부터 시작, 0번 ~ s_num-1번 학생이라 생각)

두번째 for문 : grade -> 학년 (인덱스는 0부터 시작,   0학년 - 4학년까지라고 생각)

세번째 for문 : k -> 같은 반이었는지 확인 할 대상의 학생 번호 (학생 번호 인덱스는 0부터 시작, 0번 ~ s_num-1번 학생이라 생각)

 

 

 

2. 풀이 2 -> 풀이1 수정 후 정답

 

풀이 2 구현 방식도 풀이 1과 마찬가지로 학생을 기준으로 같은 반 된 학생이 있는지 체크해 나가는 방식이다. 

 

for i in range(s_num):
    for k in range(i+1, s_num):
            for grade in range(5):
                if students[i][grade] == students[k][grade]:
                    sameclass[i].append(k)
                    sameclass[k].append(i)
                    break
    sameclass[i] = len(sameclass[i])

 

첫번째 for문 : i -> 현재 기준이 되고 있는 학생 번호

두번째 for문 : k -> 같은 반이었는지 확인 할 대상의 학생 번호

세번째 for문 : grade -> 학년

 

 

 

3. 풀이 1과 2의 차이점

 

풀이 1과 2의 가장 큰 차이점은 두번째 for문과 세번째 for문의 순서를 바꿨다는 점이다. 

 

※ 두번째 for문과 세번째 for문을 바꾼이유!

 

풀이 1는 0번 학생이 다른 학생과 같은 반인지 검사를 할 때 1학년때 0 - 4번 학생과 같은반인지 검사하고 

2학년으로 넘어가서 0 - 4번과 비교하고 또 3학년 ... 이렇게 5학년까지 넘어간다. 

만약 0번이 1, 4학년때 같은 반이었던 친구 1번이 있다고 치자 그럼 1학년때 검사를 해서 같은반이어도 2 - 4학년때 1번 친구와 다시 같은 반이었는지 또 비교 해야한다. 

그리고 중복을 제거하기 위해(같은반이 된 적이있는지) sameclass[0]에 1번 학생이 있는지 검사도 계속 따로 해야한다. 

sameclass[i] => i번 학생이 같은 반 된 적 있는 학생의 번호를 저장 

 

if k not in sameclass[i]

 

 

그림처럼 0번 학생을 검사하고 있을 때 1번 학생과 1, 4학년때 같은 반인 경우

1학년 때 검사를 한 후 2학년때 if 1 not in sameclass[0]도 검사하고 3학년 때도  if 1 not in sameclass[0] 검사하게 된다. for문으로 자꾸 접근해야하는 것이다. 

 

 

하지만 풀이 2 처럼 두번째 for문과 세번째 for문을 바꾼다면

0번 학생이 1번 학생과 같은 반이 된 적있는지 1-5학년까지 검사를 다 한 후,  2번 학생과 같은 반이 된 적이 있는지 1-5학년까지 검사한다.  

0번 학생이 1번 학생과 2학년때 만났다면 3-5학년은 검사하지않고 통과한다. (break로 시간 단축)

그리고 통과했기 때문에 따로 sameclass[0]에 1번 학생이 있는지 검사할 필요가 없어진다. 

 

 

그러니까 풀이 1은 학년을 고정하고 비교 대상 학생을 다 검사하는 것이고, 풀이 2는 비교대상 학생을 고정하고 학년을 다 검사하는 것이다. 

따라서 풀이 2는 해당 학년에서 비교 대상 학생과 같은 반임을 알았다면 다음 학생으로 넘어가기 때문에 풀이1에 비해서 많은 시간이 단축 될 수 있다. 

 

 

 

 

4. 풀이 3 -> 다른 풀이 방식

 

처음 시간 초과가 나온 후 다른 방식으로 풀어 볼 순 없을까 하고 다시 처음부터 구현해보았다.

풀이1과 2는 학생을 기준으로 같은 반 된 학생이 있는지 체크해 나가는 방식었다면 풀이 3은 학년에서 반을 기준으로 학생들을 append하는 방식으로 구현했다. 

 

for grade in range(5):
    classcheck, check = [[],[],[],[],[],[],[],[],[]], []
    for j in range(s_num):
        ban = students[j][grade] - 1   
        classcheck[ban].append(j) 
        if len(classcheck[ban]) == 2:  
            check.append(ban)
    for k in check:
        for l in classcheck[k]:
            sameclass[l] += classcheck[k]

for cnt in range(s_num):
    sameclass[cnt] = len(set(sameclass[cnt]))
print(sameclass.index(max(sameclass))+1)

 

위의 코드를 예를 들어 그림으로 이해해보자 입력이 아래 그림과 같이 주어졌을 때

 

 

1) 1학년 때 학생들의 번호를 해당 반에 넣는다.  

2) 한 반에 두 명 이상 학생이 들어가면 check에 해당 반을 append한다. 

if len(classcheck[ban]) == 2:  
            check.append(ban)

3) 같은 반이 된 학생들을 만난 학생 리스트(sameclass)에 넣는다. 

    for k in check:
        for l in classcheck[k]:
            sameclass[l] += classcheck[k]

4) 2-5학년을 반복한다. 

 

5) sameclass에서 집합을 이용해 중복을 제거하고 가장 만난 사람이 많은 학생의 인덱스를 출력한다. 

(자기 자신을 만났다고 표시되어있지만 정답에 영향을 주지 않는다. )

for cnt in range(s_num):
    sameclass[cnt] = len(set(sameclass[cnt]))
print(sameclass.index(max(sameclass))+1)

---

문제 출처

1268번: 임시 반장 정하기