글 읽기 - 시간초과 해결 방법...ㅠㅠ

jihea37 7년 전 0

bfs를 이용해 풀었습니다.

시간초과가 나네요...

불필요한 부분이 없어보이는데 어디를 줄여야할까요?

mem같은경우는 방문했는지 여부를 판단하기 위해서 만들었습니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
	String str;
	int count;
}

class Main {

	static HashMap<String, Integer> hash = new HashMap<String, Integer>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt(); // testcase

		for (int tt = 0; tt < t; tt++) {
			String a = sc.next();
			String b = sc.next();

			// 두 문자열의 다른 부분 찾기
			int left = 0;
			int right = a.length() - 1;

			for (left = 0; left < a.length(); left++) {
				if (a.charAt(left) != b.charAt(left)) {
					break;
				}
			}
			if (left == a.length()) {
				System.out.println("0");
				continue;
			}
			// System.out.println(left);

			for (right = a.length() - 1; right >= 0; right--) {
				if (a.charAt(right) != b.charAt(right)) {
					break;
				}
			}
			// System.out.println(right);

			a = a.substring(left, right + 1);
			b = b.substring(left, right + 1);

			LinkedList<String> queue = new LinkedList<String>();
			ArrayList<String> mem = new ArrayList<String>();

			queue.add(a);
			mem.add(a);
			hash.put(a, 0);

			while (!queue.isEmpty()) {
				String tmp = queue.poll();
				int count = hash.get(tmp);
				// System.out.println("tmp = "+tmp);

				if (tmp.equals(b)) {
					break;
				}

				for (int i = 0; i < tmp.length() - 1; i++) {
					if (tmp.charAt(i) != tmp.charAt(i + 1)) {
						String newStr = tmp.substring(0, i) + tmp.charAt(i + 1)
								+ tmp.charAt(i) + tmp.substring(i + 2);
						if (!mem.contains(newStr)) {
							queue.add(newStr);
							mem.add(newStr);
							hash.put(newStr, count + 1);
						}
					}
				}
			}

			if (hash.containsKey(b)) {
				System.out.println(hash.get(b));
			} else {
				System.out.println("-1");
			}
		}
	}
}

ljh6274 7년 전 0

제가 한 방법은 그다지 효율적이진 못하지만, i번째 문자가 변경 해야할 문자와 다르면 i+1~n까지 중 바꿔야할 문자로 처음 발견되는 위치의 문자를 가져오는 식으로 구현 했습니다.

C++로 약 300ms가 나오긴 했지만 통과 받았네요, bfs로는 문자열의 경우의 수가 워낙 많아서 통과가 힘들듯 하네요..

일단은 이렇게 통과하시고 다른분들 코드 보시는걸 추천 드립니다.

nisroeld99 7년 전 1

버블소트의 특징을 이해하시면 acc받으실수있을겁니다.

dtc03012 7년 전 1

제가 푼 방법은 b를 기준으로 잡고 첫번째 두번째 스트링에서 b가 이동할 수 있는 거리의 합을 구했습니다.

왜냐하면 b가 어떻게 이동하든 항상 좋은 문자열이기 때문입니다.

comseung18 1년 전 0

b 가 어떻게 이동하든 항상 좋은 문자열인 것은 아닙니다.

ababab

일 때 가운데 "ab" 를 바꾸면

abbaab 가 되어 좋은 문자열이 아니게 됩니다.

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

문제

문제

출처

ICPC

시간초과 해결 방법...ㅠㅠ

jihea37 7년 전 0

ljh6274 7년 전 0

nisroeld99 7년 전 1

dtc03012 7년 전 1

comseung18 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말