[Baekjoon] 33559/Infinite Array Swaps/Python/파이썬

💡문제

이 문제는 Finite Array Swaps와 굵은 글씨로 적힌 부분과 입출력만 다릅니다.

동우는 길이가 $N$인 두 배열 $A=\left[ A_1,A_2,\cdots ,A_N \right]$과
$B=\left[ B_1,B_2,\cdots ,B_N \right]$을 가지고 있다.

동우는 두 배열에 다음 두 시행을 각각 원하는 만큼 할 수 있다. 교환하는 두 원소의 인덱스는 달라야 한다.

• 배열 $A$에서 두 원소를 골라 교환한다.
• 배열$B$에서 두 원소를 골라 교환한다.

이 연산을 통해 얻은 최종 상태에서의 두 배열을 $A^\prime=\left[ A_1^\prime,A_2^\prime,\cdots ,A_N^\prime \right]$과 $B^\prime=\left[ B_1^\prime,B_2^\prime,\cdots ,B_N^\prime \right]$이라 할 때, 동우는 $A_i^\prime=B_i^\prime$를 만족하는 쌍의 개수를 최대화하려고 한다. 두 배열이 주어질 때, 이를 최대로 하는 교환을 찾아보자.

입력

첫 번째 줄에 두 배열의 길이 $N(1\le N\le 10^5)$이 주어진다.

두 번째 줄에 배열 $A$의 원소 $A_1,A_2,\cdots ,A_N(1\le A_i\le 10^9)$이 공백으로 구분되어 주어진다.

세 번째 줄에 배열 $B$의 원소 $B_1,B_2,\cdots ,B_N(1\le B_i\le 10^9)$이 공백으로 구분되어 주어진다.

주어지는 입력은 모두 정수이다.

출력

GUN이 쓴 곡의 구간의 초당 박자 변화량의 합을 입력 순서대로 Q 줄에 걸쳐 출력한다.

예제입력

6
2 4 3 3 2 4
3 1 6 8 2 2

예제출력

3
4 3 2 4 3 2
1 6 2 8 3 2

---

📖내가 작성한 Code

import sys
import collections

'''
그냥 같은거 찾으면 안됨?
1초에 10**5
근데 for 하나로 해야 하네
'''


def find_same_numbers(a,b):
    count_a = collections.Counter(a)
    count_b = collections.Counter(b)

    combinations_number = []
    not_combinations_a = []
    not_combinations_b = []

    for i in set(a+b):
        if i in count_a and i in count_b:
            common = min(ca := count_a[i],cb := count_b[i])
            combinations_number.extend([i] * common)
            if (cnt_a := ca - common) > 0:
                not_combinations_a.extend([i] * cnt_a)
            if (cnt_b := cb - common) > 0:
                not_combinations_b.extend([i] * cnt_b)
        elif i in count_a:
            not_combinations_a.extend([i] * count_a[i])
        else:
            not_combinations_b.extend([i] * count_b[i])
    return combinations_number, not_combinations_a,not_combinations_b


def main():
    inputs = sys.stdin.read().split()
    n = int(inputs[0])
    combinations_number,not_combinations_a,not_combinations_b =(
        find_same_numbers(inputs[1:n+1],inputs[n+1:]))

    sys.stdout.write(str(len(combinations_number))+'\n')
    sys.stdout.write(" ".join(combinations_number + not_combinations_a) + '\n')
    sys.stdout.write(" ".join(combinations_number + not_combinations_b))


if __name__ == '__main__':
    main()

---

✍️풀이과정

문제를 잘못 읽어서 시간을 많이 소비한 문제. 단순 구현 문제라고 생각하니, 종이에 수도코드를 적어서 엣지 케이스를 방지하는게 중요하다고 생각한다. 그리고 sys.stdout.write 실수로 2번 틀려서 멘탈이 약간 흔들렸다. 앞으로는, print를 쓰고 최적화 할 때 변경하려고 한다.

2등. 1등의 경우 dic.get을 이용함. 나는 Counter를 사용. 케이스 차이라고 생각.

---

🧠 코드 리뷰

1. 함수 분리 : match_elements 함수를 분리하여, 배열에서 매칭 가능한 원소와 남은 원소를 구분하는 로직을 모듈화 했습니다.
2. 가독성, 변수명, 출력 형식, 순서 보장, 입력 파싱을 주의할 필요가 있습니다.

---

🛠️AI 개선 코드

import sys
import collections

def match_elements(array_a, array_b):
    """
    두 배열에서 각 원소의 등장 빈도를 계산한 후,
    - matched: 두 배열 모두에서 매칭 가능한 원소(최소 빈도만큼) 리스트
    - remaining_a: array_a에서 매칭 후 남은 원소 리스트
    - remaining_b: array_b에서 매칭 후 남은 원소 리스트
    를 반환합니다.
    """
    count_a = collections.Counter(array_a)
    count_b = collections.Counter(array_b)

    matched = []       # 두 배열에서 매칭된 원소들을 저장
    remaining_a = []   # array_a에만 남는 원소들을 저장
    remaining_b = []   # array_b에만 남는 원소들을 저장

    # 두 배열에 등장하는 모든 고유 원소에 대해 처리
    for element in set(array_a + array_b):
        # element가 두 배열 모두에 있을 경우
        if element in count_a and element in count_b:
            common = min(count_a[element], count_b[element])
            matched.extend([element] * common)
            # array_a에 남는 개수가 있다면 추가
            if (leftover_a := count_a[element] - common) > 0:
                remaining_a.extend([element] * leftover_a)
            # array_b에 남는 개수가 있다면 추가
            if (leftover_b := count_b[element] - common) > 0:
                remaining_b.extend([element] * leftover_b)
        # element가 array_a에만 있을 경우
        elif element in count_a:
            remaining_a.extend([element] * count_a[element])
        # element가 array_b에만 있을 경우
        else:
            remaining_b.extend([element] * count_b[element])
    return matched, remaining_a, remaining_b

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    # 배열 A와 B를 각각 n개의 원소로 분리
    array_a = data[1:n+1]
    array_b = data[n+1:2*n+1]

    matched, leftover_a, leftover_b = match_elements(array_a, array_b)
    # 최종 배열은 매칭된 원소를 앞부분에 두고 나머지 원소를 뒤에 이어붙입니다.
    final_array_a = matched + leftover_a
    final_array_b = matched + leftover_b

    sys.stdout.write(str(len(matched)) + '\n')
    sys.stdout.write(" ".join(final_array_a) + '\n')
    sys.stdout.write(" ".join(final_array_b))
    
if __name__ == '__main__':
    main()

---

💻결과

백준문제 보러가기

---

🖱️참고 링크

파이썬 참고 딕셔너리 자료형