글 읽기 - 시간초과의 늪에서 살려주세요...

le_effort 4년 전 0

반복문을 최대한 적게 쓰려고 해도 어떻게 해야 할 지 모르겠습니다 ㅠㅠㅠ

도움좀 주시면 감사하겠습니다 ㅠㅠㅠ

import java.util.*;
import java.io.*;
public class Main {
	static StringBuilder sb = new StringBuilder();
	
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      LinkedList <Integer>que = new LinkedList<>();
      int test_case = Integer.parseInt(br.readLine());

      for(int i=0; i<test_case ;i++) {
    	  int cnt=2;
    	  que.clear();
    	  /////////////////입력//////////////////
    	  String[] order = br.readLine().split("");	//명령 종류
    	  int n = Integer.parseInt(br.readLine());//배열개수
    	  String input[] = br.readLine().replaceAll("[\\[\\]]","").split(","); //배열에 들어갈 값
    	  ////////////////입력///////////////////////
    	  for(int j=0; j<n; j++) {
    		  que.offer(Integer.parseInt(input[j]));
    	  }
    
    	  	//정해진 숫자를 큐에 넣는 과정 끝
    	  
    	  for(int k=0; k<order.length;k++) {	//p도 10만까지
    		  if(order[k].equals("R")) {
    			  cnt++;
    		  }
    		  else if(order[k].equals("D")) {
    			  if(que.isEmpty()) {
    				  break ;
    			  }
    			  else{
    				  if(cnt%2!=0)
    				  que.removeLast();
    			  
    			  else {
    				  que.removeFirst();
    			  }
    			 }
    		  }
    	  }
    	  sibal(que,cnt);
}
    	  
   
      System.out.println(sb.toString());
   }
   public static boolean isNumeric(String s) {
	   try {
	       Double.parseDouble(s);
	       return true;
	   } catch(NumberFormatException e) {
	       return false;
	   }
	 }
   public static void sibal(LinkedList<Integer> que,int cnt) {
	   if(!que.isEmpty()) {
 		  if(cnt%2 ==0) {
 			  sb.append("[");
 		  for(int a=0; a<que.size(); a++) {
 			  if(a+1==que.size()) {
 				  sb.append(que.get(a));
 			  }
 			  else {
 				  sb.append(que.get(a)+",");
 			  }
 		  }
 		  sb.append("]"+"\n");
 		  }
 		  else {
 			  sb.append("[");
 			  for(int b=que.size()-1; b>=0; b--) {
 				  if(b==0) {
 					  sb.append(que.get(b));
 				  }
 				  else {
 				  sb.append(que.get(b)+",");
 				  }
 			  }
 			  sb.append("]"+"\n");
 		  }  
 	  }
 	  
 	  else {
 		  sb.append("error"+"\n");
 	  }
 	  
   }
   }

cjstjdgur123 4년 전 0

LinkedList 클래스 get() 함수 시간복잡도는 O(N)이라고합니다.

최악의 경우 N은 70만 정도될 수 있고, size(=N)만큼 get() 함수를 호출하면

O(70만 * 70만)번의 반복을 행하게되므로 pop 하여 출력하는 방식을 추천드립니다.

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

문제

문제

출처

ICPC

시간초과의 늪에서 살려주세요...

le_effort 4년 전 0

cjstjdgur123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말