글 읽기 - 덧셈 연산 하나 차이인데 시간초과가 날 수 있나요?

rkdgh98 2년 전 0

두 코드의 유일한 차이는 while문 조건입니다.

위 코드에서는 while문 종료 조건을 boxes 리스트가 비었을 경우로 두었고,

아래 코드는 while문의 종료 조건을 doneCount라는 처리된 상자 개수를 의미하는 변수가 총 상자 개수와 같아 질 때로 설정했습니다.

위 코드는 정답을 받았고, 아래 코드는 시간 초과가 발생했습니다.

요지는 아래 코드처럼 단순히 doneCount++;코드 한 줄 만으로 정답 / 시간초과가 충분히 갈릴 수 있는 상황인지 궁금합니다.

제 생각은 이 덧셈 연산이 많아봤자 상자의 최대 개수인 10000을 넘지 않는 것 같은데, 어떻게 시간초과로 갈리는 것인지 이해가 가지 않아서 질문 드립니다.

또는 그 외에 제 코드에서 시간이 많이 걸리는 부분을 지적해주시면 감사드리겠습니다.

// 정답 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static BufferedReader br;
	static BufferedWriter bw;

	static int N, M;
	static List<Integer> cranes, boxes;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		cranes = new ArrayList<>();
		int maxCrane = 0;
		for (int i = 0; i < N; i++) {
			int crane = Integer.parseInt(st.nextToken());
			maxCrane = Math.max(crane, maxCrane);
			cranes.add(crane);
		}

		M = Integer.parseInt(br.readLine());
		boxes = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int box = Integer.parseInt(st.nextToken());
			boxes.add(box);
			if (maxCrane < box) {
				bw.write(-1 + "\n");
				bw.flush();
				bw.close();
				br.close();
				return;
			}
		}

		cranes.sort(Collections.reverseOrder());
		boxes.sort(Collections.reverseOrder());


		int ans = 0;
		while (!boxes.isEmpty()) {
			for (int i = 0; i < N; i++) {
				int crane = cranes.get(i);
				for (int j = 0; j < boxes.size(); j++) {
					int box = boxes.get(j);
					if (box <= crane) {
						boxes.remove(j);
						break;
					}
				}
			}
			ans++;
		}

		bw.write(ans + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}



// 시간 초과 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static BufferedReader br;
	static BufferedWriter bw;

	static int N, M;
	static List<Integer> cranes, boxes;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		cranes = new ArrayList<>();
		int maxCrane = 0;
		for (int i = 0; i < N; i++) {
			int crane = Integer.parseInt(st.nextToken());
			maxCrane = Math.max(crane, maxCrane);
			cranes.add(crane);
		}

		M = Integer.parseInt(br.readLine());
		boxes = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int box = Integer.parseInt(st.nextToken());
			boxes.add(box);
			if (maxCrane < box) {
				bw.write(-1 + "\n");
				bw.flush();
				bw.close();
				br.close();
				return;
			}
		}

		cranes.sort(Collections.reverseOrder());
		boxes.sort(Collections.reverseOrder());

		int doneCount = 0;
		int ans = 0;
		while (doneCount != M) {
			for (int i = 0; i < N; i++) {
				int crane = cranes.get(i);
				for (int j = 0; j < boxes.size(); j++) {
					int box = boxes.get(j);
					if (box <= crane) {
						boxes.remove(j);
						doneCount++;
						break;
					}
				}
			}
			ans++;
		}

		bw.write(ans + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}

rkdgh98 2년 전 1

@kdh6429

죄송합니다만 글을 읽어봐도 잘 이해하지 못했습니다.. 추가 설명 부탁드려도 될까요?

제가 질문에 올린 두 코드 모두 같은 remove()방식을 사용하고 있습니다.

두 코드의 유일한 차이점은 시간초과가 난 코드는 doneCount라는 변수를 추가적으로 사용한다는 점입니다.

doneCount++; 연산이 많이 수행되어봤자 M의 최대 크기인 만 번인데,

단순히 만 번의 + 연산 때문에 정답과 시간초과가 갈릴 수 있는지가 궁금합니다.

같은 시간복잡도를 가진 코드를 여러 번 제출 끝에 그냥 운좋게 한 번 맞은 것인지, 아니면 진짜 +연산 횟수 때문에 시간초과가 난 것인지 확실하지 않아서 올린 질문입니다.

kdh6429 2년 전 0

모바일로 봐서 코드를 잘못본거같네요.. 피씨로 볼때 다시한번 살펴보겠습니다.

kdh6429 2년 전 1

작성하신 코드가 최적화되어 있지 않은듯 합니다. 통과하신 코드도 5초안으로 겨우 들어와있고 비슷한 복잡도이기 떄문에 해당 코드 변경 때문에 통과/실패이긴 어렵고, 최적화를 통해 시간을 단축시키는게 좋을 것 같습니다.. 예를 들어 110번째줄처럼 매번 형변환을 하는 것은 시간을 많이 쓰게됩니다.

rkdgh98 2년 전 0

감사합니다! 애초에 운좋게 하나 통과된거군요

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

문제

문제

출처

ICPC

덧셈 연산 하나 차이인데 시간초과가 날 수 있나요?

rkdgh98 2년 전 0

rkdgh98 2년 전 1

kdh6429 2년 전 0

kdh6429 2년 전 1

rkdgh98 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말