LeetCode (C/C++, Java) 419. Battleships in a Board

https://leetcode.com/problems/battleships-in-a-board/

---

풀이

공간복잡도가 O(1)이고 한 번만 순회하여 답을 구해야 했다.
주어진 battleship은 수직 혹은 수평으로만 주어지기에 위에서부터 순회하며 현재 셀에 battleship이 있고, 해당 셀의 위쪽 혹은 왼쪽이 X가 아니라면 즉, 이미 카운팅된 battleship이 아니라면 카운트 해 답을 구했다.

---

C/C++ 코드

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int row = board.size();
        int col = board[0].size();

        int cnt = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '.') continue;`
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;

                cnt++;
            }
        }
        return cnt;
    }
};

 

Java 코드

class Solution {
    public int countBattleships(char[][] board) {
        int row = board.length;
        int col = board[0].length;

        int cnt = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == '.') continue;`
                if (i > 0 && board[i - 1][j] == 'X') continue;
                if (j > 0 && board[i][j - 1] == 'X') continue;

                cnt++;
            }
        }
        return cnt;
    }
}