숫자 변환하기

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

프로그래머스

 

1. 개요

큐에 (연산을 가했을 때의 숫자, 그 숫자에 도달하기 까지 필요한 연산 횟수)를 저장하고, 이를 순회하며 목표치에 도달한 경우가 있는 지 확인하는 것이 이 문제의 골자이다. 

 

2. 알고리즘 및 풀이

1) 변수 초기화

int ans = -1;
queue<vector<int>> que;	// 숫자, 그 숫자에 도달하기 까지의 연산 횟수를 저장
que.push({x, 0});	// 큐 초기화
set<int> visited;	// 봤던 숫자를 저장

 

숫자와 연산횟수를 자장하기 위한 큐, 방문한 숫자들을 기록하기 위한 set을 초기화 한다.

 

set은 기록한 숫자들을 확인할 때의 시간복잡도를 줄이기 위해 vector 대신 사용한다.

 

2) 큐 순회

while (!que.empty()) {
        vector<int> que_top = que.front();	// 맨 앞의 원소 가져오기
        que.pop();
        int cur = que_top[0];
        int cnt = que_top[1];
        
        if (y < cur || visited.count(cur) > 0) {	// 목표를 지나쳤거나, 이미 본 적이 있는 숫자면
            continue;	// 무시
        }
        visited.insert(cur);	// 현재 숫자를 확인했다고 표시
        if (cur == y) {	// 목표 도달
            ans = cnt;	// 답 설정
            break;	// 반복문 탈출
        }
        else {	// 도달하지 못했다면
            vector<int> candid = {cur*2, cur*3, cur+n};	
            
            for (int i = 0; i < 3; i++) {	// 3가지 경우 순회
                if (candid[i] <= y && visited.count(candid[i]) == 0) {	// 보는 숫자가 목표 이하이고, 방문한 적이 없다면
                    que.push({candid[i], cnt+1});	// 나중에 보기 위해, 큐에 저장
                }
            }
        }
    }

 

(1) 목표를 지나쳤거나, 이전에 본 적 있는 숫자인지 확인

목표치를 지나쳤거나, 이미 방문한 시점에서는 더 이상 볼 이유가 없으므로, 무시한다.

 

(2) 본 적이 있는 숫자로 기록

visited에 현재 숫자를 넣음으로써, 해당 숫자를 본 적이 있다고 표시한다.

 

(3) 목표에 도달했는 지 확인

답안은 여기까지 오는데 필요한 연산 횟수이다.

 

따라서 ans의 값을 cnt의 값으로 바꾸고, 반복문을 탈출한다.

 

(4) 목표에 도달하지 못했다면

3가지 연산을 수행하는 경우 별 값과 연산횟수를 계산하고, 이를 큐에 넣는다.

 

3. 전체 소스코드

// C++

#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int solution(int x, int y, int n) {
	// 1)
    int ans = -1;
    queue<vector<int>> que;
    que.push({x, 0});
    set<int> visited;
    
    // 2)
    while (!que.empty()) {
        vector<int> que_top = que.front();
        que.pop();
        int cur = que_top[0];
        int cnt = que_top[1];
        
        // (1)
        if (y < cur || visited.count(cur) > 0) {
            continue;
        }
        
        // (2)
        visited.insert(cur);
        
        // (3)
        if (cur == y) {
            ans = cnt;
            break;
        }
        
        // (4)
        else {
            vector<int> candid = {cur*2, cur*3, cur+n};
            
            for (int i = 0; i < 3; i++) {
                if (candid[i] <= y && visited.count(candid[i]) == 0) {
                    que.push({candid[i], cnt+1});
                }
            }
        }
    }
      
    return ans;
}

 

# Python3

from collections import deque


def solution(x, y, n):
	# 1)
    ans = -1
    que = deque()
    que.append((x, 0))
    visited = set()
    
    # 2)
    while que:
        cur, cnt = que.popleft()
        
        # (1)
        if y < cur or cur in visited:
            continue
        
        # (2)
        visited.add(cur)
        
        # (3)
        if cur == y:
            ans = cnt
            break
            
        # (4)
        else:
            for candid in (cur * 2, cur * 3, cur + n):
                if candid <= y and candid not in visited:
                    que.append((candid, cnt + 1))
                    
    return ans

 

채점 결과