글 읽기 - 17176번 시간초과 해결...

99waterk 4년 전 0

17176번을 풀면서 시간초과가 나는데 왜 나느지 모르겠습니다... 반복문도 하나밖에 쓰지 않았는데 뭘 잘못한걸까요....

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		String[] tmp = br.readLine().split(" ");
		int[] tmpN = new int[n];
		String ans = br.readLine();
		for (int i = 0; i < n; i++) {

			tmpN[i] = Integer.parseInt(tmp[i]);

			if (tmpN[i] == 0) {
				ans = ans.replaceFirst(" ", "");
			} else if (tmpN[i] <= 26) {
				// sb.append((char) (tmpN[i]));
				tmpN[i] += 64;
				ans = ans.replaceFirst((char) (tmpN[i]) + "", "");
			} else if (tmpN[i] <= 52 && tmpN[i] > 26) {
				tmpN[i] += 70;
				ans = ans.replaceFirst((char) (tmpN[i]) + "", "");
			}

		}

		if (ans.length() == 0) {
			System.out.println("y");
		} else {
			System.out.println("n");
		}

	}
}

djm03178 4년 전 0

반복문이 하나인 것처럼 보이지만 사실 17, 21, 24번째 줄은 실행될 때마다 새로운 String 객체를 만들고 전체 문자열을 복사한 뒤 작업을 수행하기 때문에 결국 문자열의 길이에 비례하는 시간을 소요하게 됩니다. 그래서 반복문 전체는 길의의 제곱에 비례하는 시간을 소요하게 됩니다.

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

문제

문제

출처

ICPC

17176번 시간초과 해결...

99waterk 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말