글 읽기 - 시간초과를 어떻게 극복할 수 있을까요?

zxcv551133 7년 전 0

아래와 같은 코드로 하면 런타임에러가 나서, 몇가지를 개선하고 BigInteger을 사용하는 코드로

수정했는데 시간초과에 걸립니다.

아래 알고리즘은 한줄마다 해당 char 이 몇개 있나를 세어 반환하는 알고리즘입니다.

문자열 전체를 입력받지는 않고 처음 입력받는 word에 있는 char 개수를 이용하여 시간을 조금 단축합니다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 줄의 범위
		String word = sc.next();
		int K = sc.nextInt(); // 줄을 고른 개수
		int[] rem = new int[N + 1];
		rem[0] = 0;
		for (int i = 1; i <= N; i++) {
			rem[i] = (rem[i - 1] + i) % word.length();
		}

		for (int i = 0; i < K; i++) {
			int row = sc.nextInt();
			char c = sc.next().charAt(0);
			if (row == 1) {
				System.out.println(howManyChar(word.substring(0, 1), c));
			} else if (rem[row - 1] + rem[row] >= word.length()) {
				System.out.println((row / word.length() + 2) * howManyChar(word, c)
						- howManyChar(word.substring(0, rem[row - 1]), c)
						- howManyChar(word.substring(rem[row], word.length()), c));
			} else {
				System.out.println((row / word.length() + 1) * howManyChar(word, c)
						- howManyChar(word.substring(0, rem[row - 1]), c)
						- howManyChar(word.substring(rem[row], word.length()), c));
			}
		}
	}

	public static int howManyChar(String word, char w) {
		int count = 0;
		for (int i = 0; i < word.length(); i++) {
			if (word.charAt(i) == w) {
				count++;
			}
		}
		return count;
	}
}

zlzmsrhak 7년 전 0

howManyChar 함수를 전처리 등을 이용해서 O(L)로 미리 계산한 다음에

쿼리 처리 단계에서 O(1)로 계산하면 시간이 줄어들 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과를 어떻게 극복할 수 있을까요?

zxcv551133 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말