Q × P 크기의 격자(grid)가 주어졌다고 가정해 보겠습니다. 이 격자에는 정확히 세 개의 별표('*')가 있고, 나머지 칸은 모두 점('.')으로 채워져 있습니다. 여기서 '*'는 직사각형의 꼭짓점을 의미합니다. 우리의 목표는 누락된 네 번째 꼭짓점의 좌표를 찾는 것입니다. 이 문제에서는 1부터 시작하는 인덱싱(1-based indexing)을 사용합니다.
예를 들어 입력이 grid = [".*.", "...", "*.*"]라면 출력은 (1, 3)이 됩니다. 이것이 바로 누락된 좌표입니다.
문제 해결 접근 방식
이 문제의 핵심 아이디어는 간단합니다. 직사각형의 꼭짓점들은 항상 두 개의 행과 두 개의 열에 걸쳐 존재하며, 각 행과 열에는 두 개의 '*'가 포함됩니다. 따라서 '*'가 단 하나만 있는 행과 열을 찾으면, 그 교차 지점이 곧 누락된 네 번째 꼭짓점의 위치입니다.
다음 단계에 따라 문제를 해결할 수 있습니다.
p := 행의 개수
q := 열의 개수
row := 모든 행 번호를 키로 하고 값이 0인 맵(map) 생성
col := 모든 열 번호를 키로 하고 값이 0인 맵(map) 생성
i를 0부터 p까지 반복:
j를 0부터 q까지 반복:
grid[i][j]가 '*'와 같다면:
row[i] := row[i] + 1
col[j] := col[j] + 1
row 맵에서 값이 1인 키 k를 찾아 x_coord := k로 설정
col 맵에서 값이 1인 키 k를 찾아 y_coord := k로 설정
(x_coord + 1, y_coord + 1) 반환 (1-based 인덱싱 적용)
이 알고리즘의 시간 복잡도는 O(p × q)이며, 공간 복잡도는 O(p + q)입니다.
예제 구현
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def get_missing_vertex(grid) :
p = len(grid)
q = len(grid[0])
row = dict.fromkeys(range(p), 0)
col = dict.fromkeys(range(q), 0)
for i in range(p) :
for j in range(q) :
if (grid[i][j] == '*') :
row[i] += 1
col[j] += 1
for k,v in row.items() :
if (v == 1) :
x_coord = k
for k,v in col.items() :
if (v == 1) :
y_coord = k
return (x_coord + 1, y_coord + 1)
grid = [".*.", "...", "*.*"]
print(get_missing_vertex(grid))
입력
[".*.", "...", "*.*"]
출력
(1, 3)