이 문제에 경우 특별한 알고리즘을 필요로 하진 않는다. 조금만 생각한다면 주어진 조건을 쉽게 찾을 수 있다. 먼저 반으로 나눴을 때 합이 최소가 되려면 자릿수가 가장 적어여 한다. 1이 아무리 작은 값이라도 10만의 자리수로 가면 그 밑의 자릿수에서 아무리 9여도 1보다 클 수 없다는 얘기다. 즉, 자릿수를 가장 적게 만들도록 로직을 작성하면 된다.
그럼 어떻게 만들란 말인가??
1. 우선 짝수일 때를 생각해보면 무조건 반띵이다. 조금만 생각하면 알 수 있으니 설명은 생략한다. 2. 그럼 홀수일 때는? 두 가지로 나뉜다. a. 왼쪽 서브스트링이 더 긴 경우 b. 오른쪽 서브스트링이 더 긴 경우
2번이 이해가 가지 않는다면 예시를 들어보겠다. 123이 있을 때 반띵을 하려니 정확히 나누어지지 않는다. 왼 쪽이 클 수도 있고 오른쪽이 클 수도 있으니 이 두 경우의 수를 모두 계산한다. 12+3 VS 1+23 따라서 15가 더 작으므로 15를 선택하게 만들면 된다. 위 알고리즘을 코드로 살펴보자.
코드
import java.util.Arrays;
import java.util.Scanner;
import static java.lang.Math.min;
/*
사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
*/
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
String str = sc.next();
// int -> int[]
int[] num = str.chars().map(c -> c - '0').toArray();
int len = num.length;
int half = len / 2;
int[] subLeft = Arrays.copyOf(num, half);
int[] subRight = Arrays.copyOfRange(num, half, num.length);
int sumLeft = sum(subLeft);
int sumRight = sum(subRight);
if (num.length % 2 == 0) { //짝수면 무조건 반갈
System.out.printf("#%d %d\n", test_case, sumLeft + sumRight);
}
else { // 홀수일 땐 왼쪽이 긴 배열, 오른쪽이 긴 배열 두 경우가 있으므로
int[] subLeft2 = Arrays.copyOf(num, half + 1);
int[] subRight2 = Arrays.copyOfRange(num, half + 1, num.length);
int sumLeft2 = sum(subLeft2);
int sumRight2 = sum(subRight2);
System.out.printf("#%d %d\n", test_case, min(sumLeft + sumRight, sumLeft2 + sumRight2));
}
}
}
static int sum(int[] arr) {
int cnt = 1;
int result = 0;
for (int i = arr.length-1; i >= 0; i--) {
result = result + arr[i] * cnt;
cnt *= 10;
}
return result;
}
}
보이는 바와 같이 홀수일 경우에 대해선 왼쪽 서브스트링의 길이가 더 긴 경우를 고려하는 부분을 추가해주었다.
주석으로 설명해놓았으니 이해하는데 크게 어렵진 않을 것이다.
추가로 int -> int[], string->int[]로 바꾸는 로직이 생각보다 자주 출제되므로 한번 확실하게 이해하고 넘어가는 편이 좋을 것 같다.
