글 읽기 - 시간초과 해결좀 부탁드립니다 ㅠㅠ

windy10928 3년 전 1

우선 ArrayList 에 모든 나무들을 add하여 해당 list를 탐색하며 진행합니다.

아래와 같이 소스 짰는데 시간초과가 뜹니다.

ArrayList[][] map 이렇게 해서 map의 좌표별로 ArrayList 를 받아와서 돌린 것과

map의 x,y 좌표와 상관없이 아래 처럼 하나의 ArrayList 로 돌리다 다 똑같지 않나요...?

전자 (map 좌표별로 ArrayList 받아오기) 의 경우는 시간안에 들어옵니다...

ArrayList remove 함수 호출 시에 list의 size가 커진 만큼 Shift 하는데 오래 걸려서 그런걸까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
	
	static int N,M,K;
	static ArrayList<Tree> list = new ArrayList<>();
	static int[][] map;
	static int[][] energy;
	static int[] dx = {-1,-1,-1,0,0,1,1,1};
	static int[] dy = {-1,0,1,-1,1,-1,0,1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][N+1];
		energy = new int[N+1][N+1];
		
		for (int i = 0; i <= N; i++) {
			Arrays.fill(map[i], 5);
		}
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				energy[i][j] = Integer.parseInt(st.nextToken()); 
			}
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			list.add(new Tree(x, y, z));
		}
		
		while(K-- > 0) {
            // 봄
            // 가장 최근에 생성된 (나이가 가장 어린) 순서로 탐색
			for (int i = list.size()-1; i >= 0; i--) {
				Tree t = list.get(i);
				int tx = t.x;
				int ty = t.y;
				int tz = t.z;
				if(map[tx][ty] >= tz) {
					map[tx][ty] -= tz;
					t.z++;
				}
				else {
					t.isDead = true;
				}
			}
			// 여름
			for (int i = 0; i < list.size(); i++) {
				Tree t = list.get(i);
				if(t.isDead) {
					int tx = t.x;
					int ty = t.y;
					int tz = t.z;
					map[tx][ty] += (tz/2);
					list.remove(i);
					i--;
				}
			}
            
			// 가을
			int size = list.size();
			for (int i = 0; i < size; i++) {
				Tree t = list.get(i);
				
				if(t.z % 5 != 0) continue;
				int tx = t.x;
				int ty = t.y;
				
				for (int j = 0; j < 8; j++) {
					int nx = tx + dx[j];
					int ny = ty + dy[j];
					
					if(!isRange(nx, ny)) continue;
					list.add(new Tree(nx, ny, 1));
				}
			}
            
			// 겨울
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					map[i][j] += energy[i][j];
				}
			}
		}
		System.out.println(list.size());
	}
	
	static boolean isRange (int x, int y) {
		if( x < 1 || x >= N+1 || y < 1 || y >= N+1) return false;
		return true;
	}
}

class Tree {
	int z;
	int x;
	int y;
	boolean isDead;
	
	Tree(int x, int y, int z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

shieldnet 3년 전 3

ArrayList<T> 의 remove함수의 시간복잡도는 O(N)입니다.

windy10928 3년 전 1

예상이 맞았네요 ㅠ 감사합니다.

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

문제

문제

출처

ICPC

시간초과 해결좀 부탁드립니다 ㅠㅠ

windy10928 3년 전 1

shieldnet 3년 전 3

windy10928 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말