글 읽기 - 속도 차이가 나는 이유가 무엇인가요?

riimy 4년 전 0

1번 코드와 2번코드에서 속도가 거의 3배 이상 나는데 왜 그런건가요?

1번코드로 풀면 맞긴 맞는데 좋은 코드는 아닌가요?

////////////////////////////////////////1번 코드//////////////////////////////////////

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int R, C, ans;
	static char[][] map;
	static boolean[][] visited;

	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static ArrayList<Character> al;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		R = scanner.nextInt();
		C = scanner.nextInt();
		map = new char[R][C];
		visited = new boolean[R][C];
		al = new ArrayList<>();

		for (int i = 0; i < R; i++) {
			map[i] = scanner.next().toCharArray();
		}

		al.add(map[0][0]);
		visited[0][0] = true;
		ans = Integer.MIN_VALUE;

		dfs(0, 0);
		System.out.println(ans);
	}

	public static void dfs(int y, int x) {
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (safe(ny, nx) && !visited[ny][nx] && !al.contains(map[ny][nx])) {
				visited[ny][nx] = true;
				al.add(map[ny][nx]);

				dfs(ny, nx);

				visited[ny][nx] = false;
				al.remove(al.size() - 1);
			}

			if (al.size() > ans) {
				ans = al.size();
			}
		}
	}

	public static boolean safe(int y, int x) {
		if (y < R && x < C && y >= 0 && x >= 0) {
			return true;
		} else {
			return false;
		}
	}
}
////////////////////////////////////////2번 코드//////////////////////////////////////

import java.io.*;
import java.util.*;

public class Main {
	static int arr[][];
	static int cnt = 1;
	static int ans = 1;
	static boolean visited[];
	static int dx[] = { 1, -1, 0, 0 };
	static int dy[] = { 0, 0, 1, -1 };
	static int r, c;
	static boolean[] check;
	static ArrayList<Integer> list = new ArrayList<>();

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		r = scanner.nextInt();
		c = scanner.nextInt();

		visited = new boolean[26];
		arr = new int[r][c];

		for (int i = 0; i < r; i++) {
			String s = scanner.next();
			for (int j = 0; j < c; j++) {
				arr[i][j] = s.charAt(j) - 'A';
			}
		}

		dfs(0, 0);
		System.out.println(ans);
	}

	public static void dfs(int y, int x) {

		visited[arr[y][x]] = true;
		for (int i = 0; i < 4; i++) {
			int ny = y + dx[i];
			int nx = x + dy[i];

			if (safe(ny, nx)) {
				if (!visited[arr[ny][nx]]) {
					cnt++;
					ans = Math.max(cnt, ans);
					dfs(ny, nx);
				}
			}
		}
		cnt--;
		visited[arr[y][x]] = false;
	}

	public static boolean safe(int y, int x) {
		if (y < r && x < c && y >= 0 && x >= 0) {
			return true;
		} else {
			return false;
		}
	}
}

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

문제

문제

출처

ICPC

속도 차이가 나는 이유가 무엇인가요?

riimy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말