백준 1009

• solved.ac기준 브론즈 2단계 문제
  
  

풀이)

1. 숫자의 범위가 매우 커져 BigInteger을 활용하려 했으나 메모리 초과로 불가능.

2. 일의 자리 수만 보면 되기 때문에 숫자를 무조건 곱하지 말고, 나머지 연산을 통해 일의 자리만 곱한다.
   예를 들어 7의 100승을 알고자 한다면 7 -> 7x7 = 49 -> 9x7 = 63 -> 3x7 = 21 -> ... 이렇게 일의 자리만 따온다.

3. 더 나아가 시간을 최소한으로 줄이려면 각 숫자마다 제곱할 때의 규칙을 따져야 한다. 숫자를 제곱할 때 일의 자리 수가 규칙적으로 바뀌는 점을 이용해 문제를 풀어야 한다.

• 1, 5, 6은 제곱하면 항상 일의 자리 수가 똑같으며
• 2, 3, 7, 8은 제곱하면 4번의 사이클로 규칙적으로 일의 자리 수가 바뀐다.
• 4, 6은 제곱하면 2번의 사이클로 규칙적으로 일의 자리 수가 바뀐다.
• 10은 제곱하면 항상 일의 자리 수가 0이다.

4. 시간을 최대한 줄이기 위해 String으로 연산할 게 아니라, StringBuilder sb를 활용했다.

5. swich case 문 중 조건을 여러 개 붙이는 콤마 방식은 java 14 이후로 가능한 기능이기에, 백준 오픈 sdk에선 컴파일이 불가능하다. 때문에 if 문을 활용한다.

실제로 StringBuilder을 활용했는지, 풀이 2나 3을 썼는지에 따라 런타임이 유의미하게 달라진다.

내 코드)

//풀이 2번 활용.
//StringBuilder 안 씀.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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

		int test = Integer.parseInt(bf.readLine());
		String sb = "";
        for (int i = 0; i < test; i++) {
        	String input[] =bf.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            if (a == 1) {
            	sb += "1\n";
            	continue;
            }
            if (a % 10 == 0) {
                sb += "10\n";
                continue;
            }
            int result = a % 10;
            for (int j = 1; j < b; j++) {
            	result = (result * (a%10)) %10;
            }
            sb += result + "\n";
        }
        System.out.print(sb);	
	}
}

코드 1)

//풀이 2번 방식을 활용.
// StringBuilder 활용
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[]args) throws IOException {
	
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int test = Integer.parseInt(bf.readLine());
        for (int i = 0; i < test; i++) {
        	String input[] =bf.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            if (a == 1) {
            	sb.append("1\n");
            	continue;
            }
            if (a % 10 == 0) {
            	sb.append("10\n");
                continue;
            }
            int result = a % 10;
            for (int j = 1; j < b; j++) {
            	result = (result * (a%10)) %10;
            }
            sb.append(result + "\n");
        }
        System.out.print(sb);	
	}
}

코드 2)

//풀이 3번 방식을 활용.
`import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Main {
	public static void main(String[]args) throws IOException {
	
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int test = Integer.parseInt(bf.readLine());
        for (int i = 0; i < test; i++) {
        	String input[] =bf.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int ans = a%10;
            
            if(ans == 0 )sb.append("10\n");
            else {
				if (ans == 2 || ans == 3 || ans == 7 || ans == 8) {
					b = (b - 1) % 4;
					for (int j = 0; j < b; j++) {
						ans = (ans * a) % 10;
					}
				} else if (ans == 4 || ans == 9) {
					if (b % 2 == 0) {
						ans = (ans * a) % 10;
					}
				}
				sb.append(ans).append("\n");
            }

        }
        System.out.print(sb);	
	}
}

• 추가

//버전이 맏지 않아 백준에선 해당 구문을 쓸 수는 없지만 이 또한 맞는 방식이다.

            switch(ans){
            	case 0 -> {
            		sb.append("10\n");
            		break;}
            	case 1, 6, 5-> {
            		sb.append(ans + "\n");
            		break;}
            	case 4, 9-> {
            		if(b%2 != 0) {sb.append(ans + "\n");}
            		else {sb.append((ans * a)%10 + "\n");}
            		break;}
            	case 2, 3, 7, 8->{
            		b = (b-1) % 4;
            		for (int j =0; j<b;j++)
            			ans = (ans * a) % 10;
            		sb.append(ans + "\n");
            		break;}
            }