글 읽기 - 자바 시간초과...

ljo950924 4년 전 0

아무리 줄여봐도 시간 초과가 납니다..

어느 부분이 잘못된건가요

혹은 어느 부분을 줄일 수 있을가요?

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {

	static class Tree{
		int x, y, z;
		Tree(int x, int y, int z){
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
	
	static class Pos{
		int x, y;
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	static int N,M,K;
	static int[][] arr;
	static int[][] A;
	static List<Tree> tree = new LinkedList<>();
	static int[] di= {-1,-1,-1,0,0,1,1,1};
	static int[] dj= {-1,0,1,-1,1,-1,0,1};
	
	static void solve() {
		Tree cur;
		int size;	// 나무 개수
		int[][] dies = new int[N+1][N+1];    // 죽은 나무
		List<Tree> newTree = new LinkedList<>();    // 새로운 나무
		
		while(K-->0) {
			// 봄 & 가을
			size = tree.size();
			
			for(int i=0; i<size; i++) {
				cur = tree.get(i);
				int x = cur.x;
				int y = cur.y;
				int z = cur.z;
				
				// 양분 먹기
				if(arr[x][y]>= z) {
					arr[x][y] -= z;
					cur.z++;

					// 번식
					if(cur.z%5==0) {
						int nx,ny;
						for(int k=0; k<8; k++) {
							nx = x+di[k];
							ny = y+dj[k];
							
							if(nx==0 || ny==0 || nx>N || ny>N) continue;
							
							newTree.add(new Tree(nx,ny,1));
						}
					}
					
				} else {
					// 제거
					dies[x][y] += z/2;
					tree.remove(i);
					size--;
					i--;	
				}
			}
		
			tree.addAll(0, newTree);
			newTree.clear();

			// 여름 & 겨울
			for(int i=1; i<=N; i++){
				for(int j=1; j<=N; j++) {
					arr[i][j]+=A[i][j];
					arr[i][j]+=dies[i][j];
					dies[i][j]=0;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		N=scan.nextInt();
		M=scan.nextInt();
		K=scan.nextInt();
		arr = new int[N+1][N+1];
		A = new int[N+1][N+1];
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				arr[i][j]=5;
				A[i][j] = scan.nextInt();
			}
		}
		
		for(int i=1; i<=M; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			int z = scan.nextInt();
			tree.add(new Tree(x,y,z));
		}
		
		// 크기 순 정렬
		tree.sort(new Comparator<Tree>() {
			public int compare(Tree t1, Tree t2) {
				return t1.z - t2.z;
			}
		});
		
		solve();
		
		System.out.println(tree.size());
		
	}

}

kum4950 4년 전 0

링크드리스트를 사용하셨는데,

43 번 줄에 get 메소드로 인덱스를 이용해서 조회하셨잖아요?

링크드리스트에서 get 메소드 사용하면 0번부터 링크타고 찾기때문에 O(N) 시간복잡도가 발생됩니다.

그래서 링크드리스트에서는 iterator 를 사용해주시는게 좋아요,,,

package algo;
import java.io.FileInputStream;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {

	static class Tree{
		int x, y, z;
		Tree(int x, int y, int z){
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
	
	static class Pos{
		int x, y;
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	static int N,M,K;
	static int[][] arr;
	static int[][] A;
	static List<Tree> tree = new LinkedList<>();
	static int[] di= {-1,-1,-1,0,0,1,1,1};
	static int[] dj= {-1,0,1,-1,1,-1,0,1};
	
	static void solve() {
		Tree cur;
		int size;	// 나무 개수
		int[][] dies = new int[N+1][N+1];    // 죽은 나무
		List<Tree> newTree = new LinkedList<>();    // 새로운 나무
		
		while(K-->0) {
			// 봄 & 가을
			size = tree.size();
			
			for(Iterator<Tree> it = tree.iterator(); it.hasNext(); ) {
				cur = it.next();
				int x = cur.x;
				int y = cur.y;
				int z = cur.z;
				
				// 양분 먹기
				if(arr[x][y]>= z) {
					arr[x][y] -= z;
					cur.z++;

					// 번식
					if(cur.z%5==0) {
						int nx,ny;
						for(int k=0; k<8; k++) {
							nx = x+di[k];
							ny = y+dj[k];
							
							if(nx==0 || ny==0 || nx>N || ny>N) continue;
							
							newTree.add(new Tree(nx,ny,1));
						}
					}
					
				} else {
					// 제거
					dies[x][y] += z/2;
					it.remove();
					size--;
				}
			}
		
			tree.addAll(0, newTree);
			newTree.clear();

			// 여름 & 겨울
			for(int i=1; i<=N; i++){
				for(int j=1; j<=N; j++) {
					arr[i][j]+=A[i][j];
					arr[i][j]+=dies[i][j];
					dies[i][j]=0;
				}
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		
		System.setIn(new FileInputStream("res/input"));
		Scanner scan = new Scanner(System.in);
		
		N=scan.nextInt();
		M=scan.nextInt();
		K=scan.nextInt();
		arr = new int[N+1][N+1];
		A = new int[N+1][N+1];
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				arr[i][j]=5;
				A[i][j] = scan.nextInt();
			}
		}
		
		for(int i=1; i<=M; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			int z = scan.nextInt();
			tree.add(new Tree(x,y,z));
		}
		
		// 크기 순 정렬
		tree.sort(new Comparator<Tree>() {
			public int compare(Tree t1, Tree t2) {
				return t1.z - t2.z;
			}
		});
		
		solve();
		
		System.out.println(tree.size());
		
	}

}

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

문제

문제

출처

ICPC

자바 시간초과...

ljo950924 4년 전 0

kum4950 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말