<Algorithm> 126. 이상한 나라의 덧셈게임(SWExpert)

1. 이상한 나라의 덧셈게임(SWExpert)

• 수학 문제

• 처음에 최선의 선택만 보고 그리디로 접근을 했더니 경우의 수가 너무 많았다. 그래서 아래의 블로그에서 힌트를 보고 풀 수 있었다.

• 이 게임은 숫자가 주어지는 순간 게임의 승패가 결정 되어있었다. 더하기이므로 어느 위치를 더해도 결과는 정해져 있다.

• 제출할때 계속 런타임에러가 발생해서 상당히 애먹었는데 처음에는 1000자리 이하 인 줄 알고 nextInt로 했는데 알고보니 10^999 자리까지 input이 들어와 int형으로 받을 수가 없었다. 그래서 단순하게 Double로 바꿨는데 그래도 런타임에러가 발생했다. double 이 어느정도 넘어가면 chatAt에서 len와 맞지 않는 문제가 있엇고 결국 String 형으로 받아서 처리 했다.

• 문제에서 이상한나라로 표현한게 이문제의 힌트였던 것 같고 풀면서 되게 신기했다.

import java.util.Scanner;
import java.util.Stack;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        /******************************
         * Stack를 이용해서 덧셈의 위치 상관없이
         * (여기서는 뒤로) 두개의 숫자를 pop해서
         * 더하고 10이상이면 두자리수를 각각 push하고 
         * 이하면 한자리를 push해서 Stack 크기가
         * 1이 될때까지 돌린 후 2로 나눴을때 
         * 짝수면 B 홀수면 A를 출력한다.
         *******************************/
        int T = Integer.parseInt(sc.nextLine());
        
        for(int t = 0; t < T; t++ ) {
            String num = sc.nextLine();
            int len = num.length();
            
            Stack<Integer> st = new Stack<>();
            
            if(len == 1) {
                System.out.println("#"+(t+1)+" B");
                continue;
            }
            
            for(int i = 0; i < len; i++) {
                st.add(num.charAt(i)-'0');
            }
            
            int step = 0;
            
            while(st.size() != 1) {
                int sum =st.pop()+st.pop();
                
                if(sum < 10) {
                    st.push(sum);
                }else {
                    st.push(sum/10);
                    st.push(sum%10);
                }
                step++;
            }
            
                String res = (step%2==0)?"B":"A";
                System.out.println("#"+(t+1)+" "+res);
        }
        
    }
}
 

참고 & 출처  

https://whereisusb.tistory.com/281