[백준] 28286. 재채점을 기다리는 중 (Python)

백준 문제 풀이 - 구현

📰 문제

---

문제 확인 🏃

💡 입출력 예제

---

5 0
1 2 3 4 5
1 2 4 5 1

>> 2

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

>> 4

💬 풀이

---

🎵 첫번째 풀이

N, K = map(int, input().split())            # 문제 수 N, 밀고 당길 수 있는 최대 횟수 K
C = list(map(int, input().split()))         # 각 문제의 정답을 나타내는 정수
P = list(map(int, input().split()))         # 민규가 OMR 카드에 기입한 답안

answer = 0

def pull(idx, array):     # 당기기
    temp = array[:idx] + array[idx+1:] + [0]
    return temp

def push(idx, array):     # 밀기
    temp = array[:idx] + [0] + array[idx:-1]
    return temp

def calculate_sum(array):
    count = 0
    for i in range(N):
        if C[i] == array[i]:
            count += 1
    return count
    
def check(array, K):
    global answer
    answer = max(answer, calculate_sum(array))

    if K:
        for idx in range(N):
            check(pull(idx, array), K-1)
            check(push(idx, array), K-1)

def solution():
    check(P, K)
    return answer

print(solution())

🎵 두번째 풀이

import copy

N, K = map(int, input().split())            # 문제 수 N, 밀고 당길 수 있는 최대 횟수 K
C = list(map(int, input().split()))         # 각 문제의 정답을 나타내는 정수
P = list(map(int, input().split()))         # 민규가 OMR 카드에 기입한 답안

answer = 0

def pull(idx, array):     # 당기기
    temp = copy.deepcopy(array)
    temp.pop(idx)
    temp.append(0)
    return temp

def push(idx, array):     # 밀기
    temp = copy.deepcopy(array)
    temp.insert(idx, 0)
    temp.pop(-1)
    return temp

def calculate_sum(array):
    count = 0
    for i in range(N):
        if C[i] == array[i]:
            count += 1
    return count
    
def check(array, K):
    global answer
    answer = max(answer, calculate_sum(array))

    if K:
        for idx in range(N):
            check(pull(idx, array), K-1)
            check(push(idx, array), K-1)

def solution():
    check(P, K)
    return answer

print(solution())

🎵 세번째 풀이

import copy

N, K = map(int, input().split())            # 문제 수 N, 밀고 당길 수 있는 최대 횟수 K
C = list(map(int, input().split()))         # 각 문제의 정답을 나타내는 정수
P = list(map(int, input().split()))         # 민규가 OMR 카드에 기입한 답안

answer = 0

def pull(idx, array):     # 당기기
    temp = copy.deepcopy(array)
    temp.pop(idx)
    temp.append(0)
    return temp

def push(idx, array):     # 밀기
    temp = copy.deepcopy(array)
    temp.insert(idx, 0)
    temp.pop(-1)
    return temp
    
def check(array, K):
    global answer
    answer = max(answer, sum(C[i] == array[i] for i in range(N)))

    if K:
        for idx in range(N):
            check(pull(idx, array), K-1)
            check(push(idx, array), K-1)

def solution():
    check(P, K)
    return answer

print(solution())

🎵 네번째 풀이

N, K = map(int, input().split())            # 문제 수 N, 밀고 당길 수 있는 최대 횟수 K
C = list(map(int, input().split()))         # 각 문제의 정답을 나타내는 정수
P = list(map(int, input().split()))         # 민규가 OMR 카드에 기입한 답안

answer = 0
    
def check(array, idx, K):
    global answer
    answer = max(answer, sum(C[i] == array[i] for i in range(N)))

    if K:
        for idx in range(N):
            check(array[:idx] + array[idx+1:] + [0], idx+1, K-1)
            check(array[:idx] + [0] + array[idx:-1], idx+1, K-1)

def solution():
    check(P, 0, K)
    return answer

print(solution())

✒️ 생각

---

1. 문제의 포인트는 어디에서라도 당기기와 밀기가 발생할 수 있다 (내가 고려하지 못한 것)
   예를 들어 3번째 위치에서 밀기한 이후, 1번째 위치에서 당기기가 발생할 수도 있다.

2. deepcopy로 복사한 후 새로운 배열을 만드는 방법보다는 슬라이싱을 통해 배열을 만드는 방법이 더 효율적 (당연한 걸 수도 있지만)

3. sum을 통해서 값이 동일한 경우의 개수를 세는 방법보다는 직접 하나씩 세는 방법(calculate_sum)이 조금 더 빠름