두번째 pramp mock 인터뷰 경험이다.
문제
1은 섬을 0은 바다를 나타낸다. 상하좌우로 인접한 1은 하나의 섬이다. 총 섬의 갯수를 구하라.
input: binaryMatrix = [ [0, 1, 0, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 1] ]
output: 6 # since this is the number of islands in binaryMatrix.
# See all 6 islands color-coded below.
https://www.pramp.com/challenge/yZm60L6d5juM7K38KYZ6
이문제와도 동일: Leetcode-200.-Number-of-Islands
https://velog.io/@soopsaram/Leetcode-200.-Number-of-Islands
해결 O(n) / O(1)
익숙한 유형의 문제였고, visited체크를 통해서 dfs로 해결하는 문제였다. 처음에 mark_island()를 bool타입으로 리턴을 받으려고 해서 잘 안풀려서 버벅였다. 어쨋든 mark_island()가 visit체크만 하는 void리턴타입 함수로 해서 잘 해결했다.
#include <stdio.h>
#include <stdlib.h>
int r_size;
int c_size;
//void mark_island(int (*mat)[c_size], int r, int c) {
void mark_island(int mat[][c_size], int r, int c) {
if (r < 0 || r >= r_size || c < 0 || c >= c_size)
return;
if (mat[r][c] == 0)
return;
mat[r][c] = 0; // marked
mark_island(mat, r - 1, c);
mark_island(mat, r, c - 1);
mark_island(mat, r + 1, c);
mark_island(mat, r, c + 1);
}
int getNumberOfIslands(size_t numRows, size_t numCols, int binaryMatrix[numRows][numCols])
{
int islands = 0;
r_size = numRows;
c_size = numCols;
for (int r = 0; r < numRows; r++) {
for (int c = 0; c < numCols; c++) {
if (binaryMatrix[r][c] == 1) {
islands++;
mark_island(binaryMatrix, r, c);
}
}
}
return islands;
}
int main() {
int m[2][2] = {{1, 0}, {0, 1}};
int result = getNumberOfIslands(2,2,m);
printf("%d", result);
return 0;
}2차원 배열의 포인터 타입
그런데 실제 pramp에서 정확한 답이 안나왓는데, segmentation fault가 난것같다.(로그상에 안나옴). 원인은 이차원 배열 포인터를 매개변수로 전달하는 방식이 틀려서 였다.
-
처음에 아래와 같이 포인터를 전달했다. 내 local pc에서 컴파일해보니 아래와 같은 컴파일 warning발생. 2차원 배열은 포인터타입을 이렇게 전달하면 안된다.
void mark_island(int **mat, int r, int c) {에러로그
warning: incompatible pointer types passing 'int (*)[numCols]' to parameter of type 'int **' [-Wincompatible-pointer-types] -
2차원 배열의 정확한 포인터 전달 방법 -> column의 사이즈를 명시할것.
column 사이즈를 명시하지 않으면, 해당 포인터의 포인터 연산시 증감 사이즈를 알 방법이 없다. 따라서 함수 내부에서 mat[i][j] 형태로 사용할 수 없다.void mark_island(int mat[][c_size], int r, int c) {또는 이렇게, 포인터인것을 명확히 하기위해 아래와 같이 하는게 더 가독성이 높을것같다.
void mark_island(int (*mat)[c_size], int r, int c) {
int (*mat)[4] 의 정확한 의미는 mat은 포인터 연산시 sizeof(int) * 4 크기 만큼 값이 증가하고 감소하는 포인터 형이라는 의미다.
- 참고
개선할 점
- 잘 아는 문제도 역시 누가 보는데 풀면 버벅이게 된다. -> mock인터뷰를 더 많이 경험해보면 나아질듯
- time complexity를 말할때 O(n)이라고 했는데, n이 뭐냐고 물어봄. 앞으로는 더 정확히 말해야할것같다. 정확히는 O(m*n) 이 맞다.
- dfs 순회의 리턴타입에대해 고민하다가 막혀서 시간을 많이 날렸다. 인터뷰어도 혼자 끙끙거리고 있으니, 물어보라고 말함. 이 경우 코드를 작성하기 전에 dfs순회방식에 대해 충분히 설계를 하고 작성을 시작해야했다.
- 구현방식에 대해서는 인터뷰이가 제시한 방식대로 할 필요없음. 내가 자신있는 방식으로 풀기. 재귀로 풀어야할것같은데 인터뷰이가 iterative로 푸는게 좋겠다고 함. 그냥 재귀로 풀겟다고 하고 그렇게 푸는게 나음.
- 인터뷰어가 힌트를 주는데 영어를 잘 알아듣지 못했다!
- 여러가지 솔루션에 대한 아이디어를 제시하지 못했음.
- 생각해보니 코너/엣지 케이스에대해서 충분히 논의하지 않은것 같음.
- 마지막으로 가장 중요한것 문법! -> C언어의 2차원배열 포인터를 함수의 매개변수로 전달하는방식. 예전에도 조금 햇갈려했었는데, 이번 기회에 확실히 숙지하게 될것같음.
- 결과적으로 로직상에 문제는 없었지만, 문법 오류로 pramp상에서 정확한 답이 나오지 못했다. -> 잘하자.
