[코딩테스트] 백준 1850 자바

백준 1850

백준 1850 문제

해당 문제는 예제 입력 3과 같이 입력값이 크면 단순한 방법으로 최대 공약수를 찾기 어렵다. 하지만 예제를 잘 보면 규칙을 찾을 수 있는데, a와 b의 자릿수 차이만큼 1를 출력해주면 정답이다.

일반적인 출력을 사용할 경우에 시간 초과가 발생할 수 있으므로 BufferedWriter를 사용하겠다.

import java.util.*;
import java.io.*;

public class Boj1850 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken()); // 1번째 수
        long b = Long.parseLong(st.nextToken()); // 2번째 수
        long result = gcd(a, b); // 결괏값

        // 결괏값만큼 1을 반복해 출력(출력 횟수가 많기 때문에 BufferedWriter 사용)
        while (result > 0) {
            bw.write("1");
            result--;
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 최대 공약수를 구하는 메서드 구현
    private static long gcd(long a, long b) {
        if (b == 0) { // b가 0이면 a가 최대 공약수
            return a;
        } else {
            return gcd(b, a % b); // 재귀 함수 형태로 최대 공약수 찾기
        }
    }
}

풀이

1. 1번째 수를 입력 받아 a에 저장한다.
2. 2번째 수를 입력 받아 b에 저장한다.
3. 최대 공약수를 구하는 메서드 gcd(a, b)를 통해 결괏값을 반환 받는다.
   3-1. gcd() 메서드는 최대 공약수를 구하는 메서드로 매개변수 b가 0이면 더 이상 나눌 수 없기 때문에 a가 최대 공약수가 따라서 a를 반환한다.
   3-2. b가 0이 아니면 더 나눌수 있기 때문에 gcd(b, a % b)를 재귀 호출하여 최대 공약수를 구한다.
4. 반환 받은 결괏값 result만큼 BufferedWriter를 통해 1를 출력해주면 된다.