[Python] 백준/BOJ 3077번: 임진왜란 (Silver 3)

💻 Problem

문제 보러 가기

 

선생님이 다시 사용한 채점 방법은 두 해전을 골라 순서가 일치하면 점수를 주는 방법이다. 즉, 선생님은 학생의 답 중에 N(N-1)/2개의 쌍을 모두 고른 뒤, 올바른 순서로 적혀 있으면 1점을 주려고 한다. 최종 점수는 획득점수/(N(N-1)/2)가 된다.

문제의 정답과 현우가 작성한 답안이 주어졌을 때, 현우의 점수를 구하는 프로그램을 작성하시오.

 

💡 Approach

처음엔 시간을 제대로 보지 않고 그냥 브루트포스로 풀면 되지 않을까 싶었다.

import sys
input = sys.stdin.readline

def grade():
    global score
    
    # 학생의 답 중에 2개를 고른다
    for i in range(n):
        for j in range(i + 1, n):
            # 2개의 순서가 올바르면 1점을 준다
            if correct.index(answers[i]) < correct.index(answers[j]):
                score += 1

n = int(input()) # 해전의 개수
correct = list(input().split()) # 올바른 정답
answers = list(input().split()) # 학생이 작성한 답안
score = 0

# 채점 후 점수 출력
grade()
print(f'{score}/{n * (n - 1) // 2}')

 

보이는 대로 코드를 작성했더니 시간 초과가 떴다.

살펴보니 시간복잡도가 약 n^3인데, 주어진 문제에서 n의 최댓값이 2500이니 10억을 초과하게 된다.

• (1) 바깥쪽 루프: i 반복문 <- n번 반복
• (2) 안쪽 루프: j 반복문 <- (n-i-1)번 반복
• (3) index() 호출: correct.index() 두 번 호출 <- 2n
• 즉, n * (n-i-1) * 2n => 약 n^3

 

그래서 3중 반복이 되는 것을 막기 위해 학생의 답 중 2개를 고르는 2중 반복문 내에서 if 문으로 비교하는 부분을 수정해야겠다 싶었다.

해당 부분에서 접근만 해서 비교하도록 하자.

채점하기 전에 correct, answers를 사전에 처리하면 해당 부분에서 접근만으로 비교할 수 있을 것이다.

 

✏️ Solution 1

import sys
input = sys.stdin.readline

def grade():
    global score
    
    # 학생의 답 중에 2개를 고른다
    for i in range(n):
        for j in range(i + 1, n):
            # 2개의 순서가 올바르면 1점을 준다
            if answers[i] < answers[j]:
                score += 1

n = int(input()) # 해전의 개수
correct = list(input().split()) # 올바른 정답
answers = list(input().split()) # 학생이 작성한 답안
score = 0

# 학생이 작성한 답안을 정답 순서로 초기화
for i in range(n):
    answers[i] = correct.index(answers[i])

# 채점 후 점수 출력
grade()
print(f'{score}/{n * (n - 1) // 2}')

 

answers를 사전에 초기화하는 방법이다.

학생이 작성한 답안을 하나씩 확인하면서 해당 답안이 정답에서 몇 번째인지로 초기화해 준다.

이렇게 하면 채점할 때 답안 두 개를 바로 비교할 수 있다.

 

✏️ Solution 2

import sys
input = sys.stdin.readline

def grade():
    global score
    
    # 학생의 답 중에 2개를 고른다
    for i in range(n):
        for j in range(i + 1, n):
            # 2개의 순서가 올바르면 1점을 준다
            if correct.get(answers[i]) < correct.get(answers[j]):
                score += 1
                                                       
n = int(input()) # 해전의 개수
correct = dict(zip(input().split(), [i for i in range(n)])) # 올바른 정답
answers = list(input().split()) # 학생이 작성한 답안
score = 0

# 채점 후 점수 출력
grade()
print(f'{score}/{n * (n - 1) // 2}')

 

correct를 딕셔너리를 통해 입력받는 방법이다.

파이썬의 zip()을 활용하면 입력값과 index를 함께 저장할 수 있다.

참고로 딕셔너리 접근할 때 인덱스로 접근해도 상관없지만 get()으로 접근하면 key가 딕셔너리에 존재하지 않을 때 None(또는 지정된 기본값)을 반환한다.