[SWEA 5604] 구간 합 (JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo

SW Expert Academy

1. 주의할 점

- 숫자 하나씩 직접 할 경우 시간초과발생

- 10^15의 마지막 자리수를 Long으로 받아오고(Integer로는 10^15자체를 선언할 수 없다), Number 배열의 Index에 접근시 런타임에러 발생(이거 때문에 2번 틀렸다)

- 각 자리수의 중요성

 

2. 구현

(1) 백준의 1019번 문제 "책페이지"와 푸는 방법이 거의 똑같다.

(2) Start와 End를 입력받은 후, While문을 수행한다.

(3) Start는 End보다 크지 않으면서, 끝자리가 0이 되도록 숫자를 1씩 더한다. 또한, 더하는 과정에서 해당 자리수(Mul)만큼 Number에 더해준다.

Ex) 768          ->                  769               ->            770

            number[8]+=Mul                number[9]+=Mul

 

(4) 현 시점에서 Start가 End보다 크다면 멈춘다

Ex) Start: 77, End: 79

    Start : 77->78->79->80

    While문에서 벗어난다.

 

(5) End는 Start보다 작지 않으면서, 끝자리가 9가 되도록 숫자를 1씩 뺀다. 또한, 빼는 과정에서 해당 자리수(Mul)만큼 Number에 더해준다.

Ex) 811          ->                  810               ->            809

            number[1]+=Mul               number[0]+=Mul

(6) 바뀐 Start와 End를 기준으로 ((Start/10)-(End/10)+1) *Mul만큼 Number[0~9]에 더해준다.

Ex) 바뀐 Start : 770, 바뀐 End: 809, (Start/10)-(End/10)+1) = 80-77+1 = 4

(7) Mul에 10을 곱하고(다음으로 구하려는 숫자는 기존에 몇번째 자리의 수였는지 기억하는 역할), Start와 End는 10씩 나눈후 다시 2-(3)번부터 시작한다.

 

[2-(6)번에서 "((Start/10)-(End/10)+1) *Mul만큼 Number[0~9]에 더해준다" 해주는 이유]

우선 770부터 809까지 끝자리 0~9가 4번씩 나온다.

Mul을 곱하는 이유: 만약 입력으로 받았던 숫자가 7700과 8090이였다면 빨간 부분은 이미 한번의 While문을 돈 이후다. 따라서 뒤에서 첫번째 자리가 아닌 뒤에서 2번째 자리수이므로 4번이 아닌 40번씩 나온다는 결과를 지닌다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_d4_5604_구간합 {
	static long number[], result,start, end, mul;
	static void cal(long a) {
		for (long i = a; i > 0; i /= 10) {
			String s = Long.toString(i);
			int t = s.charAt(s.length()-1)-'0';
			number[t]+=mul;				
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for (int t = 1; t <= test; t++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			start = Long.parseLong(st.nextToken());
			end = Long.parseLong(st.nextToken());
			// 초기화
			number = new long[10];
			result = 0;
			mul = 1;
			if(start==0) start=1;
			while (start <= end) {
				while(start%10!=0 && start<=end) {
					cal(start);
					start++;
				}
				if(start>end) break;
				while(end%10!=9 && start<=end) {
					cal(end);
					end--;
				}
				long diff = end/10 - start/10 +1;
				for(int i=0;i<10;i++)
					number[i]+=diff*mul;
				mul*=10;
				start/=10;
				end/=10;
			}		
			for (int i = 1; i < 10; i++)
				result += (i * number[i]);
			System.out.println("#" + t + " " + result);
		}
	}
}