[ 𝗽𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗲𝗿𝘀 ] 택배상자꺼내기 - 시뮬레이션, 수학 | JavaScript

🎯 문제 설명

🧩 프로그래머스 Lv.1 - 택배상자꺼내기

1 ~ n의 번호가 있는 택배 상자가 창고에 있습니다. 당신은 택배 상자들을 다음과 같이 정리했습니다.

왼쪽에서 오른쪽으로 가면서 1번 상자부터 번호 순서대로 택배 상자를 한 개씩 놓습니다. 가로로 택배 상자를 w개 놓았다면 이번에는 오른쪽에서 왼쪽으로 가면서 그 위층에 택배 상자를 한 개씩 놓습니다. 그 층에 상자를 w개 놓아 가장 왼쪽으로 돌아왔다면 또다시 왼쪽에서 오른쪽으로 가면서 그 위층에 상자를 놓습니다. 이러한 방식으로 n개의 택배 상자를 모두 놓을 때까지 한 층에 w개씩 상자를 쌓습니다.

• 위 그림은 w = 6일 때 택배 상자 22개를 쌓은 예시입니다.

다음 날 손님은 자신의 택배를 찾으러 창고에 왔습니다. 당신은 손님이 자신의 택배 상자 번호를 말하면 해당 택배 상자를 꺼내줍니다. 택배 상자 A를 꺼내려면 먼저 A 위에 있는 다른 모든 상자를 꺼내야 A를 꺼낼 수 있습니다. 예를 들어, 위 그림에서 8번 상자를 꺼내려면 먼저 20번, 17번 상자를 꺼내야 합니다.

당신은 꺼내려는 상자 번호가 주어졌을 때, 꺼내려는 상자를 포함해 총 몇 개의 택배 상자를 꺼내야 하는지 알고 싶습니다.

이때, 꺼내야 하는 상자의 총개수를 return 하도록 solution 함수를 완성해 주세요.

🥅 제한 사항

• 2 ≤ 택배 상자의 개수 n ≤ 100
• 1 ≤ 가로로 놓는 상자의 개수 w ≤ 10
• 1 ≤ 꺼내려는 택배 상자의 번호 num ≤ n

📍 입출력 예

n	w	num	result
22	6	8	3
13	3	6	4

👩🏻‍💻 문제풀이

시뮬레이션

처음에는, 문제에 적힌 그대로 순서대로 풀었습니다.

boxs라는 배열을 만들어서 상자를 차례대로 정렬했습니다.

const h = Math.ceil(n / w);
const boxs = Array.from({ length: h }, () => Array(w).fill(0));

for(let i = 0; i < h; i++){
	for(let j = 0; j < w; j++){
		if(i % 2 === 0){
			// 짝수번째 줄이라면 -> 오른쪽 방향으로 숫자를 나열
			boxs[i][j] = i * w + j + 1
		} else {
			// 홀수번째 줄이라면 <- 왼쪽 방향으로 숫자를 나열
			boxs[i][j] = i * w + (w - j)
		}
	}
}

그럼 아래와 같이 상자가 배치됩니다.

그런데, n을 넘어서까지 배치가 되므로, 조건을 추가해주었습니다.

for(let i = 0; i < h; i++){
	for(let j = 0; j < w; j++){
		if(i % 2 === 0){
			let curN = i * w + j + 1
			if(curN <= n) boxs[i][j] = curN;
		} else {
			let curN = i * w + (w - j)
			if(curN <= n) boxs[i][j] = curN;
		}
	}
}

이제 n을 넘어서는 숫자는 배치되지 않습니다.

이제 num의 행, 열을 찾아야합니다. 박스를 배치하면서 한번에 찾으면 좋을 것 같습니다. 반복문 내에 조건을 추가해서 변수에 저장해주겠습니다.

let row;
let col;

for(let i = 0; i < h; i++){
	for(let j = 0; j < w; j++){
		if(i % 2 === 0){
			let curN = i * w + j + 1
			if(curN <= n) boxs[i][j] = curN;
			if(curN === num) {
				row = i;
				col = j;
			}
		} else {
			let curN = i * w + (w - j)
			if(curN <= n) boxs[i][j] = curN;
			if(curN === num) {
				row = i;
				col = j;
			}
		}
	}
}

이제 필요한 조건을 모두 갖추었습니다. boxs 배열을 돌면서, 뺴야할 상자를 세어줍니다.

let count = 0;
for(let r = row; r < h; r++){
	if(boxs[r][col] !== 0) count++;
}

아래 사진의 빨간색 부분만 탐색하며 count를 셉니다. 그리고 count를 return 해주면 됩니다.

수학적 규칙 찾기

하지만, 위 방식은 메모리도 많이 쓰고 복잡합니다. 사실 우리는 num의 위치를 찾아서 row, col 을 알게되면 빨간색 부분만 탐색할 수 있습니다. 굳이 boxs 배열을 만들 필요가 없습니다.

일단 row는 쉽게 구할 수 있습니다. num - 1로 인덱스 번호를 기준으로 해서 w로 나누면 몇번째 줄인지 알 수 있습니다.

row를 구했다면, 이를 가지고 col 도 구할 수 있습니다. row가 짝수라면 오른쪽으로 숫자가 나열되고, 홀수라면 왼쪽으로 숫자가 나열됩니다. 이에 맞춰서 구할 수 있습니다.

let row = Math.floor((num - 1) / w);
let col;
if(row % 2 === 0){
	col = (num - 1) % w
} else {
	col = w - 1 - (num - 1) % w
}

이제 row 이상의 줄에서 해당 칸의 숫자를 n과 비교하여 작거나 같으면 count를 올리고, n보다 크다면 상자가 없으므로 더하지 않으면 됩니다.

let count = 0;
for(let i = row; i < h; i++){
	if(i % 2 === 0 && (i * w + col) <= n){
		count++
	} else if(i % 2 !== 0 && (i * w + (w - col)) <= n){
		count++
	}
}

이렇게 하면 메모리를 크게 절약하고 불필요한 연산을 줄일 수 있습니다.