문제: https://school.programmers.co.kr/learn/courses/30/lessons/161990
바탕화면에 있는 모든 파일('#')을 포함하는 가장 작은 직사각형을 찾는 문제
문제분석
- 바탕화면은 격자 형태이며, 각 칸은 '.'(빈 칸) 또는 '#'(파일)로 표시
- 모든 파일을 한 번에 선택하기 위한 최소 크기의 드래그 영역을 찾아야 한다
- 드래그 영역은 시작점 (lux, luy)와 끝점 (rdx, rdy)로 정의
문제 접근방법
- 모든 파일 위치를 확인하며 가장 작은 x, y 좌표와 가장 큰 x, y 좌표를 찾아야 함
- 가장 작은 좌표 → 드래그 시작점 S(lux, luy)
- 가장 큰 좌표+1 → 드래그 끝점 E(rdx, rdy)
- ⚠️ 끝점은 파일 위치보다 1 더 크게 설정해야 함 why? 파일을 완전히 포함하기 위해
- 드래그는 격자점을 기준인데, 파일은 격자 칸에 있음
- 파일이 있는 칸을 완전히 포함하려면 그 칸의 오른쪽 아래 격자점까지 드래그해야 함
내 코드
function solution(wallpaper) {
// 초기값 설정 (최소값은 가능한 최대로, 최대값은 가능한 최소로 설정)
let lux = wallpaper.length;
let luy = wallpaper[0].length;
let rdx = 0;
let rdy = 0;
// 모든 파일 위치 확인
for (let i = 0; i < wallpaper.length; i++) {
for (let j = 0; j < wallpaper[i].length; j++) {
if (wallpaper[i][j] === '#') {
// 파일을 발견하면 시작점과 끝점 좌표 업데이트
lux = Math.min(lux, i);
luy = Math.min(luy, j);
rdx = Math.max(rdx, i);
rdy = Math.max(rdy, j);
}
}
}
// 드래그 끝점은 파일 위치보다 1 더 크게 설정해야 함
return [lux, luy, rdx + 1, rdy + 1];
}내 코드 성능
메모리: 33.6 MB, 시간: 0.54 ms
개선된 코드
참고: deun블로그
function solution(wallpaper) {
let lux = wallpaper.length;
let luy = wallpaper[0].length;
let rdx = 0;
let rdy = 0;
for (let i = 0; i < wallpaper.length; i++) {
if (!wallpaper[i].includes('#')) continue; // ✅
lux = Math.min(lux, i);
rdx = Math.max(rdx, i + 1);
luy = Math.min(luy, wallpaper[i].indexOf('#')); // ✅
rdy = Math.max(rdy, wallpaper[i].lastIndexOf('#') + 1); // ✅
}
return [lux, luy, rdx, rdy];
}- 중첩된 반복문 제거 후 내장 메서드(
indexOf,lastIndexOf)를 활용- 하나의 반복문으로 모든 계산을 수행
- 각 행마다 최소/최대 인덱스를 바로 찾아 처리
- 파일이 없는 행(
if (!wallpaper[i].includes('#')) continue;)은 빠르게 건너 뜀 - 성능 개선
- 메모리: 33.6 MB → 33.4 MB,
- 시간: 0.54 ms → 0.23 ms
indexOf(), lastIndexOf() 리뷰하기
indexOf() 메서드
배열이나 문자열에서 특정 요소나 문자의 첫 번째 등장 위치(인덱스)를 찾아 반환
찾는 요소가 없으면 -1을 반환
array.indexOf(searchElement, [fromIndex])
string.indexOf(searchValue, [fromIndex])searchElement/searchValue: 찾을 요소 또는 문자열
fromIndex (선택적): 검색을 시작할 인덱스 (안 써주면 기본값 0)
사용 예) 특정 문자 이후의 내용 추출 - URL에서 쿼리 파라미터 추출
const url = 'https://example.com/search?query=javascript&limit=10';
const queryStartIndex = url.indexOf('?');
if (queryStartIndex !== -1) {
const queryString = url.substring(queryStartIndex + 1);
console.log('쿼리 문자열:', queryString); // 'query=javascript&limit=10'
}lastIndexOf() 메서드
배열이나 문자열에서 특정 요소나 문자의 마지막 등장 위치(인덱스)를 찾아 반환
찾는 요소가 없으면 -1을 반환
array.lastIndexOf(searchElement, [fromIndex])
string.lastIndexOf(searchValue, [fromIndex])searchElement/searchValue: 찾을 요소 또는 문자열
fromIndex (선택적): 역방향 검색을 시작할 인덱스 (기본값: array.length-1 또는 string.length-1)
사용 예 1) 파일 경로에서 파일명 추출하기
const filePath = '/users/documents/projects/report.pdf';
const lastSlashIndex = filePath.lastIndexOf('/');
const fileName = filePath.substring(lastSlashIndex + 1);
console.log('파일명:', fileName); // 'report.pdf'사용 예 2) 중복 요소 중 마지막 위치 찾기
// 배열에서 중복된 요소의 마지막 위치 찾기
const numbers = [2, 5, 9, 2, 7, 5, 3, 5];
const lastFiveIndex = numbers.lastIndexOf(5); // 7 반환
console.log('마지막 5의 위치:', lastFiveIndex);
// 특정 위치 이전의 마지막 등장 위치 찾기
const previousFiveIndex = numbers.lastIndexOf(5, 6); // 5 반환
console.log('인덱스 6 이전의 마지막 5 위치:', previousFiveIndex);실제 사용 범위
- 문자열 처리 작업 단순화:
- URL 파싱
- 파일 경로 처리
- 이메일 검증
- 텍스트 분석
- 데이터 검증과 처리:
- 입력값 유효성 검사
- 데이터 추출 및 변환
참고
https://bedecked-operation-4d1.notion.site/99-3-TIL-1c9eb405261e80f2b3b8e14bf17779e9
