제15회 블루브릿지컵(Lanqiao Cup) 실전 모의고사 2차 Java 주요 문항 해설

제15회 블루브릿지컵(Lanqiao Cup) Java 부문 2차 모의고사의 주요 문제들을 분석하고, 효율적인 알고리즘을 적용한 코드 구현 사례를 소개합니다. 각 문제는 기초적인 연산부터 탐색(BFS), 수학적 사고력을 요구하는 알고리즘까지 다양한 영역을 다룹니다.

거듭제곱의 나머지 연산

2023회 반복하며 숫자를 2배씩 늘리고, 그 과정에서 하위 3자리만 유지하는 문제입니다. 모듈로 연산의 성질을 이용하여 숫자가 지나치게 커지는 것을 방지합니다.

public class PowerModulo {
    public static void main(String[] args) {
        long currentVal = 1;
        for (int step = 1; step <= 2023; step++) {
            currentVal = (currentVal * 2) % 1000;
        }
        System.out.println("최종 결과: " + currentVal);
    }
}

진법별 자릿수 합 비교

10진수 숫자를 2진수와 8진수로 변환했을 때, 각 진법에서의 자릿수 합이 동일한 23번째 숫자를 찾는 문제입니다.

public class DigitSumComparison {
    public static void main(String[] args) {
        int matchCount = 0;
        for (int num = 1; num <= 10000; num++) {
            if (getDigitSum(num, 2) == getDigitSum(num, 8)) {
                matchCount++;
                if (matchCount == 23) {
                    System.out.println("23번째 숫자: " + num);
                    break;
                }
            }
        }
    }

    private static int getDigitSum(int n, int base) {
        int sum = 0;
        while (n > 0) {
            sum += n % base;
            n /= base;
        }
        return sum;
    }
}

최대 약수 개수 탐색

주어진 숫자 리스트 중 약수의 개수가 가장 많은 숫자를 찾아야 합니다. 약수 탐색 시 반복 범위를 조절하여 효율을 높일 수 있습니다.

public class MaxDivisors {
    public static void main(String[] args) {
        String data = "393353 901440 123481 850930 423154 240461 373746 232926 396677 486579 744860 468782 941389 777714 992588 343292 385198 876426 483857 241899 544851 647930 772403 109929 882745 372491 877710 340000 659788 658675 296521 491295 609764 718967 842000 670302";
        String[] tokens = data.split(" ");
        int bestNumber = 0;
        int maxCount = -1;

        for (String token : tokens) {
            int num = Integer.parseInt(token);
            int currentDivisors = countDivisors(num);
            if (currentDivisors > maxCount) {
                maxCount = currentDivisors;
                bestNumber = num;
            }
        }
        System.out.println("최대 약수 개수 보유 숫자: " + bestNumber);
    }

    private static int countDivisors(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) count++;
        }
        return count;
    }
}

6자리 정수 순환 왼쪽 이동

입력받은 6자리 정수의 첫 번째 자릿수를 맨 뒤로 보내는 문제입니다. 문자열 인덱싱을 활용하면 간단히 해결할 수 있습니다.

import java.util.Scanner;

public class CyclicShift {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        if (input.length() == 6) {
            String shifted = input.substring(1) + input.charAt(0);
            System.out.println(shifted);
        }
    }
}

문자열 내 마지막 모음 찾기

주어진 문자열에서 마지막으로 나타나는 모음(a, e, i, o, u)을 출력합니다. 문자열의 뒤에서부터 탐색하면 탐색 시간을 단축할 수 있습니다.

import java.util.Scanner;

public class LastVowel {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String word = sc.next();
        char result = ' ';
        for (int i = word.length() - 1; i >= 0; i--) {
            char c = word.charAt(i);
            if ("aeiou".indexOf(c) != -1) {
                result = c;
                break;
            }
        }
        System.out.println(result);
    }
}

자릿수 곱 변환 프로세스

숫자의 모든 비제로(non-zero) 자릿수를 곱하는 과정을 숫자가 10보다 작아질 때까지 반복하고, 각 단계의 결과를 출력합니다.

import java.util.Scanner;

public class DigitProductProcess {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        
        while (n >= 10) {
            n = getNextProduct(n);
            System.out.println(n);
        }
    }

    private static long getNextProduct(long num) {
        long product = 1;
        String s = String.valueOf(num);
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit != 0) {
                product *= digit;
            }
        }
        return product;
    }
}

격자 내 최대공약수(GCD) 기반 이동 탐색

이웃한 격자 간의 GCD가 1보다 큰 경우 이동이 가능할 때, 특정 시작점에서 도달 가능한 모든 칸의 수를 BFS로 구합니다.

import java.util.*;

public class GridGcdPath {
    static int n, m;
    static long[][] board;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        board = new long[n + 1][m + 1];
        visited = new boolean[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                board[i][j] = sc.nextLong();
            }
        }
        int startR = sc.nextInt();
        int startC = sc.nextInt();

        System.out.println(bfs(startR, startC));
    }

    static long getGcd(long a, long b) {
        while (b != 0) {
            a %= b;
            long temp = a; a = b; b = temp;
        }
        return a;
    }

    static int bfs(int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r, c});
        visited[r][c] = true;
        int count = 1;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            for (int i = 0; i < 4; i++) {
                int nr = curr[0] + dr[i];
                int nc = curr[1] + dc[i];

                if (nr >= 1 && nr <= n && nc >= 1 && nc <= m && !visited[nr][nc]) {
                    if (getGcd(board[curr[0]][curr[1]], board[nr][nc]) > 1) {
                        visited[nr][nc] = true;
                        count++;
                        q.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return count;
    }
}

고정 길이 구간 최대 합

길이가 n인 수열에서 연속된 k개 요소의 합 중 최대값을 찾는 문제입니다. 슬라이딩 윈도우 기법을 사용하면 O(n)의 시간 복잡도로 해결 가능합니다.

import java.util.Scanner;

public class MaxSubarraySum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextLong();
        }

        long currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }

        long maxSum = currentSum;
        for (int i = k; i < n; i++) {
            currentSum = currentSum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, currentSum);
        }
        System.out.println(maxSum);
    }
}

태그: java algorithm bfs gcd sliding window

11월 8일 00:01에 게시됨