글 읽기 - 코드는 맞는것 같은데 시간초과가 떠요 ㅠㅠ

qkrtkdals1997 7년 전 0

일단 언어는 자바를 쓰고 있습니다.

제가 이클립스에서 돌렸을 때는 잘 되는 걸로 보아서 알고리즘에 문제가 있는 것 같지는 않습니다.

어느 부분을 어떻게 고쳐야 시간초과를 해결할 수 있을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
	
public class Main {
	
	static void StacktoString(Stack<Character> st,String exp){
		String result="";
		//스택 사이즈가 폭발문자열보다 작을 경우 메서드 종료
		if(st.size()<exp.length()) return;
		//스택에서 폭발문자열의 길이만큼 POP해서 result에 저장
		for(int i=0;i<exp.length();i++){
			result=st.pop()+result;
		}
		//result와 폭발문자열이 같지 않을 경우 다시 스택에 PUSH
		if(!result.equals(exp)) {
			for(int i=0;i<result.length();i++){
				st.push(result.charAt(i));	
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		//gvn:문자열, exp:폭발 문자열
		String gvn=br.readLine();
		String exp=br.readLine();
		//gvn을 입력시킬 스택 생성
		Stack<Character> st=new Stack<Character>();
		
		int i=0;
		String result="";
		//gvn을 스택에 하나씩 입력시키면서 StacktoString 메서드를 통해서 스택에 폭발문자열이 존재하는지 확인
		while(i<gvn.length()){
			st.push(gvn.charAt(i++));
			StacktoString(st,exp);
		}
		//폭발과정이 끝난후, 스택에 있는 값들을 result 문자열에 저장
		while(!st.isEmpty()){
			result=st.pop()+result;
		}
		//문자열의 사이즈가 0이면 FRULA 출력
		if(result.isEmpty())bw.write("FRULA");
		//아니면 그대로 출력
		else bw.write(result);
		
		bw.close();
		br.close();
	}
}

pichulia 7년 전 0

  while(!st.isEmpty()){
   result=st.pop()+result;
  }

문제가 된 부분은 아마 이부분이라고 생각합니다.

java.util.Stack이 아니라 그냥 배열을 쓰는 것이 어떨까요?

qkrtkdals1997 7년 전 0

그런데 다른 분들의 글을 보니깐 스택을 이용해야 시간 초과를 해결할 수 있다고 하더라구요..그리고 배열보다는 덜 익숙한 스택을 연습해보고 싶기도 했고요

스택보다 배열을 쓰면 빠른가요?

qkrtkdals1997 7년 전 0

배열을 쓰면 오히려 인덱스 하나하나 불러와야되서 시간이 더 많이 걸리지 않나요?

pichulia 7년 전 0

인덱스 하나하나 불러온다는게 무슨 뜻이죠?

스택을 쓰지 말라고는 안했습니다.

java.util.Stack 을 쓰지 말라고 했죠...

아래는 "배열"로 "스택"을 구현한 모습입니다.

제가 지적했던

  while(!st.isEmpty()){
   result=st.pop()+result;
  }

이 부분에 대한 문제를 깔끔하게 해결할 수 있죠.

문자열의 concat(+) 연산자는 생각보다 오래걸립니다. 그렇기 때문에 생긴 TLE로 보여지네요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
    static String exp;
    static char[] st;
    static int stl;
    static int m;
	static void StacktoString(){
		String result="";
		//스택 사이즈가 폭발문자열보다 작을 경우 메서드 종료
		if(stl<exp.length()) return;
 		//스택에서 폭발문자열의 길이만큼 POP해서 result에 저장
		for(int i=0;i<exp.length();i++){
			result=st[stl-i-1]+result;
		}
        stl-= m;
		//result와 폭발문자열이 같지 않을 경우 다시 스택에 PUSH
		if(!result.equals(exp)) {
			for(int i=0;i<result.length();i++){
				st[stl++] = result.charAt(i);	
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        st = new char[1000009];
        stl = 0;
		//gvn:문자열, exp:폭발 문자열
		String gvn=br.readLine();
		exp=br.readLine();
		m = exp.length();
		int i=0;
        int n = gvn.length();
		String result="";
		//gvn을 스택에 하나씩 입력시키면서 StacktoString 메서드를 통해서 스택에 폭발문자열이 존재하는지 확인
		while(i<gvn.length()){
            st[stl++] = gvn.charAt(i++);
			StacktoString();
		}
		//문자열의 사이즈가 0이면 FRULA 출력
		if(stl == 0)bw.write("FRULA");
		//아니면 그대로 출력
		else {
            for(i=0;i<stl;i++)
            bw.write(st[i]);
        }
		
		bw.close();
		br.close();
	}
}

qkrtkdals1997 7년 전 0

감사합니다! 덕분에 해결했습니다! :)

배열로 스택을 구현하라는 말씀이 이런 거였군요.

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

문제

문제

출처

ICPC

코드는 맞는것 같은데 시간초과가 떠요 ㅠㅠ

qkrtkdals1997 7년 전 0

pichulia 7년 전 0

qkrtkdals1997 7년 전 0

qkrtkdals1997 7년 전 0

pichulia 7년 전 0

qkrtkdals1997 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말