글 읽기 - 향상된 for문과 일반 for문 성능차이?

sonyjun 3년 전 0

향상된 for문과 vs 일반 for문

40~43번 줄의 일반 for문은 시간초과를..

44~46번 줄의 향상된 for문은 정답으로 인정됩니다.

두 for문의 성능차이는 얼마 안나는 걸로 알고 있는데, 이유 알고계신분 계신가요?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
/*
4
S 100 3
W 50 1
S 10 1
 */
public class Main {
	static int totalSheepNum = 0;

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int islandNum = Integer.parseInt(br.readLine());
		LinkedList<Island>[] adjList = new LinkedList[islandNum + 1];
		StringTokenizer st;
		for(int i = 1; i < adjList.length ; i ++) {
			adjList[i] = new LinkedList<Island>();
		}
		for (int i = 1; i < adjList.length - 1; i++) {
			st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();
			long count = Integer.parseInt(st.nextToken());
			int adjVertex = Integer.parseInt(st.nextToken());
			int who;
			if (temp.equals("S")) {// 양이면 고유번호 1
				who = 1;
			} else {// 늑대면 고유번호 2
				who = 2;
			}
			adjList[adjVertex].add(new Island(who, count, i + 1));
		}
		System.out.println(postOrder(adjList, new Island(0, 0, 1)));
	}

	public static long postOrder(LinkedList<Island>[] adjList, Island visitIsland) {
		long sum = 0;
		for (int i = 0; i < adjList[visitIsland.vertex].size(); i++) {
			Island adjIsland = adjList[visitIsland.vertex].get(i);
			sum += postOrder(adjList, adjIsland);
		}
		/*for (Island adjIsland : adjList[visitIsland.vertex]) {
			sum += postOrder(adjList, adjIsland);
		}*/
		
		if (visitIsland.who == 1) {// 방문한 친구가 양이라면
			return sum + visitIsland.count;
		} else {// 방문한 친구가 늑대라면, 혹은 루트라면..
			return (sum - visitIsland.count) >= 0 ? sum - visitIsland.count : 0;
		}
	}
}

class Island {
	// 1:양
	// 2:늑대
	int who;
	long count;
	int vertex;

	public Island(int who, long count, int vertex) {
		this.who = who;
		this.count = count;
		this.vertex = vertex;
	}
}

WeissBlume 3년 전 1

LinkedList의 랜덤 접근은 O(1)이 아니라 O(n)입니다. 따라서 기존 for 루프는 사실상 향상된 루프의 제곱 만큼의 시간을 소요합니다.

sonyjun 3년 전 0

아.... 이해했습니다.. 답변감사드립니다!!

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

문제

문제

출처

ICPC

향상된 for문과 일반 for문 성능차이?

sonyjun 3년 전 0

WeissBlume 3년 전 1

sonyjun 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말