글 읽기 - JAVA List차이점과 Comparalbe 질문드립니당 !

cocobino 5년 전 0

<문제에 봄에 나무가 한곳에 여러곳 있을경우 어린나무부터 양분을 먹게되있어서>

다음과같이 봄함수에 Comparable를 활용해 year 기준으로 오름차순 정렬을 한후

Collections.sort(tree.get(x).get(y)); 을 사용하여 양분을 먹게 하였습니다. 헌데 TEST_CASE가 커지면 어긋나게 됩니다.

그래서 저는 가을에 다음과같이 add 0번인덱스에 1살나무를 추가해주는 방식으로 했습니다.

tree.get(nx).get(ny).add(0,new Tree(nx,ny,1,true));

위방식으로 푸니 정답은 맞았는데 가을에 나무가 추가될떄 앞에서 더해주는 방법이 아니라

봄에 나무가 영야분을 먹기전에 year을 기준으로 하는 정렬 설정이 잘못된거일까요 ??

아니면제가 comareTo 함수를 잘못사용한거일까요? 옳바른 사용법을 알고싶습니다.

2. LinkedList 를 사용하면 시간 초과가 났는데 ArrayList 차이점도 궁금합니다.

고수님들 부탁드립니다 !!

static ArrayList<ArrayList<ArrayList<Tree>>> tree = new ArrayList<>();

class Tree implements Comparable<Tree>{
	int x,y,year;
	boolean live;
	public Tree(int x, int y, int year, boolean live) {
		// TODO Auto-generated constructor stub
		this.x=x;
		this.y=y;
		this.year=year;
		this.live=live;
	}
    
    // Collections.sort(tree.get(x).get(y)); 시tree 를 기준으로 오름차순 정렬
	@Override
	public int compareTo(Tree o) {
		// TODO Auto-generated method stub
		return this.year < o.year ? -1 : 1 ;
	}
 

    
    
    /*
    아래는 전체 소스 코드입니다.
    */
    
    import java.awt.List;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	 
	static int n,m,k;
	static int map[][],add[][];
	static ArrayList<ArrayList<ArrayList<Tree>>> tree = new ArrayList<>();
	
	static int dx[] = {0, 0,-1, 1, 1,1,-1,-1};
	static int dy[] = {1,-1, 0, 0,-1,1, 1,-1};
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		 st = new StringTokenizer(br.readLine());
		 n = Integer.parseInt(st.nextToken()); //행열
		 m = Integer.parseInt(st.nextToken()); // m개 나무
		 k = Integer.parseInt(st.nextToken()); //k 년도후
		 
		 map = new int [n][n];
		 add = new int [n][n];
		 
		 for(int i=0; i<n; i++) {
			 tree.add(new ArrayList<>());
			 for(int j=0; j<n; j++) {
				 tree.get(i).add(new ArrayList<Tree>());
			 }
		 }
		 
		 for(int i=0; i<n; i++) {
			 st= new StringTokenizer(br.readLine());
			 for(int j=0; j<n; j++) {
				 add[i][j] = Integer.parseInt(st.nextToken());
			 }
		 }//insert
		 
		 
		 
		 for(int i=0; i<m; i++) {
			 st = new StringTokenizer(br.readLine());
			 int x= Integer.parseInt(st.nextToken())-1;
			 int y = Integer.parseInt(st.nextToken())-1;
			 int year = Integer.parseInt(st.nextToken());	 
			 
			tree.get(x).get(y).add(new Tree(x,y,year,true));
			 
		 }//insert tree 
		
		 for(int i=0; i<n; i++)Arrays.fill(map[i], 5);
		 
		 /*
		  * sol : simulation
		  */
		 
		 for(int i=0; i<k; i++) {
			 Spring();
			 summer();
			 fall();
			 winter();
		 }
		 
		 //print
		 int rst=0;
		 for(int i=0; i<n; i++) {
			 for(int j=0; j<n; j++) {
				 rst += tree.get(i).get(j).size();
			 }
		 }
		 
		bw.write(String.valueOf(rst));
		bw.flush();
		
	}// main

	private static void winter() {
		// TODO Auto-generated method stub
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				map[i][j]+=add[i][j];
	}

	private static void fall() {
		// TODO Auto-generated method stub
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				//나무나이 %5 ==0 이면 번식하기
				if(tree.get(i).get(j).size() !=0) {
					for(int k=0; k<tree.get(i).get(j).size(); k++) {
						if(tree.get(i).get(j).get(k).year %5 ==0) {
							addTree(i,j);
						}
					}
				}
			}
		}
	}

	private static void addTree(int x, int y) {
		// TODO Auto-generated method stub
		for(int i=0; i<8; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			//범위안
			if(nx>=0 && ny>=0 && nx<n && ny<n) {
			tree.get(nx).get(ny).add(0,new Tree(nx,ny,1,true));	
			}
			
		}
	}

	private static void summer() {
		// TODO Auto-generated method stub
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				//나무가 해당 위치에 있따면
				if(tree.get(i).get(j).size() !=0) {
					for(int k=0; k<tree.get(i).get(j).size(); k++) {
						//나무가 죽었으면
						if(tree.get(i).get(j).get(k).live==false) {
							//땅에 영양공급
							 map[i][j] +=tree.get(i).get(j).get(k).year/2;
							 //이후 제거
							 tree.get(i).get(j).remove(k);
							 k--;
						}
					}
				}
			}
		}
		
	}

	private static void Spring() {
		// TODO Auto-generated method stub
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				//나무가 해당위치에 있다면
				if(tree.get(i).get(j).size() !=0) {
					for(int k=0; k<tree.get(i).get(j).size(); k++) {
                        /*질문 드렸던 부분*/
						Collections.sort(tree.get(i).get(j));
						// 트리 나이보다 양분이 크면 양분없애고  => 나이 ++
						if(map[i][j] >=tree.get(i).get(j).get(k).year && tree.get(i).get(j).get(k).live) {
							map[i][j] -=tree.get(i).get(j).get(k).year;
							tree.get(i).get(j).get(k).year++;
						}else if(map[i][j] <tree.get(i).get(j).get(k).year && tree.get(i).get(j).get(k).live){
							//트리 나이보다 양분이 작으면
							tree.get(i).get(j).get(k).live=false;	
							
						}
					}
				}
			}
		}
	}// func : Spring
 

}// class
 

class Tree implements Comparable<Tree>{
	int x,y,year;
	boolean live;
	public Tree(int x, int y, int year, boolean live) {
		// TODO Auto-generated constructor stub
		this.x=x;
		this.y=y;
		this.year=year;
		this.live=live;
	}
	@Override
	public int compareTo(Tree o) {
		// TODO Auto-generated method stub
		return this.year < o.year ? -1 : 1 ;
	}
 
}
    

bupjae 5년 전 1

compareTo 를 잘못 구현하셨습니다.

예를 들어 tree1.year = 1 이고 tree2.year = 1 라고 가정하면

지금 구현하신 대로라면 tree1.compareTo(tree2) == 1, tree2.compareTo(tree1) == 1 이 됩니다.

이는 compareTo 의 계약조건인 sgn(tree1.compareTo(tree2)) == -sgn(tree2.compareTo(tree1)) 을 어긴게 됩니다.

관련된 API 문서를 자세히 읽어보세요.

Java 표준 라이브러리 에서는 잘못 구현된 compareTo 때문에 정렬 등을 할 수 없다고 판단되면 runtime error 를 발생시킬 수도 있습니다.

bupjae 5년 전 1

runtime error 가 발생되지 않았더라도, 원하는대로 정렬되지 않을 가능성이 매우 큽니다.

bupjae 5년 전 1

2번쨰 질문은

LinkedList 와 ArrayList 는 사용하는 내부 자료구조가 다릅니다. 클래스 이름을 보면 알 수 있듯이 LinkedList 는 링크리스트를 사용하고 ArrayList는 배열을 사용합니다.

예를 들어 배열 정중앙에 있는 원소가 무엇인지 알아보는 건 LinkedList는 O(n), ArrayList는 O(1) 의 시간복잡도를 가지고

그렇게 찾아낸 위치에 있는 원소를 삭제하는 건 LinkedList는 O(1), ArrayList는 O(n)의 시간복잡도를 가집니다.

전혀 다른 자료구조이기 때문에, 사용하고 있는 알고리즘이 어느 자료구조를 쓰는게 더 적합한지를 먼저 따져봐야 할 것입니다.

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

문제

문제

출처

ICPC

JAVA List차이점과 Comparalbe 질문드립니당 !

cocobino 5년 전 0

bupjae 5년 전 1

bupjae 5년 전 1

bupjae 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말