글 읽기 - 런타임에러 원인ㅠㅠ

bluebear9699 5년 전 0

도대체 런타임 에러 오류 어디일까요ㅠㅜㅠㅠㅠ

한번만 도와주세요..ㅠㅠ

package c_3045;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
	
	static DoublyLinkedList dobleLink = new DoublyLinkedList();
	
	public static void main(String[] args) throws Exception {
			
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		String firstinput =br.readLine();
		String nodesCount[] = firstinput.split(" ");
		
		int nodes = Integer.parseInt(nodesCount[0]);
		int count = Integer.parseInt(nodesCount[1]);
	
	 String[] order= new String[count];
	
		for(int i =0; i<count; i++) {
			order[i]= br.readLine();
		}
			br.close();
		
		for(int i =0; i<nodes; i++) {
			dobleLink.addLast(i+1);
		}
		
		for(int i =0; i<count; i++) {
			String action[] = order[i].split(" ");
			change(action[0],action[1],action[2]);
		}
		
		int max=0;
		int maxindex=0;
		int[] dp = new int[nodes];// 인덱스마다 각 증가 수열의 길이//dp 배열은 증가 수열의 길이를 넣을 것이다.
		int[] array = dobleLink.toIntArr(nodes);// 인덱스마다 각 입력값
		int ans = 0;
		int k=0;
		LinkedList sequence = new LinkedList();//증가 수열 인덱스
		
		dp[0] = 1;
			
			for (int i = 1; i < nodes; i++) {
			  k=0;
			  dp[i] = 1;
			  int[] temp = new int[i+1];
			  for (int j = 0; j < i; j++) {
			    if (array[j] < array[i] && dp[j] + 1 > dp[i]) {
			      dp[i] = dp[j] + 1;
			      temp[k++] = j;
			      if(dp[j] + 1 > max) {
			    	  max = dp[j] + 1 ;
			    	  maxindex = i;
			      }
			    }
			  }
			  temp[k++] = i;
			  sequence.addLast(temp);
			}
			  
			  for(int i=1;i<nodes;i++) {
				  if (ans < dp[i]) {
				    ans = dp[i];
				  }
				}
				System.out.println(nodes - ans);
				if(maxindex > 0) {
					int[] changearr = (int[])sequence.get(maxindex-1);
					
					for(int i=0; i<changearr.length; i++) {
						array[changearr[i]]=0;
					}
				}
		
		for(int i=0; i<nodes-1; i++) {
			if(array[i] > 0 && array[i]<nodes) {
				int a=array[i];
				int b=array[i]+1;
				System.out.println("A"+" "+a+" "+b);
				}
			else if( array[i] == nodes){
				int a=array[i];
				int b=array[i]-1;
				System.out.println("B"+" "+a+" "+b);	
			}
		}
		}
	private static void change(String selection, String X, String Y) {
		int x= Integer.parseInt(X);
   		int y= Integer.parseInt(Y);
   		
		if(selection.equals("A")) {
			dobleLink.toFront(x,y);//x노드를 y노드의 앞으로 이동
		}else {
			dobleLink.toRear(x,y);//x노드를 y노드의 뒤로 이동
		}
	}
}
   class DoublyLinkedList {
    private Node head;// 첫번째 노드를 가리키는 필드,변수,참조값
    private Node tail;// 마지막 노드를 가리키는 필드,변수
    private int size = 0; // 몇개의 엘리먼트
    
    public class Node{//링크드 리스트에서는 하나의 엘리먼트가(노드)하나의 객체다
    	//그객체를 LinkedList의 innerclass로 정의
    	
        private Object data;//데이터가 저장될 변수-실제 저장값
       
        private Node next;//다음 노드를 가리키는 변수,참조값
        private Node prev;//이전 노드
        
        public Node(Object input) {//객체생성 초기화
            this.data = input;
            this.next = null;//생성시는 미정
            this.prev = null;
        }
        public String toString(){//노드의 값을 쉽게 출력위해
            return String.valueOf(this.data);
        }
    }
    
  	public void toFront(int x, int y) {
   		Object currentNodeData = remove(x);
   		addFront(y, currentNodeData);//x노드를 y노드의 앞으로 이동
   	}
    
    public void toRear(int x, int y) {
    	Object currentNodeData = remove(x);
    	addRear(y, currentNodeData);//x노드를 y노드의 뒤로 이동
   	}
    
    public void addFront(int k, Object input){// 특정 위치 값 추가
        // 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
        if(k == 1){
            addFirst(input);
        } else {
            Node temp1 = node(k).prev;
            if(temp1 == null){
            	addFirst(input);
            }
            else {
            Node temp2 = temp1.next;//k번째 노드를 temp2로 지정
        
            Node newNode = new Node(input);//새로운 노드를 생성.
            
            temp1.next = newNode;// temp1의 다음 노드로 새로운 노드를 지정
            
            newNode.next = temp2;// 새로운 노드의 다음 노드로 temp2를 지정
            
            temp2.prev = newNode;//생성노드를 temp2의 이전노드로
            
            newNode.prev = temp1;//새로운 노드의 이전 노드로 temp1
            
            size++;
            }
        }
    }
    public void addRear(int k, Object input){// 특정 위치 값 추가
        // 만약 k가 0이라면 첫번째 노드에 추가하는 것이기 때문에 addFirst를 사용합니다.
        
            Node temp1 = node(k);
           
            Node temp2 = temp1.next;//k번째 노드를 temp2로 지정
        
            Node newNode = new Node(input);//새로운 노드를 생성.
            
            temp1.next = newNode;// temp1의 다음 노드로 새로운 노드를 지정
            
            newNode.next = temp2;// 새로운 노드의 다음 노드로 temp2를 지정
            
            if (temp2 != null) {//temp2가 없었을수도 있으니
                temp2.prev = newNode;//생성노드를 temp2의 이전노드로
            }
            newNode.prev = temp1;//새로운 노드의 이전 노드로 temp1
            
            size++;
            
            if(newNode.next == null){//마지막 꼬리에 추가시 검사사항
                tail = newNode;
         //혹시나 새로운 노드의 다음 노드가 없다면 새로운 노드가 마지막 노드이기 때문에 tail로 지정.
            }
        }
 
    public void addFirst(Object input){//머리에 추가
       
        Node newNode = new Node(input);//노드를 생성
        
        newNode.next = head;//새로운 노드의 다음 노드로 해드 지정
        
        if(head != null){//처음으로 노드를 추가하는것이 아니라면
           head.prev = newNode;//새로운 노드를 헤드의 이전노드로 지정
         }
        
        head = newNode;//헤드로 새로운 노드를 지정
        size++;
        if(head.next == null){
            tail = head;
        }
    }
   
	public void addLast(Object input){//꼬리에 추가
        if(size == 0){//리스트의 노드가 하나도 없다면 첫번째 노드를 추가하는 메소드를 사용.
            addFirst(input);
        } else {//기존 노드가 하나라도 있다면 
        	Node newNode = new Node(input);
        	
            tail.next = newNode;//마지막 노드의 다음 노드로 생성한 노드를 지정.
           
            newNode.prev = tail;//생성한 노드의 이전 노드로 기존의 tail을 지정
            
            tail = newNode; //마지막 노드를 갱신.
           
            size++;//엘리먼트 개수 1 증가
        }
    }
    Node node(int data) {
    	Node searchNode=head;
        while(!(searchNode.data.equals(data))) {
        	searchNode = searchNode.next;
        }
          return searchNode;
	}
    
    public String toString() {//리스트안에 데이터 전부 출력
        if(size == 0){//리스트에 데이터가 없다면
            return "[]";
        }       
        Node temp = head;//항상 시작은 헤드 지정
        String str = "[";
        while(temp.next != null){//head의 다음 노드가 없을 때까지 반복문을 실행
            str += temp.data + ",";
            temp = temp.next;
        }//마지막 노드는 다음 노드가 없기 때문에 아래의 구문은 마지막 노드는 제외.
        str += temp.data;// 마지막 노드를 출력결과에 포함
        return str+"]";
    }
    public int[] toIntArr(int n) {
    	int [] arr= new int[n];
    	int i=0;
        Node temp = head;
        while(temp.next != null){
            arr[i++]=(int)temp.data;
        	temp = temp.next;
        }
        arr[i++]=(int)temp.data;
        return arr;
    }
    
    public Object removeFirst(){//첫번째 노드 삭제
        Node temp = head;//첫번째 노드를 temp로 지정
        head = temp.next;//head의 값을 두번째 노드로 변경.
        
        Object returnData = temp.data;//데이터 삭제 전에 리턴할 값을 임시 변수에 담자.
        
        temp = null;//null로 지정해서 가비지 컬렌션이 됨
        
        if(head != null) {
        	head.prev = null;//새로운 헤드가 됬으니 이전노드를 삭제해주는거
        }
        size--;
        
        return returnData;
    }
    
    public Object remove(int k){
    	Node todoDeleted;//삭제할 노드
    	Object returnData = null;//리턴 데이터
    	
        if(node(k).prev == null) {//삭제할려는값이 첫번째값이라면
        	todoDeleted = head;
        	returnData = todoDeleted.data;
        	head.next.prev = null;
       	 	head = head.next;
        }else {
        	 
        Node temp = node(k).prev;//삭제 노드 전 노드를 temp의 값으로 지정
        
         todoDeleted = temp.next;// 삭제 노드를 todoDeleted에 기록
        // 삭제 노드를 지금 제거하면 삭제 앞 노드와 삭제 뒤 노드를 연결할 수 없다.  
        
        temp.next = temp.next.next;
        
        if(temp.next != null) {
        	temp.next.prev = temp;//삭제노드의 후와 전을 연결
        }
        // 삭제된 데이터를 리턴하기 위해서 returnData에 데이터를 저장합니다.
         returnData = todoDeleted.data; 
        
        if(todoDeleted == tail){//삭제할려는데이터가 마지막값이라면
            tail = temp;
        }
        }
        todoDeleted = null; 
        size--;
        return returnData;
    }
	}

bupjae 5년 전 1

문제 설명에는 입력 데이터의 첫번째 줄에 N(nodes)와 M(count) 이 같이 주어진다고 되어있는데

이 프로그램은 두 줄에 걸쳐서 입력받고 있기 때문에 오류가 발생합니다.

bluebear9699 5년 전 0

런타임에러는 해결했는데 또다시 메모리 초과가 나오네요 ㅠㅠ

bupjae 5년 전 0

단순히 계산했을 때 이 프로그램의 공간복잡도는 O(n+m) 으로 지나치게 많은 메모리를 요구하고 있는 것은 아닌것 같지만

안타깝게도 Java 언어는 메모리 소모량 예측이 쉽지 않습니다.

BOJ에서는 각 언어별 특성을 어느정도 보정하기 위해서 Java의 메모리 허용량을 다른 언어의 약 2배 정도 할당하고 있지만

경우에 따라서는 그것도 충분하지 않을 때도 있는 것 같습니다.

이 프로그램의 메모리 소비량을 줄일 수 있는 몇가지 팁을 드리겠습니다.

1) 이 프로그램은 입력 데이터를 모두 배열에 저장해 두고 있는데, 실제로는 딱 한 번만 순서대로 처리하고 있습니다.

링크 리스트의 초기 상태를 만드는 27~29번째 줄을 nodes와 count를 읽은 직후로 옮기고, 입력 데이터를 따로 order 배열에 저장하는 대신에

31~33번째 줄 루프에서 한 줄씩 읽고 곧장 처리하고 버리는 식으로 하면 될 것 같습니다.

2) DoublyLinkedList 객체를 따로 N개 만들고 객체 참조를 이리저리 옮기는 것 보다는, 한번에 [N] 크기의 배열을 만들고 배열의 index로 링크를 표현하면 메모리를 절약할 수 있습니다.

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

문제

문제

출처

ICPC

런타임에러 원인ㅠㅠ

bluebear9699 5년 전 0

bupjae 5년 전 1

bluebear9699 5년 전 0

bupjae 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말