[백준] 25418 정수 a를 k로 만들기 Java

코딩테스트 준비할 때 자잘한 처리에 도움이 될 것 같아서 남기는 포스팅이다. 어렵지 않은 문제로, 알고리즘을 공부한 사람들이라면 BFS로의 접근을 쉽게 떠올릴 수 있는 문제였다. 

 

https://www.acmicpc.net/problem/25418

 

문제

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

 

입력

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

제한

1 ≤ A < K ≤ 1,000,000

 

예제 입력

1111 997651

 

예제 출력

850

 

나 또한 처음엔 이 문제를 보자마자 BFS를 떠올렸고, 코드를 다음과 같이 작성했다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] visited = new int[K*2+1];

        Queue<Integer> q = new LinkedList<>();
        visited[A] = 1;
        q.offer(A);

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == K) {
                System.out.println(visited[cur]-1);
                break;
            }

            // 정수 A에 1을 더한다
            if (visited[cur+1] == 0 && cur+1 <= K) {
                visited[cur+1] = visited[cur] + 1;
                q.offer(cur+1);
            }
            // 정수 A에 2를 곱한다
            if (visited[cur*2] == 0 && cur*2 <= K) {
                visited[cur*2] = visited[cur] + 1;
                q.offer(cur*2);
            }

        }

    }

}

 

제한으로 A < K 라는 조건이 있었고, A가 K-1이 되는 최악의 경우를 생각해 연산 횟수와 방문 여부를 통합 관리하는 visited 배열의 크기는 K*2+1로 설정해주었다. 

 

 

 

 

 

무난하게 맞췄으나, 이 코드를 개선해보고자 했다. K 이상의 숫자들에 대해서도 큐에 넣어 확인하는 것이 시간, 메모리적으로 비효율적이라고 생각했다. 나는 시간과 메모리 비용이 상호 보완적 관계에 있다고 생각하는데, 이 코드는 메모리적으로 보나 시간적으로 보나 개선될 여지가 있었다. 그래서 다시 작성한 코드이다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj25418 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] visited = new int[K+1];

        Queue<Integer> q = new LinkedList<>();
        visited[K] = 1;
        q.offer(K);

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == A) {
                System.out.println(visited[cur]-1);
                break;
            }

            if (visited[cur-1] == 0 && cur-1 >= A) {
                visited[cur-1] = visited[cur] + 1;
                q.offer(cur-1);
            }

            if (visited[cur/2] == 0 && cur%2 == 0 && cur/2 >= A) {
                visited[cur/2] = visited[cur] + 1;
                q.offer(cur/2);
            }

        }

    }

}

 

주어지는 연산 자체가 더하기와 곱하기이고 A와 K가 둘 다 양수라는 조건이 있었으니, A -> K로 가는 과정이 단방향이라고 생각했다. 이를 역으로 생각해보면 K라는 숫자에서 반대 연산을 하게 되어도 K -> A로 가는 과정이 단방향이 되는 것이다. 그렇다면 배열의 크기를 K 이상으로 잡을 필요가 없어진다.

 

A -> K가 되지 않는 경우는 주어지지 않는 문제이므로 K -> A가 되는 과정에서 배열 인덱스가 음수를 가리키게 되는 상황도 없을 것이라고 판단해서, K -> A로 연산을 해 나가도록 구현해보았다. (사실 부트캠프에서 알고리즘 문제를 풀 때 페어 오빠가 친절하게 알려주셔서 생각해뒀던 아이디어인데 이렇게 써먹게 되었다... ㅎㅎ감사합니다)

 

int[] visited = new int[K+1];

 

 

개선점을 살펴보면, visited 배열의 크기가 절반으로 줄었다. 이를 통해 메모리 비용이 줄어들 것임을 예측할 수 있다.

 

if (visited[cur-1] == 0 && cur-1 >= A) {
    visited[cur-1] = visited[cur] + 1;
    q.offer(cur-1);
}

if (visited[cur/2] == 0 && cur%2 == 0 && cur/2 >= A) {
    visited[cur/2] = visited[cur] + 1;
    q.offer(cur/2);
}

 

while 문의 내용을 보면 더하기, 곱하기를 빼기, 나누기로 변환해 작성한 것을 알 수 있다. 추가된 것은 나누기 연산을 할 때 cur (현재 숫자) 값이 짝수인 지를 확인하는 부분인데, 홀수를 2로 나눠서 연산 오류가 발생하는 것을 막아준 것이다. Java 에서는 15 / 2 의 연산이 7로 처리되기 때문에 이 부분을 고려해줬다.

 

 

 

제출 결과, 이전 코드에 비해 메모리 사용량은 53712 KB -> 25276 KB로 줄었고, 시간 또한 136 ms -> 112 ms로 줄어든 것을 볼 수 있다.