글 읽기 - (java) 시간초과가 왜 나는걸까요?

qorrhktk66 3년 전 0

n의 최대값인 123456을 넣어도 바로 출력이 되는데, 어디를 잡아야 시간초과가 안될까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		try {
			int N = 1;
			while (N != 0) {
				StringTokenizer st1 = new StringTokenizer(br.readLine());
				N = Integer.parseInt(st1.nextToken());
				if (N != 0) {
					int M = 2 * N;
					int count = 0;
					ArrayList<String> list = new ArrayList<String>();
					for (long i = N + 1; i <= M; i++) {
						if (i > 1) { // 1보다 크면서
							if (i <= 3) { // 3이하 (2, 3)일때
								list.add(i + "");
							} else { // 4 이상일 때
								if (i % 2 == 1) { // 홀수일 때만
									count = 0;
									for (long j = 3; j <= (int) (Math.sqrt(i)); j++) {
										if (i % j == 0) {
											count++;
										}
									}
									if (count == 0) {
										list.add(i + "");
									}
								}
							}
						}
					}
					bw.write(list.size() + "\n");
				}
			}

			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

qorrhktk66 3년 전 0

31 카운트부분에 break;만 추가해줬는데 되네요.

굳이 여러번 카운트 할것 없이 한번 나누어 질때 카운트만 걸어줘도 됐었습니다.

qorrhktk66 3년 전 0

그리고 애초에 리스트를 인티저로 했으면 됐을텐데, 좀 멍청했습니다 ㅜㅜ

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

문제

문제

출처

ICPC

(java) 시간초과가 왜 나는걸까요?

qorrhktk66 3년 전 0

qorrhktk66 3년 전 0

qorrhktk66 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말