글 읽기 - 시간초과관련 코드 확인 부탁드립니다.

tjtjdgur34 7년 전 0

일부로 배열로 만들면 시관초과 및 런타임 에러가 발생할 것 같아서 안만들었는데... 시간초과가 뜨네요.... 어느 부분이 잘못된걸까요...

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int L, N, count, j, circuit;
	static int flag = 0;
	static int[] changeN;
	static String[] changeD;
	static ArrayList<Point> bang = new ArrayList<>();
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		L = scan.nextInt();
		N = scan.nextInt();
		changeN = new int[N];
		changeD = new String[N];
		
		for(int i = 0; i < N; i++) {
			changeN[i] = scan.nextInt();
			//scan.nextLine();
			changeD[i] = scan.next();
		}
		
		Point p = new Point(0,0);
		bang.add(p);
		while(true) {
			//진행카운트
			if(circuit == changeN[j]) {
				changeDirection(changeD[j]);
				circuit = 0;
				j++;
			}
			//다음거 충돌 확인
			if(collision(p)) {
				circuit++;
				p = move(p);
			}
			else	
				break;
		}
		
		System.out.println(count+1);
	}

	private static void changeDirection(String s) {
		if(s.equals("L")) {
			//System.out.println("L");
			if(flag == 0)	flag = 1;
			else if(flag == 1)	flag = 2;
			else if(flag == 2)	flag = 3;
			else	flag = 1;
		} else {
			//System.out.println("R");
			if(flag == 0)	flag = 3;
			else if(flag == 1)	flag = 0;
			else if(flag == 2)	flag = 1;
			else	flag = 2;
		}
	}
	
	private static Point move(Point p) {
		int x = p.x;
		int y = p.y;
		
		if(flag == 0)	x++;
		else if(flag == 1)	y++;
		else if(flag == 2)	x--;
		else 	y--;
		
		Point np= new Point(x, y);
		bang.add(np);
		count++;
		return np;
	}

	//충돌 여부를 확인
	private static boolean collision(Point p) {
		int x = p.x;
		int y = p.y;
		
		if(flag == 0)	x++;
		else if(flag == 1)	y++;
		else if(flag == 2)	x--;
		else 	y--;
		
		if(x == -L-1 || x == L+1 || y == -L-1 || y == L+1)
			return false;
		
		for(Point c: bang) {
			if(c.x == x && c.y == y)
				return false;
		}
		
		return true;
	}

}

kdk8361 7년 전 0

명령이 1e3, 길이가 1e8인데 한칸씩 움직일때마다 몸통 다 검사하시면 시간이 많이 걸리겠죠.

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

문제

문제

출처

ICPC

시간초과관련 코드 확인 부탁드립니다.

tjtjdgur34 7년 전 0

kdk8361 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말