글 읽기 - 2%에서 시간초과가 납니다

dev_moon 3년 전 0

2%에서 시간초과가 납니다

무엇을 잘못했을까요?

로직은 input값 배열대로 stack에 넣다가, 폭탄문자열의 마지막 부분이 입력되면 폭탄 길이만큼 탐색을 해주는 식으로 코드를 짰습니다.

제가 생각하기엔 remove같은 함수도 안 써서

O(n*m) 시간에 끝날거라고 예상했는데 시간초과가 뜨네요;;;

궁금합니다.

package 문자열;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class back_9935문자열폭발 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> stack = new Stack<>();  
		String str = in.readLine();
		String bom = in.readLine();
		int bomLen = bom.length();
		char lastChar = bom.charAt(bom.length()-1);
		//총 길이 탐색하기
		for(int i=0; i < str.length(); i++) {
		//끝 문자열 탐색
			stack.push(str.charAt(i));
			if(stack.peek()==lastChar && stack.size()>=bomLen) {
				//갯수만큼 스택에서 빼오기
				char tmp[] = new char[bomLen];
				Stack<Character> bom_tmp = new Stack<>();
				for(int j=0; j<bomLen; j++) {
					bom_tmp.push(stack.peek());
					tmp[j] = stack.pop();
				}
				//뽑았으면 폭탄 배열과 같은지 비교하기
				boolean flag = true;
				for(int j= 0; j<bomLen; j++) {
					if(bom_tmp.pop()!= bom.charAt(j)) {
						flag = false;
						break;
					}
				}
				if(flag) {
					//똑같다면 팝 계속하기
					continue;
				}else {
					//같지 않다면 팝한거 다시 푸시하기
					for(int j=bomLen-1 ;j >= 0 ; j--) {
						stack.push(tmp[j]);
					}
				}
			}
		}
		ArrayList<Character> list = new ArrayList<>();
		if(stack.size()!=0) {
			//거꾸로 출력
			while(!stack.empty()) {
				list.add(stack.pop());
			}
			for(int i=list.size()-1; i>=0; i--) {
				System.out.print(list.get(i));
			}
		}else {
			//실패 출력
			System.out.println("FRULA");
		}
	}
}

dev_moon 3년 전 0

만약 자바로 풀었을 경우 2%에 시간 초과가 뜬다면

StringBuilder를 써보세요. 출력 시간이 오래걸려서 생긴 문제였습니다.

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

문제

문제

출처

ICPC

2%에서 시간초과가 납니다

dev_moon 3년 전 0

dev_moon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

﻿2%에서 시간초과가 납니다

dev_moon 3년 전 0

dev_moon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

2%에서 시간초과가 납니다