크기가 Q * P인 그리드가 있다고 가정하고 이 그리드에는 정확히 3개의 별표 '*'가 있고 다른 모든 셀에는 점 '.'이 있습니다. 여기서 '*'는 직사각형의 꼭짓점입니다. 누락된 정점의 좌표를 찾아야 합니다. 여기에서는 1 기반 인덱싱을 고려할 것입니다.
따라서 입력이 grid =[ ".*.", "...", "*.*" ]와 같으면 출력은 [1, 3]이 됩니다. 이것은 누락된 좌표입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
p :=행 수
-
q :=열 수
-
row :=모든 행 번호에 대한 맵을 만들고 관련 값은 0
-
col :=모든 열 번호에 대한 맵을 만들고 관련 값은 0
-
범위 0에서 p까지의 i에 대해 수행
-
0에서 q 범위의 j에 대해 수행
-
grid[i, j]가 '*'와 같으면
-
행[i] :=행[i] + 1
-
열[j] :=열[j] + 1
-
-
-
행의 각 k,v에 대해 수행
-
v가 1과 같으면
-
x_coord :=k;
-
-
-
열의 각 k,v에 대해 수행
-
v가 1과 같으면
-
y_coord :=k;
-
-
-
-
return(x_coord + 1, y_coord + 1)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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)