글 읽기 - 나름 최적화한다고 했는데 시간초과가 발생하는 이유를 모르겠습니다.

hpdong413 7년 전 0

안녕하세요.

여러가지 방법으로 시도하다 카드 번호 범위를 배열 인덱스로 처리해도 되겠다싶어

아래와 같은 코드를 작성했습니다. 카드 번호를 인덱스로 처리해서 충분히 빠르다고 생각했는데

계속 시간 초과가 뜨네요. 혹시 제가 참고할만한 팁이라도 있을까요?

추가로 전에 어떤 분이 Scanner를 사용할 때 BufferedReader를 같이 쓰면 속도가 더 좋다고 하셔서

아래와 같은 방식으로 사용했는데 이게 맞는 건지도 궁금합니다.

조언 부탁드립니다.

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

public class Main {
	
	public static int[] map = new int[20000001];
	
	public static void main(String[] args) {
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(in);
		
		int numOfCard = sc.nextInt();
		
		for (int a = 0 ; a < numOfCard; a++) {
			int num = sc.nextInt();
			map[num + 10000000]++;
		}
		
		int testCount = sc.nextInt();
		
		for (int a = 0; a < testCount; a++) {
			int num= sc.nextInt();
			System.out.print(map[num + 10000000] + " ");
		}
		System.out.println();
		
		sc.close();
	}
}

sksdong1 7년 전 1

오.. 배열 2천만 크기로 잡아도 메모리 초과가 안나나요?

출력도 버퍼로 해보세요.

indioindio 7년 전 0

통과한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
  public static int[] map = new int[20000001];
 
  public static void main(String[] args) throws IOException
  {
 
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
    int numOfCard = Integer.parseInt(in.readLine());
    String[] input = in.readLine().split(" ");
    int num = 0;
 
    for (int a = 0 ; a < numOfCard; a++) {
      num = Integer.parseInt(input[a]);
      map[num + 10000000]++;
    }
 
    int testCount = Integer.parseInt(in.readLine());
    input = in.readLine().split(" ");
    StringBuilder ret = new StringBuilder(6 * testCount);
 
    for (int a = 0; a < testCount; a++) {
      num = Integer.parseInt(input[a]);
      ret.append(map[num+10000000]);
      ret.append(" ");
    }
    System.out.println(ret.toString());
 
  }
}

indioindio 7년 전 1

출력은 StringBuilder로 모아서 한 번에 했습니다.

6 * testCount는 대충 정답길이 정도 미리 할당한 건데 빈 괄호로 두어도 무방할 것 같네요.

hpdong413 7년 전 0

답변 감사합니다.

Scanner를 가장 단순한 형태로 사용하기만 했는데, 라인별로 읽어서 처리하면 속도가 훨씬 빠르군요.

이것과 비슷한 문제 때문에 시간 초과가 많이 발생했었는데 버퍼를 이용한 입출력으로 다시 도전해봐야겠습니다!!!

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

문제

문제

출처

ICPC

나름 최적화한다고 했는데 시간초과가 발생하는 이유를 모르겠습니다.

hpdong413 7년 전 0

sksdong1 7년 전 1

indioindio 7년 전 0

indioindio 7년 전 1

hpdong413 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말