난이도 : Level 1
문제 출처
문제 파악
위 사진처럼 여러 개의 파일을 한 번에 드래그해서 삭제하려고 한다.
여기서 삭제는 선택이라고 이해해도 무방하다.
파일은 2차원 좌표 위에 존재한다.
이때 파일들이 모두 포함되도록 하면서, 최대한 효율적으로 드래그 영역이 딱 맞게 잡히는 좌표를 구해야 한다.
반환 형식은 다음과 같다.
[왼쪽 위의 x좌표, 왼쪽 위의 y좌표, 오른쪽 아래의 x좌표, 오른쪽 아래의 y좌표]
해결 아이디어
보드인 wallpaper의 길이가 50 이하이므로, 이중 for문을 통한 완전탐색을 해도 무방하다고 생각했다.
2중 for문을 돌며 파일을 의미하는 문자열 "#"을 만나면 해당 위치를 따로 배열에 저장한다.
그 후 #의 위치를 저장해둔 배열을 다시 탐색하며 다음 값을 구한다.
- 가장 작은 x좌표
- 가장 작은 y좌표
- 가장 큰 x좌표
- 가장 큰 y좌표
그리고 오른쪽 아래 좌표는 실제 파일 위치보다 한 칸 바깥을 의미하므로, 최댓값에는 각각 +1을 해주었다.
정답 코드 - JavaScript reduce 풀이
// 최소한의 이동거리를 갖는 드래그의 시작점과 끝점을 담은 정수 배열을 return
// [".#...",
// "..#..",
// "...#."]
// #의 위치를 파악 후
// 가장 왼쪽 위 #, 가장 오른쪽 아래 # 찾고
// 왼쪽 위, 오른쪽 아래 좌표 return
function solution(wallpaper) {
let pos = [];
// 2중 for문으로 # 좌표 리스트에 push
for (let i = 0; i < wallpaper.length; i++) {
for (let j = 0; j < wallpaper[0].length; j++) {
if (wallpaper[i][j] === "#") {
pos.push([i, j]);
}
}
}
// pos = [[0, 1], [1, 2], [2, 3]]
// 가장 작은 i, j 찾고, 가장 큰 i, j 찾아서 +1씩 처리
// 배열을 순회하며 하나의 값으로 줄이기 -> reduce 배열 메서드
const temp = pos.reduce((acc, cur) => {
const [minI, minJ, maxI, maxJ] = acc;
const [i, j] = cur;
return [
Math.min(minI, i),
Math.min(minJ, j),
Math.max(maxI, i),
Math.max(maxJ, j),
];
}, [Infinity, Infinity, -Infinity, -Infinity]);
// 우하단 +1 후처리
let result = [...temp];
result[2] += 1;
result[3] += 1;
return result;
}reduce를 떠올린 이유
특정 배열에 여러 원소가 있고, 그 원소들을 하나의 값으로 줄여야 할 때는 Array.prototype.reduce()를 떠올릴 수 있다.
위 문제에서도 # 좌표 리스트에서 최소값과 최댓값을 찾아야 하므로, reduce를 활용해 비교적 깔끔한 코드를 구현할 수 있었다.
또한 JavaScript에는 Infinity라는 숫자 타입의 특수한 값이 존재한다.
Infinity는 양의 무한대를 의미하고, -Infinity는 음의 무한대를 의미한다.
따라서 최솟값과 최댓값을 초기화할 때 다음과 같이 사용할 수 있다.
[Infinity, Infinity, -Infinity, -Infinity]의미는 다음과 같다.
[minI, minJ, maxI, maxJ]최솟값은 매우 큰 값에서 시작하고, 최댓값은 매우 작은 값에서 시작해야 첫 번째 실제 좌표와 비교했을 때 자연스럽게 값이 갱신된다.
reduce를 쓰지 않는다면?
사실 JavaScript에서도 # 위치 배열을 따로 만들고 reduce를 사용하는 방식 말고,
2중 for문을 돌면서 바로 최솟값과 최댓값을 갱신해도 깔끔하게 풀 수 있다.
function solution(wallpaper) {
let minI = Infinity;
let minJ = Infinity;
let maxI = -Infinity;
let maxJ = -Infinity;
for (let i = 0; i < wallpaper.length; i++) {
for (let j = 0; j < wallpaper[0].length; j++) {
if (wallpaper[i][j] === "#") {
minI = Math.min(minI, i);
minJ = Math.min(minJ, j);
maxI = Math.max(maxI, i);
maxJ = Math.max(maxJ, j);
}
}
}
return [minI, minJ, maxI + 1, maxJ + 1];
}이 방식은 pos 배열을 따로 만들지 않기 때문에 메모리를 조금 더 아낄 수 있고, 흐름도 직관적이다.
Python - for문 풀이
def solution(wallpaper):
pos = []
# 2중 for문으로 # 좌표 모으기
for i in range(len(wallpaper)):
for j in range(len(wallpaper[0])):
if wallpaper[i][j] == "#":
pos.append([i, j])
# 초기값
min_i = float("inf")
min_j = float("inf")
max_i = float("-inf")
max_j = float("-inf")
# 가장 작은 i, j / 가장 큰 i, j 찾기
for i, j in pos:
min_i = min(min_i, i)
min_j = min(min_j, j)
max_i = max(max_i, i)
max_j = max(max_j, j)
# 우하단 좌표는 +1
return [min_i, min_j, max_i + 1, max_j + 1]Python - reduce 풀이
from functools import reduce
def solution(wallpaper):
pos = []
for i in range(len(wallpaper)):
for j in range(len(wallpaper[0])):
if wallpaper[i][j] == "#":
pos.append([i, j])
temp = reduce(
lambda acc, cur: [
min(acc[0], cur[0]),
min(acc[1], cur[1]),
max(acc[2], cur[0]),
max(acc[3], cur[1]),
],
pos,
[float("inf"), float("inf"), float("-inf"), float("-inf")]
)
return [temp[0], temp[1], temp[2] + 1, temp[3] + 1]