LeetCode 1582. Special Positions in a Binary Matrix
#Easy #Array #Matrix
https://leetcode.com/problems/special-positions-in-a-binary-matrix/description/
- 통과 코드: (1) set 이용하여 행 / 열 정보 저장 (2) set 이용하여 좌표 저장 (3) sum 이용
문제 요약
mat라는 매트릭스가 주어진다. 크기가 m x n이고, 각 칸은 0 또는 1로 채워져 있다.
(i, j) 좌표에 대하여, mat [ i ][ j ] == 1이면서 i 행과 j 열에 있는 다른 좌표들이 모두 0이라면 (i, j) 는 "특별한 좌표"이다.
즉, mat [ i ][ j ] 를 제외하고 i 행과 j 열에 있는 좌표들에 1이 없다면 (i, j) 는 "특별한 좌표"이다.
주어진 매트릭스 mat에 있는 "특별한 좌표"의 개수를 구하라.
문제 접근
- 1차 접근 방법: 이중 for문 3개, set 자료 구조 2개 이
<문제 요구사항 이해>
(i, j) 가 "특별한 좌표"가 되려면 다음 두 조건을 만족해야 한다.
(1) 행(i) 의 관점: i 번째 행에서 m개의 열 중 j 번째 열 하나에만 1이 있어야 함
(2) 열(j) 의 관점: j 번째 열에서 n개의 행 중 i 번째 행 하나에만 1이 있어야 함
이러한 조건을 만족하는 (i, j) 를 찾는 코드를 금방 짤 수 있을 줄 알았는데 최종적으로 답을 구하기까지 30분이나 걸렸다.
<문제 풀이 틀>
- 모든 행과 열을 탐색하면서 mat [ i ][ j ] == 1 인 좌표를 만났을 때 의미 있는 처리를 해주려고 했다. 이를 위해 이중 for문을 짰다.
- 바깥 for문은 하나의 행(i)에 대하여, 모든 열(j)을 탐색한다. 바깥 for문이 한 번 돌 때마다, 그 행에서 1을 가지고 있는 열의 개수를 셌다. 그리고 count 라는 변수에 저장했다.
- 바깥 for문이 한 번 다 돌았을 때 count가 1이라면 그 행 (i 번째 행)의 모든 열은 "특별한 좌표"의 조건을 충족한다. 반면 바깥 for문이 한 번 다 돌았을 때 count가 2 이상이라면 그 행 (i 번째 행)의 모든 열은 절대로 "특별한 좌표"가 될 수 없다.
# 각 행에 대하여 모든 열의 좌표를 탐색하는 이중 for 문
m = len(mat)
n = len(mat[0])
# 1. 각 행에 대하여 모든 열의 좌표를 탐색하는 이중 for 문
for i in range(m):
count = 0
for j in range(n):
if mat[i][j] == 1:
count += 1
if count == 1:
# 어떤 처리를 해주어야 할까?
<어려웠던 점>
m 개의 열 중에서 어떤 열 (i 번째 열)이 "특별한 좌표"의 후보에 포함되고, 어떤 열 (i 번째 열)이 "특별한 좌표"의 후보에서 아예 제외되는지 알아내는 것까지는 간단했다. 그런데 다음과 같은 부분들에서 어려움을 겪었다.
(1) 하나의 열에 대하여 모든 행의 좌표를 탐색하는 이중 for문 짜기
위에서 작성한 이중 for문으로 "특별한 좌표"가 있을 수 있는 행 (i 번째 행)의 후보를 추렸듯이, "특별한 좌표"가 있을 수 있는 열 (j 번째 열)의 후보도 추려봐야겠다고 생각했다. 그런데 열은 고정시키면서 모든 행을 순회하는 이중 for문이 바로 써지지 않았다. 기본적인 코딩인데도 바로바로 생각나지 않았다니 아쉽다.
열을 고정시키면서 그 열의 모든 행을 순회하는 이중 for문은 다음과 같이 짤 수 있다.
# 각 열에 대하여 모든 행의 좌표를 탐색하는 이중 for 문
# 2. 각 열에 대하여 모든 행의 좌표를 탐색하는 이중 for 문
for j in range(n):
count = 0
for i in specialRows:
if mat[i][j] == 1:
count += 1
if count == 1:
# 어떤 처리를 해주어야 할까?
바깥 for문에서 카운터 변수로 i 를 쓰고 안쪽 for문에서 카운터 변수로 j 를 써도 코드가 잘 돌아가게 코드를 짤 수 있다. 그렇지만 바깥 for문은 열을, 안쪽 for문은 행을 순회한다는 것을 직관적으로 보여주려면 이 코드와 같이 바깥 for문에 j 를, 안쪽 for문에 i 를 쓰는 편이 좋아보인다. 그리고 이렇게 하면 좌표들을 첫 번째 이중 for문과 일관되게 mat [ i ][ j ] 와 같이 표현할 수 있다.
(2) "특별한 좌표"의 개수를 세는 방법
지금까지 "특별한 좌표"가 있을 수 있는 행을 찾는 이중 for 문과 "특별한 좌표"가 있을 수 있는 열을 찾는 이중 for 문 2개를 만들었다. 이를 통해 후보가 되는 열 / 행들을 각각 specialRows와 specialCols라는 set에 넣어주었다. 자료구조로 set을 선택한 이유는 specialRows와 specialCols가 중복을 허용하지 않는 집합이기 때문이다.
이렇게 하고 두 set를 이용해서 "특별한 좌표"의 수를 구해줄 때 specialRows에 있는 row index가 specialCols에 있으면 "특별한 좌표"라고 보고 개수 카운팅을 해주었는데 이는 잘못된 로직이었다.
# 잘못된 코드: set에 "특별한 좌표"가 있을 수 있는 행 / 열 정보만 저장, specialRows와 specialCols 모두에 있는 인덱스의 개수 세기
m = len(mat)
n = len(mat[0])
# 1. 각 행에 대하여 모든 열의 좌표를 탐색하는 이중 for 문
# - "특별한 좌표"가 있을 수 있는 열을 specialRows에 저장
specialRows = set()
for i in range(m):
count = 0
for j in range(n):
if mat[i][j] == 1:
count += 1
if count == 1:
specialRows.add(i)
# 2. 각 열에 대하여 모든 행의 좌표를 탐색하는 이중 for 문
# - "특별한 좌표"가 있을 수 있는 열을 specialCols에 저장
specialCols = set()
for j in range(n):
count = 0
for i in range(m):
if mat[i][j] == 1:
count += 1
if count == 1:
specialCols.add(j)
# 3. 두 세트에 모두 있는 인덱스의 개수를 카운팅하여 "특별한 좌표"의 개수를 구함 (잘못된 로직)
result = 0
for row in specialRows:
if row in specialCols:
result += 1
return result
성공한 테스트 케이스들을 보면 "특별한 좌표"가 모두 i == j 인 경우이다. specialRows에 저장된 행이 specialCols에 있는지 확인하는 방법으로 "특별한 좌표"의 개수를 구할 수 있는 것은 이렇게 i == j일 때뿐이다.
실패한 테스트 케이스를 보면 "특별한 좌표"에 해당하는 좌표가 (0, 2), (3, 1) 로 i != j이다.
[0, 0, 1, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 1, 0, 0]
- specialRows: {0, 3}
- specialCols: {1, 2}
specialRows에 있는 row index가 specialCols에 없지만 "특별한 좌표"가 2개이다.
if row in specialCols: result += 1 라는 코드가 잘못된 이유를 보여주는 반례이다.
<최종 코드>
# 최종 코드 (1) "특별한 좌표"의 개수를 카운팅하는 for문 및 if 조건문 수정
specialRows와 specialCols의 정보만 가지고 "특별한 좌표"의 개수를 구하기에는 역부족이다.
"특별한 좌표"는 (i, j)에 대하여 i가 specialRows에 있고, j가 specialCols에 있으며 mat [ i ][ j ] == 1 일 때를 말한다. 이중 for 문을 한 번 더 돌면서 이러한 조건을 충족하는 좌표들의 개수를 세주어야 한다.
(이전까지는 모두 동일)
# 3. 해당 좌표에 1이 있으면서 i행이 special이고, j열이 special이면 그것은 "특별한 좌표"
result = 0
for i in range(m):
for j in range(n):
if mat[i][j] == 1 and i in specialRows and j in specialCols:
result += 1
return result
# 최종 코드(2) set에 "특별한 좌표"의 후보가 되는 (i, j)를 저장
set에 행 / 열 만 담는 것이 아니라 "특별한 좌표"가 될 수 있는 후보 좌표 그 자체를 담는 방법이다.
m = len(mat)
n = len(mat[0])
# 1. 각 행에 대하여 모든 열의 좌표를 탐색하는 이중 for 문
# - "특별한 좌표"의 후보를 specialRows에 저장
specialRows = set()
for i in range(m):
oneCount = 0
save = ()
for j in range(n):
if mat[i][j] == 1:
oneCount += 1
save = (i, j)
if oneCount == 1:
specialRows.add(save)
# 2. 각 열에 대하여 모든 행의 좌표를 탐색하는 이중 for 문
# - "특별한 좌표"의 후보를 specialCols에 저장
specialCols = set()
for j in range(n):
oneCount = 0
save = ()
for i in range(m):
if mat[i][j] == 1:
oneCount += 1
save = (i, j)
if oneCount == 1:
specialCols.add(save)
# 3. "특별한 좌표"의 개수 출력
result = 0
for sr in specialRows:
if sr in specialCols:
result += 1
# 두 set의 교집합의 개수를 구해도 됨
# result = len(specialRows & specialCols)
return result
- 2차 접근
다른 분들의 풀이를 보니 set를 굳이 이용하지 않아도 됐다. 그리고 이중 for 문 안에서 count라는 변수를 두어 count == 1인지 확인할 필요도 없었다. 어떤 행 / 열에 "특별한 좌표"가 있는지 없는지는 행 / 열별로 sum을 구해보면 바로 알 수 있기 때문이다. 각 행 / 열별 sum의 합을 저장하는 리스트만 생성해두면 문제를 풀이할 수 있었다.
# 좋은 코드
m = len(mat)
n = len(mat[0])
# 행별 / 열별 합계 구하기
rowSum = [sum(row) for row in mat]
colSum = [sum(mat[i][j] for i in range(m)) for j in range(n)]
# "특별한 좌표"의 개수 구하기
result = 0
for i in range(m):
for j in range(n):
if mat[i][j] == 1 and rowSum[i] == 1 and colSum[j] == 1:
result += 1
return result
rowSum, colSum 리스트를 생성하는 코드를 한 줄에 쓰기도 했고, 불필요한 자료구조나 변수를 쓰지 않아서 코드가 매우 간결해졌다.
문제 풀이 정리
set를 이용한 나의 코드도 타당한 코드이기는 하다. 다만, 최종적으로 "특별한 좌표"의 개수를 구할 때 조건을 어떻게 걸어줘야 할지 감을 잘 잡지 못한 것이 시간이 오래 걸린 이유인 것 같다. specialRows와 specialCols를 구하고 나서 그 둘만 가지고 "특별한 좌표"를 구하려고 한 것이 문제였다. "특별한 좌표"란 어떤 좌표를 말하는 것인지 코드상으로 정의를 내리지 못한 것이다. 결론적으로 얘기하자면 어떤 좌표 (i, j)에 대하여 i와 j가 각각 specialRows 및 specialCols에 포함되어 있고 그 좌표에 1이 있을 때가 "특별한 좌표"이다.
회고
아직은 알고리즘 문제를 풀이할 때 시뮬레이션식으로밖에 접근하지 못하는 것 같다.
매트릭스를 예로 들면, 내 코드는 모든 좌표를 모두 방문하면서 정보를 수집한다. 하지만 좋은 코드들을 보면 행별 / 열별 sum을 이용하는 것처럼 모든 좌표를 직접 방문하지 않고도 목표하는 정보를 수집한다. 현재 나의 코드와 좋은 코드 사이에는 높은 벽이 있는 것처럼 느껴진다. 좋은 코드들을 많이 보면서 내 것으로 만드는 시간이 많이 필요할 것 같다.