[SWEA]SWEA_D4_5604_구간합

SWEA_D4_5604_구간합

 

 

문제링크

SW Expert Academy

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://tv.naver.com/v/22678458

SWEA_D4_5604_구간합 - HD 1080p

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.d4;

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

/**
 * @author 은서파
 * @since 2021. 9. 28.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGGNB6cnEDFAUo&categoryId=AWXGGNB6cnEDFAUo&categoryType=CODE&problemTitle=5604&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
 * @performance 22,996 kb, 103 ms
 * @category #구현
 * @memo
 */

public class SWEA_D4_5604_구간합 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	static int T;
	static long A, B; // A와B의 최대는 10^15
	static long [] cnts;
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(input.readLine());
		for(int t=1; t<=T; t++) {
			tokens = new StringTokenizer(input.readLine());
			A = Long.parseLong(tokens.nextToken());
			B = Long.parseLong(tokens.nextToken());
			
			cnts = new long[10]; // 0부터 9까지 숫자들이 몇 번이나 나오는지 저장할 배열
			// 증가시켜야 할 개수 단위
			long delta = 1;
			while(A<=B) {
				// 위쪽 짜투리
				for(; A%10!=0 && A<=B; A++) {
					parse(A, delta);
				}
				// 아래쪽 짜투리
				for(; B%10!=9 && A<=B; B--) {
					parse(B, delta);
				}
				// A: 33, B:34 이었다면.. 이 시점에서 A는? 35
				if(A>B) {
					break;
				}
				// 이제 남은것 1 - 0~9까지의 row를 처리한다. - row의 개수만큼 추가.
				// 40 ~ 129 까지는 몇 개의 row?
				A/=10; // 4
				B/=10; // 12
				long rowCnt = B-A+1;
				for(int i=0; i<10; i++) {
					cnts[i]+=rowCnt*delta;
				}
				delta*=10;
			}// cnt 처리 완료!!
			
			long sum = 0;
			for(int i=1; i<10; i++) {
				sum+=i*cnts[i];
			}
			output.append("#").append(t).append(" ").append(sum).append("\n");
			
		}// testcase
		System.out.println(output);
	}
	
	private static void parse(long x, long delta) {
		// 123 --> 3, 2, 1
		while(x>0) {
			cnts[(int)(x%10)]+=delta;
			x/=10;
		}
	}
	

	// REMOVE_START
	private static String src = "3\n"
								+ "0 10\n"
								+ "8 12\n"
								+ "33 133";
	// REMOVE_END

}