글 읽기 - 43%에서 시간 초과 부탁드립니다

gveinn 2년 전 0

제 나름대로 구조체를 사용하지 않고 풀어봤습니다.

추가로 제 코드에 대한 설명을 덧붙이자면, 나이, x좌표, y좌표를 모두 이어붙이는 방식으로 arraylist에 넣었습니다.

(예 : 32살 (7,8)에 있는 나무는 3267로 구조체에 넣음)

이렇게 했을 때 정렬하면 바로 나이 순으로 정렬된다는 점을 이용했습니다.

질문글들을 다 읽어봤는데 remove같은 경우는 arraylist에서 시간복잡도가 O(N)이라서 손해를 본다고 한 글을 봤습니다.

혹시 remove대신 다른 좋은 방법이 있을까요? 혹은 코드에서 시간복잡도를 줄일 다른 방법이 있을까요?

고수님들의 답변 기다리겠습니다. 감사합니다!

import java.io.IOException;
import java.util.*;

public class Main {
   public static void main(String[] args) throws IOException{
      Scanner kb = new Scanner(System.in);
      int N = kb.nextInt();
      int M = kb.nextInt();
      int K = kb.nextInt();
      int[][] A = new int[N][N];
      int[][] land = new int[N][N];
      for(int i = 0; i < N; i++) {
    	  for(int j = 0; j < N; j++) {
    		  A[i][j] = kb.nextInt();
    		  land[i][j] = 5;
    	  }
      }
      
      ArrayList<Integer> tree = new ArrayList<>();
      
      // tree add ( age x y )
      for(int i = 0; i < M; i++) {
    	  int x = kb.nextInt();
    	  int y = kb.nextInt();
    	  int age = kb.nextInt();
    	  tree.add(age * 100 + (x - 1) * 10 + y - 1);
      }

	  tree.sort(Comparator.reverseOrder());
      while(K > 0) {
    	  int size = tree.size();
    	  int[][] deadTree = new int[N][N];
    	  
    	  // Spring, Summer, fall
    	  for(int i = size - 1; i >= 0; i--) {
    		  int temp = tree.get(i);
    		  int age = temp / 100;
    		  temp -= age * 100;
    		  int r = temp / 10;
    		  int c = temp % 10;
    		  
    		  if(age > land[r][c]) {
    			  deadTree[r][c] += age / 2;
    			  tree.remove(i);
    			  continue;
    		  }
    		  
    		  land[r][c] -= age;
    		  age++;
    		  tree.set(i, age * 100 + r * 10 + c);
    		  
    		  if(age % 5 == 0) {
    			  for(int a = r - 1; a <= r + 1; a++) {
        			  if(a < 0 || a >= N) continue;
        			  for(int b = c - 1; b <= c + 1; b++) {
        			      if(a == r && b == c) continue;
        			      if(b < 0 || b >= N) continue;
        				  tree.add(100 + a * 10 + b);
        			  }
        		  }
    		  }
    	  }
    	  
    	  // Winter
    	  for(int i = 0; i < N; i++) {
    		  for(int j = 0; j < N; j++)
    			  land[i][j] = land[i][j] + A[i][j] + deadTree[i][j];
    	  }
    	  K--;
      }
      System.out.println(tree.size());
   }
}

martin0327 1년 전 0

새로운 나무가 추가 될 때 나무의 나이가 항상 1이라는 점(가장 어린 나무)라는 점을 이용하면 좀 더 효율적으로 구현이 가능할 것 같습니다.

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

문제

문제

출처

ICPC

43%에서 시간 초과 부탁드립니다

gveinn 2년 전 0

martin0327 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말