[Leetcode]554. Brick Wall

문제 요약

• 알고리즘 분류:  배열, 해쉬
• 난이도: Medium
• 문제내용:
  • . n개의 벽돌 행으로 이루어진 직사각형 벽돌 벽이 있습니다. 각 행의 벽돌들은 같은 높이(1단위)를 가지지만, 너비는 다를 수 있습니다. 모든 행의 총 너비는 동일합니다.
  • 벽에 대한 정보를 담고 있는 2D 배열 wall이 주어졌을 때, 이러한 수직선을 그린 후 가로지르는 벽돌의 최소 개수를 반환 하여라
• 사이트 주소: https://leetcode.com/problems/brick-wall/description/

문제풀이

이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다:

1. 벽돌을 가로지르지 않으려면, 선이 벽돌의 경계(두 벽돌 사이)를 통과해야 합니다.
2. 최소 개수의 벽돌을 가로지르려면, 최대한 많은 행에서 벽돌 경계를 통과해야 합니다.
3. 즉, 벽돌 경계가 가장 많이 정렬된 위치에 선을 그어야 합니다.

풀이 접근

1. 각 행을 순회하면서 벽돌 경계의 위치(누적 너비)를 기록합니다.
2. 이 위치들의 빈도수를 카운트합니다.
3. 가장 많이 등장하는 경계 위치를 찾습니다. 이 위치에 선을 그으면 최대한 많은 행에서 벽돌을 가로지르지 않게 됩니다.
4. 결과적으로, 전체 행 수에서 가장 많이 등장하는 경계의 빈도수를 빼면 가로지르는 벽돌의 최소 개수가 됩니다.

예제

 위 설명으로 이해가 안 될수 있어서 아래와 같은 예제를 한번 보자

wall = [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]]

이 벽은 다음과 같은 구조를 가집니다:

| 1 | 2 | 2 | 1 |
|   3   | 1 | 2 |
| 1 |   3   | 2 |
|   2   |   4   |
|   3   | 1 | 2 |
| 1 |   3   |1|1|

경계 위치의 빈도수를 계산하면:

• 위치 1: 3번 등장
• 위치 3: 3번 등장
• 위치 4: 1번 등장
• 위치 5: 4번 등장
• 위치 6: 2번 등장

가장 많이 등장하는 경계는 위치 5로, 4번 등장합니다. 따라서 위치 5에 선을 그으면 6-4=2개의 벽돌만 가로지르게 됩니다.

 

마무리

위 구현 방식대로 하면 시간 복잡도는  한  row와 row의 벽돌 개수 만큼 처리 해야 되기 때문에 O(N^2)이 됩니다.

이 문제는 해시맵을 활용하여 벽돌 경계의 빈도수를 효율적으로 계산하는 방식으로 해결할 수 있습니다. 가장 많은 행에서 벽돌 경계가 정렬된 위치에 선을 그으면 최소 개수의 벽돌을 가로지르게 됩니다. 이는 전체 행 수에서 최대 경계 빈도수를 뺀 값과 같습니다.

Code

Python

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        size = len(wall) # 벽의 총 행 수
        map = defaultdict(int) # 벽돌 경계의 위치와 그 빈도수를 저장하는 맵

        for i in range(size):
            length = 0 # 현재까지의 누적 길이
            for j in range(len(wall[i]) - 1): # 마지막 벽돌은 벽의 끝이므로 제외
                length += wall[i][j] #  현재 벽돌의 길이를 누적
                map[length] += 1 # 현재 경계 위치의 빈도수를 증가

        return size - max(map.values(), default= 0) # 벽의 전체 행 수에서 최대 경계선을 뺀 값이 최소로 가로지르는 벽돌 수

 

Java

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int size = wall.size(); // 벽의 총 행 수
        Map<Integer, Integer> map = new HashMap<>(); // 벽돌 경계의 위치와 그 빈도수를 저장하는 맵
        int maxCount = 0; // 가장 많이 등장하는 벽돌 경계선의 수

        for (int i = 0; i < size; i++) {
            List<Integer> row = wall.get(i); // 현재 행의 벽돌 배열을 가져옴
            int length = 0; // 현재까지의 누적 길이
            for (int j = 0; j < row.size() - 1; j++) { // 마지막 벽돌은 벽의 끝이므로 제외
                length += row.get(j); // 현재 벽돌의 길이를 누적
                int value = map.getOrDefault(length, 0) + 1; // 현재 경계 위치의 빈도수를 증가
                map.put(length, value); // 맵에 업데이트된 빈도수 저장
                maxCount = Math.max(maxCount, value); // 최대 빈도수 갱신
            }
        }

        return size - maxCount; // 벽의 전체 행 수에서 최대 경계선을 뺀 값이 최소로 가로지르는 벽돌 수
    }
}

Javascript

var leastBricks = function(wall) {
     const size = wall.length; // 벽의 총 행 수
    let map = new Map(); // 벽돌 경계의 위치와 그 빈도수를 저장하는 맵
    let maxCount = 0; // 가장 많이 등장하는 벽돌 경계선의 수

    for (let i = 0; i < size; i++) {
        const row = wall[i]; // 현재 행의 벽돌 배열을 가져옴
        let length = 0; // 현재까지의 누적 길이
        for (let j = 0; j < row.length - 1; j++) { // 마지막 벽돌은 벽의 끝이므로 제외
            length += row[j]; // 현재 벽돌의 길이를 누적
            const value = map.get(length) ? map.get(length) + 1 : 1;
            map.set(length, value); // 맵에 업데이트된 빈도수 저장
            maxCount = Math.max(maxCount, value); // 최대 빈도수 갱신
        }
    }

    return size - maxCount; // 벽의 전체 행 수에서 최대 경계선을 뺀 값이 최소로 가로지르는 벽돌 수
};