[LeetCode-74] 2차원 행렬도 결국 1차원 배열이다 - 인덱스 변환으로 이진 탐색 적용하기

• 문제 링크: https://leetcode.com/problems/search-a-2d-matrix/
• 파일 경로: src/main/java/coding_test/이진탐색/LC0074_SearchA2DMatrix.java
• 난이도: Medium

문제 설명

m x n 정수 행렬이 주어진다. 각 행은 오름차순 정렬돼 있고, 각 행의 첫 값이 이전 행의 마지막 값보다 크다. target이 행렬에 있는지 O(log(m*n))에 판별해야 한다.

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
target = 3   -> true
target = 13  -> false

시행착오

mid 계산 부호 오타

int mid = left - (right - left) / 2;   // 오타: - 여야 할 게 아니라 +

left=0, right=11로 계산하면 mid = 0 - 5 = -5, 음수 인덱스가 나오는 걸 직접 확인하고 +로 수정했다.

최종 코드

public static boolean searchMatrix(int[][] matrix, int target) {
    int left = 0;
    int right = (matrix.length * matrix[0].length) - 1;
    int n = matrix[0].length;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;

        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return false;
}

변수 추적표 (target = 3)

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], n = 4

반복	left	right	mid	row=mid/n	col=mid%n	matrix[row][col]	비교	갱신
1	0	11	0+(11-0)/2=5	5/4=1	5%4=1	matrix[1][1]=11	11>3	right=4
2	0	4	0+(4-0)/2=2	2/4=0	2%4=2	matrix[0][2]=5	5>3	right=1
3	0	1	0+(1-0)/2=0	0/4=0	0%4=0	matrix[0][0]=1	1<3	left=1
4	1	1	1+(1-1)/2=1	1/4=0	1%4=1	matrix[0][1]=3	3==3	return true

오늘 배운 내용 — 2차원을 1차원처럼 다루기

이 문제에서 가장 중요한 내용은 “2차원처럼 보이는 게 실제로는 1차원”이라는 관찰이다. 문제의 두 조건(“각 행 정렬” + “다음 행 첫 값이 이전 행 마지막 값보다 큼”)을 합치면, 행렬 전체를 한 줄로 쭉 이어붙인 게 정렬된 1차원 배열과 완전히 같다.

[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
→ [1,3,5,7, 10,11,16,20, 23,30,34,60]

그래서 left, right를 “행 번호”가 아니라 전체 원소 개수 기준 1차원 인덱스로 잡고, 704 템플릿을 그대로 쓴 다음 mid(1차원 인덱스)를 실제 행/열로 변환하면 된다:

• row = mid / n (한 행의 길이로 나눈 몫)
• col = mid % n (나머지)

오답노트

• 틀렸던 부분: mid 계산식에서 left - (right - left) / 2처럼 부호를 잘못 썼다. 704 템플릿을 손으로 다시 타이핑하면서 생긴 단순 오타였는데도 결과는 완전히 다른 값(음수 인덱스)이 나왔다.
• 왜 위험한가: 이런 부호 오타는 논리적으로는 “그럴듯해 보이는” 코드라서, 코드를 눈으로만 읽으면 잘 안 보인다. 실제로 left, right 값을 대입해서 손으로 계산해봐야 -5라는 말이 안 되는 인덱스가 나온다는 걸 알 수 있었다.
• 일반화: 2차원 배열/행렬 문제를 만났을 때, “각 행이 정렬되어 있는가” + “행 간에도 순서가 있는가”를 확인하면 1차원 이진 탐색으로 통째로 변환할 수 있는지 판단할 수 있다. 두 조건 중 하나라도 없으면(예: 각 행은 정렬됐지만 행 간 순서는 없는 경우) 이 변환은 못 쓰고 행별 이진 탐색을 두 번 해야 한다.
• 언제 다시 떠올릴까: 익숙한 템플릿을 다시 타이핑할 때일수록 오히려 오타를 의심하고, 극단적인 입력값을 대입해 손으로 검산해본다.

꿀팁

• row/col ↔ 1차원 인덱스 변환(row = idx / n, col = idx % n)은 2차원 배열을 다루는 다른 유형(DFS/BFS, 시뮬레이션 등)에서도 자주 쓰이는 변환이라 이번 기회에 확실히 손에 익혀두면 좋다.
• 코드를 짤 때 “이 조건들을 합치면 결국 무슨 자료구조와 똑같아지는가”를 먼저 따져보면, 새로운 템플릿을 만들 필요 없이 이미 아는 템플릿(1차원 이진 탐색)을 그대로 재사용할 수 있는 경우가 많다.