[Java] Softeer 슈퍼바이러스를 풀면서 (분할 정복과 이것 저것 정리)

들어가면서..

요즘 Java 언어로 코딩테스트를 대비하기 시작하면서, Softeer에 등록된 연습 문제들을 풀며 자바 폐관 수련을 이어나가고 있습니다..

 

그러던 중 오랜만에 분할 정복을 통해 풀어야 하는 문제를 풀이하는데, 풀이 방법을 떠올리지 못해서 분할 정복 풀이 방식에 대해 정리해 볼 겸.. 공부하면서 깨달은 여러 가지를 끄적여보려고 합니다.

 

---

Softeer Level 3 슈퍼바이러스 문제

 

Softeer

바로 이 문제가 글을 쓰게 만든 원인입니다.

문제 자체는 설명만 보면 굉장히 쉬워 보이지만, linear 하게 곱셈 연산을 N번 하게 되면 10의 16승 번의 연산을 진행하게 되어 제 시간을 절대 지킬 수 없습니다.

 

이러한 경우 이전에는 당연하게 "그렇다면, 시간 복잡도를 log 밑 2로 줄여야 겠는데??" 라는 생각을 하지 않았을까 싶은데, 오랜만에 다시 문제들을 풀다 보니 떠올리지 못했습니다.

 

 

앞서 말했듯이 이 문제는 분할 정복을 이용해 풀이하면 됩니다.

문제의 원인은 P의 N * 10 승을 구하는 부분에서 시간이 초과되는 것이므로, 이 부분을 이중 분할을 이용해서 해결해 주면 됩니다.

---

그래서 어떻게 코딩을 해야하지?

"백문이 불어일타"라고 코드부터 보겠습니다.

private static long solve(long p, long n){
    if(n == 1)
        return p;

    long res = solve(p, n / 2);
    if(n % 2 == 0){
        return (res * res) % MOD;
    }
    else{
        res *= res;
        res %= MOD;
        return (res * p) % MOD;
    }
}

저는 p의 n승을 구하는 함수를 위와 같이 작성했습니다.

 

이때, n을 2로 나누면서 하나의 큰 문제 계산을 해결하기 위해 작은 단위의 문제로 쪼개는데, (n / 2 승을 구한 뒤 이 결과 두 개를 곱하는 거죠)

n이 짝수인지 홀수인지 여부에 따라 작업이 달라집니다. (작업을 두 개로 쪼개기 때문)

 

 

n이 짝수인 경우에는 n / 2가 깔끔하게 나누어 떨어질 것이고 solve method 실행 결과를 얻은 다음 이걸 제곱 연산하면 끝입니다. (물론 이는 재귀적 호출을 통해 n == 1까지 계산되겠죠??)

 

n이 홀수인 경우에는 n / 2 연산 결과가 사실 *.5와 같이 나올 겁니다. (물론 정수형 타입 연산이라 소수점은 연산되지 않습니다.) 

 

예를 들어 n = 5 라면, n / 2 = 2일 것이므로 두 개의 solve method 결과에 p를 한 번 더 곱해줘야 하는 것입니다.

 

 

 

여기서 다음 부분을 왜 굳이 이렇게 처리했지 싶으실 것 같습니다.

else{
    res *= res;
    res %= MOD;
    return (res * p) % MOD;
}

그냥 (res * res * p) % MOD로 계산하면 안 되나?? 싶으실 것 같은데, 원래 저도 이렇게 제출을 했으나.. 실패했습니다.

 

 

 

실패 원인을 생각해 보면, 아마 res 최댓값이 10^9 정도, p는 10^8 이므로 res * res * p가 이론상 10 ^ 26 까지 커질 수 있고, 이는 2 ^ 80을 넘어서는 크기의 수가 됩니다. (10 ^ 3 은 대략 2 ^ 10 이므로)

 

그래서 저 연산 도중에 데이터 손실이 발생하고, 큰 숫자의 연산에서 실패하는 케이스가 등장하는 것 같더라고요 (python으로 푸시는 분들은 그냥 res * res * p % MOD로 처리해도 다 맞더라고요..)

---

전체 답안은??

제출한 답안은 다음과 같습니다.

private static final int MOD = 1000000007;

public static void main(String args[]) throws IOException
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    long k = Long.parseLong(st.nextToken());
    long p = Long.parseLong(st.nextToken());
    long n = Long.parseLong(st.nextToken());
    n *= 10;

    long res = solve(p, n) * k;
    res %= MOD;

    System.out.println(res);
}

private static long solve(long p, long n){
    if(n == 1)
        return p;

    long res = solve(p, n / 2);
    if(n % 2 == 0){
        return (res * res) % MOD;
    }
    else{
        res *= res;
        res %= MOD;
        return (res * p) % MOD;
    }
}

---

여러 가지 오늘 배운 점들

먼저 입출력 처리를 하는 방법을 조금 정리했습니다.

 

크게 BufferedReader + StringTokenizer를 이용하는 방법과 Scanner를 이용하는 두 가지 방법으로 입출력을 다루더라고요

전자의 성능이 조금 더 좋다고 합니다.

 

주로 Scanner를 이용해서 입력을 처리했는데, 속도를 위해서라도 코딩테스트를 볼 때에는 BufferedReader를 활용하는 것이 좋아 보입니다. 

 

(Scanner가 여러 가지 지원하는 메서드를 통해 타입 캐스팅을 직접 할 필요가 없다는 점, 사용하기 쉽다는 점 등 장점이 많기는 하지만.. 많은 입력을 요구하는 경우 성능 상 좋지 못합니다.)

 

• BufferedReader
  • java.io package에 존재 
  • 입력된 데이터를 버퍼를 거쳐 전달한다.
  • 이에 따라 많은 양의 데이터를 처리할 때 유리
  • new BufferedReader(new InputStreamReader(System.in)); 이런 형태로 프로그램 입력을 받기 위해 선언해서 사용하더라
• BufferedWriter
  • java.io package에 존재 
  • 출력할 데이터를 버퍼를 거쳐 전달한다.
  • 버퍼를 통해 출력하기 때문에 flush(), close() 반드시 호출해서 뒤처리까지 해줘야 한다.
  • write method는 자동 개행을 제공하지 않으니 직접 처리해 줘야!!
• StringTokenizer
  • BufferedReader로 입력받은 데이터를 line 단위로만 처리 가능해서 같이 사용한다.
  • StringTokenizer의 nextToken method를 이용하면, 공백 단위로 끊어서 데이터 처리가 가능!
  • BufferedReader만 사용하고 싶은 경우에는 String.split() method 사용해도 무관

 

입출력 방식의 성능 비교나 설명등은 다음 글들을 참고했습니다.

https://rlakuku-program.tistory.com/33

[Java] 빠른 입출력을 위한 BufferedReader, BufferedWriter, StringTokenizer, StringBuilder

---

ArrayList vs LinkedList

ArrayList

• 내부적으로 데이터를 배열로 관리
• index 이용해 탐색 비용 저렴 → O(1)
• 데이터 추가 삭제를 위해 임시 배열을 생성해 데이터를 복사하는 방법
• 따라서 추가, 삭제에 대한 비용 부담 → O(N)

LinkedList

• 인접 리스트 구조를 따른다.
• 따라서 탐색 비용이 높다 → O(N)
• 각 노드가 인접한 노드의 정보만 알고 있는 상태
• 대신 추가, 삭제 비용 저렴 → O(1)

이러한 점을 참고해서, ArrayList, LinkedList 사용하면 될 것으로 보임

 

Queue 구현에는 LinkedList 사용하고, 일반 배열 정보를 사용할 때에는 ArrayList 사용이 적합해 보인다. (C++ vector 대체 용도 목적)

---

요즘 추세가 백엔드 개발자들에게는 Java 언어를 이용한 코테를 요구하는 곳이 많은 것 같아서 익숙한 C++을 대신해 Java로 문제들을 계속해서 풀고 있는데

 

개발을 할 때 사용하는 문법들과는 또 다른 부분들도 있는 것 같고, 사용하는 자료 구조들도 아직 익숙지 않다 보니 여러 시행착오를 거치고 있는 것 같습니다.

 

그래도 풀다 보면 익숙해지지 않을까.. 생각하며 여기서 글을 마쳐보겠습니다.