[백준 27488] Sum of Two Numbers-Java

문제

문제 링크

문제 요약

• 자연수 𝑛 이 주어졌을 때, 다음 조건을 만족하는 두 개의 음이 아닌 정수 𝑥, 𝑦를 찾으라는 문제
  • x+y=n을 만족해야함
  • x의 각 자리 숫자의 합과 y의 각 자리 숫자의 합의 차이가 1 이하이어야 한다.
  • 이 조건을 만족하는 x와 y는 항상 존재

입출력 분석

입력

• 첫 번째 줄 : 테스트 케이스의 수 (1<t<=10,000)
• 이후 t개의 줄 : 각 줄에 자연수 n이 주어짐

출력

• 각 테스트 케이스에 대해, 조건을 만족하는 두 정수 x와 y를 출력
• 가능한 정답이 여러 개일 경우, 아무거나 출력

제한 사항

1. 제한 시간 : 1초
   • 일반적으로 1초 동안 약 1억 회(10^8) 의 연산을 수행할 수 있다고 가정
2. 메모리 제한 : 1024 MB
3. 입력 조건 :
   • 테스트 케이스 수 (t)
     • 1 <= t <= 10,000
     • 즉, 최대 10,000개의 테스트 케이스가 주어질 수 있음.
   • 각 테스트 케이스의 입력 (n)
     • 1 <= n <= 10^9
     • 각 테스트 케이스는 하나의 정수 n로 주어짐.
     • n은 최대 10^9의 값을 가질 수 있음.

설계

목표

1. s의 길이가 최대 100이고, 테스트 케이스가 최대 10,000개일 수 있으므로 O(n) 시간 복잡도로 설계해야 한다. (정수가 아닌 문자열 입력받음)
2. A와 B의 자리수 합이 최대한 균형을 이루도록 나눠야 한다. (모두 정한 규칙을 따르기 위해서)

자리수 나누기 로직

for (char ch : s.toCharArray()) {
    int x = ch - '0';
    int y = x;
    x /= 2;
    y -= x;

    if (L < R) {
        A = A * 10 + y;
        B = B * 10 + x;
        L += y;
        R += x;
    } else {
        A = A * 10 + x;
        B = B * 10 + y;
        L += x;
        R += y;
    }
}

• 자리 숫자를 2로 나누어 몫(x)과 나머지(y)를 구한다.
• 까지의 자리수 합 (L과 R)을 비교하여:
  • L < R: 큰 숫자 y를 A에, 작은 숫자 x를 B에 추가.
  • L >= R: 작은 숫자 x를 A에, 큰 숫자 y를 B에 추가.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void solve(String s) {
        int A = 0, B = 0;
        int L = 0, R = 0;

        for (char ch : s.toCharArray()) {
            int x = ch - '0';
            int y = x;
            x /= 2;
            y -= x;

            if (L < R) {
                A = A * 10 + y;
                B = B * 10 + x;
                L += y;
                R += x;
            } else {
                A = A * 10 + x;
                B = B * 10 + y;
                L += x;
                R += y;
            }
        }

        System.out.println(A + " " + B);
    }

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

        int T = Integer.parseInt(reader.readLine().trim());

        while (T-- > 0) {
            String s = reader.readLine().trim();
            solve(s);
        }
    }
}