문제

프로그래머스 숫자변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

1. 문제 분석

• 주어진 수식의 연산 우선순위를 조정하여 최대의 결과값을 찾는 것
• 목표는 가능한 모든 연산자 우선순위를 조합하여 결과를 계산하고, 그 중에서 최대값을 찾는 것이다.

2. 알고리즘 선택

• ‘x를 y로 변환하기 위해 필요한 최소 연산 횟수’ 부분에서 BFS으로 접근 판단

1차 풀이 - 시간초과

function solution(x: number, y: number, n: number) {
	const queue: [number, number][] = [];
	const visited = new Set();

	queue.push([x, 0]);
	visited.add(x);

	while (queue.length > 0) {
		const [x, count] = queue.shift()!;
		if (x === y) return count;

		const nextNumbers = [x + n, x * 2, x * 3];

		for (const num of nextNumbers) {
			if (visited.has(num) || num > y) continue;
			queue.push([num, count + 1]);
			visited.add(num);
		}
	}

	return -1;
}

• BFS 상향식 접근

2차 풀이

function solution(x: number, y: number, n: number) {
	const queue: [number, number][] = [];
	const visited = new Set();

	queue.push([y, 0]);
	visited.add(y);

	while (queue.length > 0) {
		const [current, count] = queue.shift()!;
		if (current === x) return count;

		const nextNumbers = [];
		if (current % 2 === 0) nextNumbers.push(current / 2);
		if (current % 3 === 0) nextNumbers.push(current / 3);
		nextNumbers.push(current - n);

		for (const num of nextNumbers) {
			if (visited.has(num) || num < x) continue;
			queue.push([num, count + 1]);
			visited.add(num);
		}
	}

	return -1;
}

• BFS 하향식 접근