문제 이해하기
서로 다른 숫자들로 구성된 m × n 크기의 행렬이 주어졌을 때, 이 2차원 배열 안에서 모든 행운의 숫자(lucky number)를 찾아 임의의 순서로 반환하는 것이 이번 글의 목표입니다.
여기서 행운의 숫자란, 해당 원소가 자신이 속한 행(row)에서는 최솟값이면서 동시에 열(column)에서는 최댓값인 숫자를 의미합니다.
예시
다음과 같은 입력 배열이 있다고 가정해 보겠습니다.
const arr = [
[3,7,8],
[9,11,13],
[15,16,17]
];이때 기대되는 출력은 다음과 같습니다.
const output = [15];
그 이유는 15가 유일하게 자신이 속한 세 번째 행에서 가장 작은 값이면서, 동시에 첫 번째 열에서 가장 큰 값을 만족하는 숫자이기 때문입니다.
풀이 접근 방법
이 문제는 행렬을 여러 번 탐색하는 단순한 방법보다, 사전 계산을 활용하면 훨씬 효율적으로 해결할 수 있습니다.
- 각 행별 최솟값을 저장할 배열(min)을 준비하고 무한대(Infinity)로 초기화합니다.
- 각 열별 최댓값을 저장할 배열(max)을 준비하고 음의 무한대(-Infinity)로 초기화합니다.
- 행렬을 한 번 순회하면서 위 두 배열을 채웁니다.
- 다시 행렬을 순회하며 어떤 원소가 '행의 최솟값'과 '열의 최댓값' 조건을 동시에 만족하는지 확인하고, 만족한다면 결과 배열에 추가합니다.
이 방식의 시간 복잡도는 O(M×N), 공간 복잡도는 O(M+N)으로 매우 효율적입니다.
구현 코드
const arr = [
[3,7,8],
[9,11,13],
[15,16,17]
];
const luckyNumbers = (arr, res = []) => {
let M = arr.length, N = arr[0].length;
let min = Array(M).fill(Infinity);
let max = Array(N).fill(-Infinity);
// 각 행의 최솟값과 각 열의 최댓값 계산
for (let i = 0; i < M; ++i)
for (let j = 0; j < N; ++j)
min[i] = Math.min(min[i], arr[i][j]),
max[j] = Math.max(max[j], arr[i][j]);
// 행의 최솟값이면서 열의 최댓값인 원소 찾기
for (let i = 0; i < M; ++i)
for (let j = 0; j < N; ++j)
if (min[i] === max[j])
res.push(arr[i][j]);
return res;
};
console.log(luckyNumbers(arr));코드 설명
코드의 핵심 흐름은 다음과 같습니다.
M에는 행의 개수,N에는 열의 개수를 저장합니다.min배열은 각 행의 최솟값을,max배열은 각 열의 최댓값을 담습니다.- 첫 번째 중첩 반복문에서 행렬 전체를 한 번만 순회하면서 두 배열을 동시에 갱신합니다.
- 두 번째 중첩 반복문에서
min[i]와max[j]가 같은 지점을 찾으면, 그 위치의 원소가 바로 행운의 숫자이므로 결과 배열에 넣습니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
[15]