코딩테스트/SWEA

[SWEA] 4008번 - 숫자 만들기 풀이 및 코드 분석 (Java)

현걸 2025. 2. 27. 13:03

문제 링크

1. 문제 분석

📌 문제 개요

  • 주어진 N개의 숫자 사이에 연산자(+,-,×,÷)를 넣어 다양한 수식을 만들 수 있다.
  • 연산자의 우선순위 없이 왼쪽에서 오른쪽으로 연산이 수행된다.
  • 연산자 카드를 적절히 배치하여, 최댓값과 최솟값의 차이를 구하는 문제이다.

🎯 요구사항

  1. 각 연산자 카드는 반드시 모두 사용해야 한다.
  2. 완성된 수식의 결과 중 최댓값과 최솟값을 찾고, 그 차이를 출력해야 한다.
  3. 나눗셈(÷) 연산은 몫만 취급(소수점 이하 버림)해야 한다.
  4. 숫자의 순서는 변경할 수 없다.
  5. 가능한 모든 연산자 조합을 탐색해야 한다.
  6. N의 최대 크기가 12이므로, 브루트포스(백트래킹)로 해결 가능하다.

2. 해결 방법

🔹 핵심 개념

이 문제는 연산자의 모든 가능한 조합을 탐색해야 하므로,
백트래킹(Brute Force) 알고리즘을 활용하여 해결할 수 있다.

🔑 해결 절차

  1. 입력값 처리
    • N → 숫자의 개수 (3 ≤ N ≤ 12)
    • nums[] → 수식에 들어갈 숫자 배열
    • cal[4] → 연산자의 개수 (+, -, ×, ÷ 순서)
    • min, max → 가능한 최댓값과 최솟값을 저장
  2. 백트래킹을 활용한 연산자 배치 탐색
    • bt(현재 위치, 현재까지의 연산 결과) 함수 실행
    • 연산자가 남아있는 경우, 각각을 사용해 연산을 수행하고 다음 단계로 진행
    • 연산이 끝난 경우, 최댓값과 최솟값을 갱신
  3. 최댓값과 최솟값의 차이 출력
    • max - min을 구해서 출력

3. 코드 구현

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

public class Solution {
    static int min, max, N;
    static int[] cal = new int[4]; // +, -, *, /
    static int[] nums;

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

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");

            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;

            N = Integer.parseInt(br.readLine()); // 숫자 개수
            nums = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++) {
                cal[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }

            // 백트래킹 시작
            backtracking(1, nums[0]);

            sb.append(max - min).append("\n");
        }

        System.out.println(sb);
    }

    // 백트래킹을 활용한 최댓값 & 최솟값 탐색
    private static void backtracking(int n, int sum) {
        if (n == N) {
            min = Math.min(min, sum);
            max = Math.max(max, sum);
            return;
        }

        for (int d = 0; d < 4; d++) {
            if (cal[d] == 0) continue; // 사용 가능한 연산자가 없으면 건너뜀

            cal[d]--; // 연산자 사용

            switch (d) {
                case 0: backtracking(n + 1, sum + nums[n]); break; // +
                case 1: backtracking(n + 1, sum - nums[n]); break; // -
                case 2: backtracking(n + 1, sum * nums[n]); break; // ×
                case 3: backtracking(n + 1, sum / nums[n]); break; // ÷ (몫만 취급)
            }

            cal[d]++; // 연산자 복구 (백트래킹)
        }
    }
}

4. 코드 분석

🔹 주요 알고리즘

  1. 백트래킹을 활용한 완전 탐색
    • 연산자가 남아있는 경우 모든 경우의 수를 탐색
    • 현재까지의 연산 결과를 sum으로 유지하면서 재귀적으로 진행
  2. 최댓값과 최솟값 갱신
    • n == N이면 최댓값과 최솟값을 갱신
    • 최댓값: max = Math.max(max, sum)
    • 최솟값: min = Math.min(min, sum)
  3. 연산자 사용 & 복구 (백트래킹)
    • 연산자를 사용하면 cal[d]--
    • 연산 후에는 다시 cal[d]++로 원래 상태로 되돌림

🔹 시간 복잡도 분석

  • 최대 연산 횟수: N = 12, 연산자는 N-1 = 11개
  • 각 단계에서 4가지 연산자 선택 가능 → O(4^(N-1))
  • 최악의 경우 (N=12)
    • O(4^11) ≈ 4,194,304 → 가능한 범위
    • 브루트포스지만 N이 작아 백트래킹으로 해결 가능

5. 개선할 점 및 대체 방법

✅ 개선할 점

  1. 메모이제이션 활용 가능
    • 이미 탐색한 (n, sum)을 Map에 저장하면 불필요한 연산을 줄일 수 있다.
    • 하지만 백트래킹으로도 충분히 빠르게 해결 가능하므로 불필요하다.
  2. DP를 활용한 방법
    • DP 배열을 활용하면 중복 계산을 방지할 수 있다.
    • 하지만 경우의 수가 많아 DP 적용이 어렵고, 백트래킹이 더 적합하다.

🔄 대체 방법

  1. 비트마스킹을 활용한 연산자 배치
    • bitmask를 사용하여 연산자의 사용 여부를 관리하면 탐색 속도를 개선할 수 있다.
    • 하지만 이 문제에서는 필요하지 않다.
  2. BFS(너비 우선 탐색)
    • 모든 경우의 수를 BFS로 탐색할 수도 있지만, 백트래킹이 더 직관적이다.
저작자표시 비영리 변경금지 (새창열림)