백준 23046 자바 - 큰 수 뒤집기 (BOJ 23046 JAVA)

문제 : https://www.acmicpc.net/problem/23046

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23000/BOJ_23046.java

 

 

... 8시간 걸렸다. 주말 다 날라갔다.

 

  처음엔 reverse에 대해 boolean으로만 처리하고 deque에 앞뒤로 boolean값에 따라 앞이나 뒤에 넣으면서 풀라는 쉬운 문제인줄 알았다. 그리고 '-' 나오기 전까지는 사실 실제로 s를 x에 더하지 않아도 되니깐, '-' 나오면 boolean값 반전시키면서 deque에 넣고, 그동안 쌓인거 저장하는 식으로 구성했다.

  거기서도 시간 줄이고 충분히 가능할꺼라 생각했다. 그런데 계속 시간초과가 나길래, 거기에 deque도 배열로 직접 만들어 쓰고, 정수 계산도 x라는 배열에 넣어 이후 한방에 carry 까지 구해가며 직접 계산했다. 거기까지 해본게 아래와 같은 코드이다.

 

 

* 시간 초과 난 코드임.

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

public class Main {
    private static class DQ {
        int[] arr;
        int s, e;
        int updateCnt;
        public DQ(int n, int first) {
            arr = new int[n*2+1];
            s = e = n;
            arr[s] = first;
            updateCnt = 1;
        }
        public void addFirst(int n) {arr[--s] = n; updateCnt++;}
        public void addLast(int n)  {arr[++e] = n; updateCnt++;}
        public void setUpdateCntZero() {updateCnt = 0;}
        public boolean needUpdate() {return updateCnt != 0;}
    }

    private static int[] x;
    private static DQ s;
    private static boolean isReverse = false;

    private static void addToX() {
        if (!s.needUpdate()) return;
        int updateCnt = s.updateCnt;
        s.setUpdateCntZero();

        int len = s.e-s.s+1;
        int[] tmp = new int[len];
        int[] tmp2 = new int[len];
        if (isReverse) {
            for (int i = s.s, tmpIdx = tmp.length-1; i <= s.e; i++, tmpIdx--) {
                tmp[tmpIdx] = s.arr[i];
                tmp2[tmpIdx] = s.arr[i];
            }
        } else {
            for (int i = s.e, tmpIdx = tmp.length-1; i >= s.s; i--, tmpIdx--) {
                tmp[tmpIdx] = s.arr[i];
                tmp2[tmpIdx] = s.arr[i];
            }
        }
        for (int i = 1; i < tmp.length; i++) {
            tmp[i] += tmp2[i-1];
            tmp2[i] += tmp2[i-1];
            if (i - updateCnt >= 0)
                tmp[i] -= tmp2[i-updateCnt];
        }

        int idx = x.length-1;
        int tmpIdx = tmp.length-1;
        while (len-->0) {
            x[idx--] += tmp[tmpIdx--];
        }
    }

    private static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        x = new int[input.length()+2];
        s = new DQ(input.length(), input.charAt(0)-'0');

        int cnt = 0;
        for (int i = 1; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '-') {
                addToX();
                isReverse = !isReverse;
                continue;
            }

            cnt++;
            if (!isReverse) s.addLast(c-'0');
            else s.addFirst(c-'0');
        }
        addToX();

        for (int i = x.length-1; i > input.length()+1-cnt; i--) {
            if (x[i] >= 10) {
                x[i-1] += x[i]/10;
                x[i] %= 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = input.length()+1-cnt;
        for (; i < x.length; i++) {
            if (x[i] != 0) break;
        }
        for (; i < x.length; i++) {
            sb.append(x[i]);
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        solution();
    }
}

 

그런데도 택도 없었다. 로직상 O(N^2)이 맞긴했지만, '-' 만날때만 저장하고, 숫자가 처음엔 적으니 어떻게든 될 줄 알았다..

 

  다른분의 도움도 받아가며 해보려 했지만 실패했었다(수학과 멋져). 와중에 공책에 계속 그려보다보니 규칙을 어느정도 찾은 것 같아 결론적으론 DP로 풀었다. 그리고 저 계산법도 크게 도움이 됬다. (예를들어 111111가 있다면, (111111*9+1) 라고 하면 1000000이 된다. 큰 수 이므로 직접 배열로 계산해야하는 상황에서 111111 이런게 100만자리가 있다고 치면, 100만개를 직접 배열에 기입하면 너무 시간손해가 크다. 하지만 거기에 9를 곱하고 1을 더하면 100만1번째 자리에만 1을 더해주고, 1의 자리에서 1만 빼면 되는것이다. 그리고 최종적으로 답을 출력하기 전에 9로 나눠주면 된다.)

 

  그럼 이제 내가 푼 방식을 써보겠다.

 

1. 12-34-56-78 이렇게 입력이 들어왔다고 보자.

그럼 1 + 12 + 213 + 2134 + 43125 + 431256 + 6521347 + 65213478 을 계산하면 답이 된다.

이걸 초딩때부터 덧셈에 사용한 방식처럼 위에서 아래로 쭉 나열해 보겠다.

위와 같이 된다.

 

2. 그리고 뒤집어지지 않은채 입력이 들어왔던 상태와, 뒤집어서 들어왔던 상태를 나눠서 살펴보자.

그럼 규칙을 찾아볼 수 있을 것이다. '1'만 봐보겠다.

다른 숫자들을 해봐도 모두 위와 같다. 노란색(안뒤집혀서 들어온 녀석들)은 노란색끼리 연결되고, 하얀부분 (뒤집혀서 들어온 녀석들)도 마찬가지로 하얀부분끼리 연결된다. 하나 더 있는데, 노란색 부분에서 처음 들어왔던 녀석들이 들어온 순서가 x라고 하면, 노란부분에서 우측에서부터 x칸만큼 밀려난 부분부터 위치하게 된다. 마찬가지로 하얀 부분에서 처음 들어온 녀석들도 노란색에서 우측에서 x칸만큼 밀려난 부분부터 위치하게 된다.

 

  즉, 위 이미지를 정리해보면 다음과 같다. 전부 맨 위로 땡긴셈이다.

 A-1. 노란부분에서 들어온 녀석들이 노란부분에서 영향을 끼친 자리수 (1의 자리부터 영향을 끼침)

A-2. 노란부분에서 들어온 녀석들이 하얀부분에서 영향을 끼친 자리수 (x번째로 들어온 경우 우측부터 x만큼 밀려난 부분부터 영향을 끼침)

B-1. 하얀부분에서 들어온 녀석들이 하얀부분에 영향을 끼친 자리수

B-2. 하얀부분에서 들어온 녀석들이 노란부분에서 영향을 끼친 자리수

간단히 적어놨지만 혹시 규칙 없을까 하고 써보다보니 공책 한 5장정도 날아갔다ㅋㅋ 수학적 지식이 딸리니 증명은 못하고 매번 이런식으로 찾는 경우가 많아 많이 아쉽다. 머리가 나쁘면 몸이 고생한다는게 이 경우다 ㅠ

 

 

3. 그럼 이제 뭘 알아야 하냐면, x번째로 들어온 수가 언제 들어왔고, 뒤집어진 상태로 들어왔는지 안뒤집힌 상태로 들어왔는지를 알아야 한다. 또한 위 4개의 이미지로 우측에서부터 몇 번째 자리에서 영향을 끼친지는 알 수 있는데, 그럼 좌측으로 몇번째 위치까지 영향을 끼치는지를 알아야 한다. 그렇게만 알면 위에 수학과분이 알려준 방식을 통해 빠르게 답을 구할 수 있다.

 

이걸 구하기 위해 다음과 같이 진행해봤다.

 

A. 입력을 받으며 실제 값은 따로 저장해두고 (코드의 arr), 2차원 배열을 하나 만든다. (코드의 dp) 그리고, x번째 들어온 값이 안뒤집힌 상태에서 들어왔다면 dp[0][x]를 1로, 뒤집혀서 들어왔다면 dp[1][x]를 1로 했다.

그 다음, 맨 우측부터 좌측으로 보면서, 만약 현재 1의 위치가 바뀌지 않은 상태라면 다음과 같다.

dp[0][i] = dp[0][i+1];
dp[1][i] = dp[1][i+1]+1;

만약 현재 1의 위치가 바뀐 상태라면 다음과 같다.

dp[1][i] = dp[0][i+1]+1;
dp[0][i] = dp[1][i+1];

무슨말이냐면, 

위와 같이 빨간 화살표가 안바뀐 것 (1이 위에 있던 상태에서 위에 있는 곳으로 이동하거나, 아래에 있던 상태에서 아래에 있는 곳으로 이동) / 파란 화살표가 상태가 바뀐 것이다.

 

그럼 위의 과정대로 진행하면

이렇게 나온다. 이걸로 뭘 알 수 있냐면, 이게 x번째 들어온 녀석들이 안뒤집힌 부분과 뒤집힌 부분에 영향을 끼친 횟수이다. 윗 줄이 뒤집힌 부분에서 끼친 영향의 횟수, 아랫줄이 안뒤집힌 부분에서 끼친 영향의 횟수이다.

 

예를들어 2번째로 들어왔던 '2'의 경우 다음과 같다.

 

4. 그럼 이제 계산을 하면 되는데, 이 부분에 위 수학과분이 알려준 방식을 사용했다. 코드의 42~56 line에 해당한다.

 

 

5. 다음으로 각 자리수에 더해뒀던 수 들을 전부 carry를 위로 올리며 실제 수를 구해야 한다. long으로도 표현 못할 200만자리의 문제이므로, 아이디어도 어렵지만 애초에 모든 연산을 최적화 해야 통과가 가능하다. 사실 그래서 엄청 오래걸리기도 했다. 뭐 하나 시간복잡도 생각을 미흡하게 하면 바로 시간초과다; 특히 자바라 더 그렇다. 이건 실제 우리가 덧셈 할때와 마찬가지다. 매번 carry 달아 올려줄 필요는 없고, 한방에 모아서 올려도 상관 없다는 점만 유의하면 된다. (매번 더할 때 마다 carry 달아 올리면 시간초과 난다.)

 

예를들어 다음을 보자. 356+999+888을 할꺼다. 다만 일단 carry를 올리지 않고, 자리수별로 더했다.

그럼 이걸 정수로 어떻게 바꿀 수 있을까? 우측부터 보며, 10을 나눈 몫을 위 자리수로 넘기고, 10으로 나눈 나머지만 냄겨두면 된다. 과정은 다음과 같다.

이건 2자리 수로 진행했지만, 1의 자리에 뭐 100만이 있어도 마찬가지 방식으로 가능하다.

이 부분을 구현하게 58~69 line 이다.

 

 

6. 예시로 계속 보여주고 있던 '12-34-56-78' 입력의 경우 위 과정을 거쳐 다음과 같이 된다. 앞에 있는 '0'들은 때고 그렸다. 배열의 각 칸이 정수의 자리수를 뜻하므로 아래를 정수로 표현하면 '649904094'가 된다.

 

 

7. 그럼 이제 뭐가 남았냐면, 초반에 설명한 대로 저걸 9로 나누면 된다. 그럼 최대 20만1 자리 숫자를 9로 나누는 연산을 해야 한다. 이 경우, 자바는 BigInteger라고 무제한에 가까운 정수를 표현하는 클래스가 있다. 거기서 나누려면 'new BigInteger("649904094").divide(new BigInteger("9"));' 와 같이 하면 된다. 그리고 내 코드를 보면 해당 코드가 없는데, 그 코드는 초반에 있었던 '시간 초과'가 빼곡한 코드들 중 하나에 있다 -_-;;

  분명 로직상 O(N)에 비례하는데 이젠 맞아야지.. 하며 맞왜틀을 외치고 있던중에 혹시나하고 시간을 재보니, 200만 자리 수 나누기 9에 대한 BigInteger 클래스의 연산이 59초가 걸린다 ㅋㅋㅋ

 

아무튼 그러니 나누기도 직접 짜야 한다...

이것 역시 초딩때 쓰던 방식을 구현하면 된다. 위 예시는 너무 크니깐 좀 줄여서 1206 / 9 를 해보자.

요걸 하면 된다. 일단 손으로 하면 다음과 같다.

이걸 코드로 구현한 부분이 72~81 line 이다. (애초에 맨 처음에 나왔던 공식만을 사용해 계산했으므로 무조건 9의 배수임이 보장된다.)

 

 

...

 

풀고 아이디가 빨간분들 (개고수) 보니 훨씬 간단한 코드로 풀었다..; 코드를 봐도 어떻게 푼건지 잘 모르겠다... 나중에 알게되면 다시 올리겠다.

 

아이디어도 생각하기 어려웠지만, 역대급 구현 문제 였다. 당분간 정수형 범위 넘어가는 문제는 쳐다도 안볼 것 같다.