0과 1로만 구성된 이진 행렬(binary matrix)이 주어졌을 때, 서로 중복되는 행을 찾아 출력하는 것이 이번 예제의 목표입니다. 파이썬 표준 라이브러리의 Counter() 메서드를 활용하면 복잡한 로직 없이도 이 문제를 아주 간단하게 해결할 수 있습니다.
문제 예시
입력: 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 출력: (1, 1, 1, 1) (0, 0, 0, 0)
알고리즘
중복 행을 찾는 절차는 다음과 같습니다.
- 1단계: 0과 1 요소만 포함하는 이진 행렬을 생성합니다.
- 2단계: 각 행을 딕셔너리의 키(key)로, 해당 행의 등장 횟수를 값(value)으로 저장합니다. 리스트는 변경 가능(mutable)하여 해시할 수 없으므로, 먼저 각 행(리스트)을 튜플(tuple)로 변환해야 합니다.
- 3단계: Counter() 메서드를 사용해 행별 빈도 정보를 담은 딕셔너리를 만듭니다.
- 4단계: 딕셔너리 전체를 순회합니다.
- 5단계: 빈도가 1보다 큰, 즉 두 번 이상 등장한 모든 행을 출력합니다.
예제 코드
# 이진 행렬에서 중복 행을 찾는 함수
from collections import Counter
def binarymatrix(A):
A = map(tuple, A) # 각 행(리스트)을 튜플로 변환
dic = Counter(A) # 행을 키로, 빈도를 값으로 하는 딕셔너리 생성
print("Duplicate rows of Binary Matrix ::>")
for (i, j) in dic.items():
if j > 1: # 빈도가 1보다 크면 중복 행
print(i)
# 드라이버(Driver) 프로그램
if __name__ == "__main__":
A = []
n = int(input("Enter n for n x n matrix : ")) # 행렬 크기 입력
print("Enter the element ::>")
for i in range(n):
row = [] # 한 행을 임시로 저장할 리스트
for j in range(n):
row.append(int(input())) # 입력값을 행 리스트에 추가
A.append(row) # 완성된 행을 행렬에 추가
print(A)
# [[1, 1, 1, 1], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]]
# 행렬 형태로 2차원 배열 출력
print("Display Array In Matrix Form")
for i in range(n):
for j in range(n):
print(A[i][j], end=" ")
print()
binarymatrix(A)
실행 결과
Enter n for n x n matrix : 4 Enter the element ::> 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 [[1, 1, 1, 1], [0, 0, 0, 0], [1, 1, 1, 1], [0, 0, 0, 0]] Display Array In Matrix Form 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 Duplicate rows of Binary Matrix ::> (1, 1, 1, 1) (0, 0, 0, 0)
핵심 포인트 정리
- 튜플 변환이 필수입니다. 파이썬의 리스트는 내용이 언제든 바뀔 수 있어 해시(hash) 값이 고정되지 않기 때문에 딕셔너리의 키나 Counter의 원소로 사용할 수 없습니다. 반면 튜플은 불변(immutable)하므로 해시가 가능하며,
map(tuple, A)로 간단히 변환할 수 있습니다. - Counter는 빈도 계산에 최적화되어 있습니다. 반복 가능한 객체를 넘기면 각 원소의 등장 횟수를 자동으로 세어 딕셔너리 형태로 반환하므로, 직접 반복문을 돌며 개수를 세는 코드보다 훨씬 간결하고 가독성이 좋습니다.
- 시간 복잡도는 O(n²)입니다. n×n 행렬의 모든 원소를 한 번씩 확인하고 해시 기반 카운팅을 수행하므로, 전체 실행 시간은 행렬 크기에 비례합니다.