[프로그래머스/JAVA] 이웃한 칸

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

https://school.programmers.co.kr/learn/courses/30/lessons/250125?language=java

프로그래머스

 

---

📌 문제 요약

 

 

🎨 인접한 칸에 있는 같은 색 개수 찾기

• 2차원 격자 모양의 보드판이 주어진다.
• 각 칸에는 색깔이 하나씩 칠해져 있다.
• 이 보드칸에서 한 칸을 선택했을 때, 그 칸의 위, 아래, 왼쪽, 오른쪽에 있는 인접한 칸들 중에서 같은 색깔로 칠해진 칸의 개수를 구해야 한다.

 

---

💡 아이디어

1️⃣ 방향 탐색

방향을 직접 하드코딩하기 보다는, 아래와 같이 변화량 배열을 사용하면 더 간단하게 4 방향을 처리할 수 있다.

int[] dh = {0, 1, -1, 0}; // 행 변화량
int[] dw = {1, 0, 0, -1}; // 열 변화량

 

예를 들어 i = 0일 때는 (h, w + 1) → 오른쪽, i = 1일 때는 (h + 1, w) → 아래쪽을 의미한다.

 

 

2️⃣ 범위 체크

if (0 <= h_check && h_check < n && 0 <= w_check && w_check < n)

 

만약 (h + dh[i], w + dw[i])가 보드 밖이라면, 색을 비교하면 안되기 때문에 위와 같이 범위 체크를 해줘야 한다.

 

 

3️⃣ count 증가

if (board[h][w].equals(board[h_check][w_check])) {
    count++;
}

 

범위를 벗어나지 않으면서, 기준 칸과 색깔이 동일하다면 count를 1만큼 증가시켜준다.

 

---

👩🏻‍💻 최종 코드

 

class Solution {
    public int solution(String[][] board, int h, int w) {
        int n = board.length;
        int count = 0;
        
        int[] dh = {0, 1, -1, 0};
        int[] dw = {1, 0, 0, -1};
        
        for(int i = 0; i < 4; i++){
            int h_check = h + dh[i];
            int w_check = w + dw[i];
            
            if(h_check >= 0 && h_check < n && w_check >= 0 && w_check < n){
                if(board[h][w].equals(board[h_check][w_check])){
                    count++;
                }
            }
        }
        
        return count;
    }
}

 

---

🕑 시간 복잡도

for (int i = 0; i < 4; i++) {
    ...
    if (board[h][w].equals(board[h_check][w_check])) {
        count++;
    }
}

 

• 이 반복문은 항상 4번만 실행된다. (상, 하, 좌, 우)
• 내부 연산은 단순한 문자열 비교 1회와 조건문 검사이다.

👉🏻 즉, 시간 복잡도는 O(1) 이다.