글 읽기 - 어느 부분에서 시간초과가 난 걸까요 ? 3일째 막혔습니다..

anwlro0212 1년 전 0

코드에 대해 간결하게 설명해드리자면,

bfs 로 풀었고, A와 B가 같다면 bfs 종료,

이미 한 번 방문한 곳은 visited 배열을 true 로 바꿔서 방문하지 않음..

근데 왜 시간초과가 날까요? 당최 모르겠습니다..

몇몇가지 테스트를 했는데 시간이 크게 오래걸리는 경우는 없었습니다.

그래서 아마 어떤 특정 경우에는..? 성립이 안된다거나 그런 경우일 것 같은데..!!

Change 메소드 -> String 형을 int 로 변환

Append 메소드 -> DSLR 등 이어 붙이는 메소드 DSL 에 새로 R을 이어붙이는 메소드

D 메소드 -> 문제의 D 명령어

S 메소드 -> 문제의 S 명령어

L 메소드 -> 문제의 L 명령어

R 메소드 -> 문제의 R 명령어

transform 메소드 -> 3을 0003 등으로 만들어 주는 메소드

음.. 구글에 다른분들 풀이 봤을때도 크게 다른건 모르겠던데 .. 근데 차이가

다른분들은 String으로 안하고 int 형으로 비교하고 한 경우가 많더라구요

StringBufferer 의 append 메소드나 그런 걸 많이 써서 시간초과가 난 걸까요 ?

import java.io.*;
import java.util.*;
class Number{
	String number;
	String inst;
	Number(String number,String inst){
		this.number=number;
		this.inst=inst;
	}
}
public class Main{

	static int arr[];
	static int max=0;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();

		int cnt=Integer.parseInt(br.readLine());
		for(int i=0;i<cnt;i++) {
			String temp[]=br.readLine().split(" ");
			String A=transform(temp[0]);
			String B=transform(temp[1]);
			sb.append(bfs(A,B)+"\n");
		}
		System.out.println(sb);

	}
	public static String bfs(String A,String B) {
		Queue<Number> queue=new LinkedList<>();
		queue.add(new Number(A,""));
		boolean visited[]=new boolean[10000];

		while(!queue.isEmpty()) {
			Number temp=queue.poll();
			String number =temp.number;
			String inst=temp.inst;

			if(number.equals(B)) {
				return inst;
			}
			if(visited[Change(number)]==true)
				continue;

			visited[Change(number)]=true;


			queue.add(new Number(D(number),Append(inst,"D")));

			queue.add(new Number(S(number),Append(inst,"S")));

			queue.add(new Number(L(number),Append(inst,"L")));
			queue.add(new Number(R(number),Append(inst,"R")));



		}

		return "";


	}
	public static int Change(String num) { //int 형으로 반환 
		int number=Integer.parseInt(num);
		return number;
	}
	public static String Append(String inst, String word) { //문자열 이어붙이기
		StringBuffer sbr=new StringBuffer();
		sbr.append(inst);
		sbr.append(word);
		return sbr.toString();
	}

	public static String D(String A) { //D
		int num=Integer.parseInt(A);
		num*=2;
		num%=10000;
		A=Integer.toString(num);
		A=transform(A);
		return A;
	}
	public static String S(String A) { //S
		int num=Integer.parseInt(A);
		num-=1;
		if(num<0)
			num=9999;
		A=Integer.toString(num);
		A=transform(A);
		return A;
	}
	public static String L(String A) { //L
		int d1=A.charAt(0)-'0';
		int d2=A.charAt(1)-'0';
		int d3=A.charAt(2)-'0';
		int d4=A.charAt(3)-'0';

		StringBuffer sbr=new StringBuffer();
		sbr.append(d2);
		sbr.append(d3);
		sbr.append(d4);
		sbr.append(d1);

		return sbr.toString();
	}
	public static String R(String A) { //R
		int d1=A.charAt(0)-'0';
		int d2=A.charAt(1)-'0';
		int d3=A.charAt(2)-'0';
		int d4=A.charAt(3)-'0';
		StringBuffer sbr=new StringBuffer();
		sbr.append(d4);
		sbr.append(d1);
		sbr.append(d2);
		sbr.append(d3);

		return sbr.toString();
	}
	public static String transform(String word) { // 3이면 0003 등으로 만들어줌(문자 앞에 공백이면 0붙임)
		if(word.length()==4)
			return word;
		else {
			StringBuffer sbr=new StringBuffer();
			String tempWord=word;
			word="";
			for(int i=0;i<4-tempWord.length();i++) {
				sbr.append("0");
			}
			sbr.append(tempWord);
			return sbr.toString();
		}
	}
}

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

문제

문제

출처

ICPC

어느 부분에서 시간초과가 난 걸까요 ? 3일째 막혔습니다..

anwlro0212 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말