BOJ 1225 - 이상한 곱셈

문제

두 자연수 A, B가 주어질 때, A의 각 자릿수와 B의 각 자릿수를 모두 곱하여 더한 값을 구하라. 예를 들어 A=123, B=45이면 1*4 + 1*5 + 2*4 + 2*5 + 3*4 + 3*5 = 54이다.

입력

A와 B가 공백으로 구분되어 주어진다 (각각 10,000자리 이하).

출력

이상한 곱셈의 결과를 출력한다.

예제

입력	출력
`123 45`	`54`

풀이

각 수의 자릿수별 합을 미리 구한 뒤, 숫자별 합끼리 곱하여 최적화한다.

A의 각 자릿수를 숫자별(0~9)로 분류하여 합을 저장한다 (예: 자릿수 2가 3번 나오면 arr[0][2] = 6)
B도 동일하게 처리한다
A의 숫자별 합과 B의 숫자별 합을 교차 곱하여 전체 합을 구한다

핵심 아이디어: A의 자릿수 합 * B의 자릿수 합 = 모든 자릿수 쌍의 곱의 합이므로, O(N+M) 전처리 후 O(81) 곱셈으로 해결한다.

코드

package day699;
 
import java.io.*;
import java.util.*;
 
public class Day678BOJ1225이상한곱셈 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    long ans = 0L;
 
    String input = br.readLine();
    StringTokenizer tokenizer = new StringTokenizer(input, " ");
    int[][] arr = new int[2][10];
 
    for (char c : tokenizer.nextToken().toCharArray()) {
      int tmp = c - '0';
      arr[0][tmp] += tmp;
    }
 
    for (char c : tokenizer.nextToken().toCharArray()) {
      int tmp = c - '0';
      arr[1][tmp] += tmp;
    }
 
    for (int i = 1; i < 10; i++) {
      for (int j = 1; j < 10; j++) {
        ans += (long) arr[0][i] * arr[1][j];
      }
    }
    System.out.println(ans);
  }
}

복잡도

시간: O(N + M) — N, M은 각 수의 자릿수
공간: O(1) — 크기 10 고정 배열 2개

문제