[누적합/자바] 코드트리 IM : 씨 오 더블유 ~ 연산한 답은 long으로

문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

알고리즘

주어진 일련의 문자열이나 수열에서 3개를 뽑아서 가짓수를 구하는 경우에, 완탐을 할 경우 시간이 초과할 것 같다면 누적합을 고려해볼 수 있다. 이 때에는 누적합 응용 기술인 LR 테크닉을 적용하는 것이 좋다.

 

이 문제에서는 n이 10의 5제곱까지이므로 완탐으로는 절대 풀 수 없을 것이다. 따라서 LR 테크닉을 적용하였다.

 

문제풀이

V1 : 실패

곱셈을 계속 더해주다보면 int 타입의 범위를 넘어서게 되어 오버플로우가 발생할 수 있다. 특히나 문자열의 길이가 10^5이므로 더욱 조심해야 한다. 가급적 코테를 볼거면 정말 가벼워보이는 답이 아닌 이상 연산값으로 통용되는 변수 ans의 선언은 long으로 하는게 안전한다.

package 코드트리.시간단축기술.LR_테크닉;

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

public class 씨_오_더블유 {
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        String[] arr = new String[n];
        int[] L = new int[n + 1];
        int[] R = new int[n + 1];
        String s = br.readLine();
        for (int i = 0; i < n; i++) {
            arr[i] = s.substring(i, i + 1);
            if (arr[i].equals("C")) {
                L[i + 1] = L[i] + 1;
            } else {
                L[i+1] = L[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (arr[n - i - 1].equals("W")) {
                R[i + 1] = R[i] + 1;
            } else {
                R[i+1] = R[i];
            }
        }
        int ans = 0; // point of failure
        for (int i = 1; i < n-1; i++) {
            if (arr[i].equals("O")) {
                ans += (L[i] * R[n - i - 1]);
            }
        }
        System.out.println(ans);
    }
}

 

V2 : 성공

package 코드트리.시간단축기술.LR_테크닉;

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

public class 씨_오_더블유 {
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        String[] arr = new String[n];
        int[] L = new int[n + 1];
        int[] R = new int[n + 1];
        String s = br.readLine();
        for (int i = 0; i < n; i++) {
            arr[i] = s.substring(i, i + 1);
            if (arr[i].equals("C")) {
                L[i + 1] = L[i] + 1;
            } else {
                L[i+1] = L[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (arr[n - i - 1].equals("W")) {
                R[i + 1] = R[i] + 1;
            } else {
                R[i+1] = R[i];
            }
        }
        long ans = 0;
        for (int i = 1; i < n-1; i++) {
            if (arr[i].equals("O")) {
                ans += (L[i] * R[n - i - 1]);
            }
        }
        System.out.println(ans);
    }
}