글 읽기 - 시간초과 질문드립니다.

hwj0623 7년 전 0

L의 상한이 10^8인게 문제인지 시간초과가 자꾸나네요..

원래 링크드 리스트로 받던걸 해시셋으로 재구현해봐도 문제가 있는데 해시코드 오버라이딩하는게 서툴러서 그 문제인지 모르겠어요.

고수님들 의견부탁드립니다.

import java.util.Scanner;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class Pos extends Object {
	public int x;
	public int y;
	public int dir; // 방향 : 0: up / 1: left / 2: down / 3: right
	public Pos(int x, int y, int curDir) {
		this.x = x;
		this.y = y;
		this.dir = curDir;
	}
	public void changeDir(char a) {
		if (a == 'L') {
			this.dir = (this.dir + 1) % 4;
		} else if (a == 'R') {
			this.dir--;
			if (this.dir < 0) {
				this.dir = 3;
			}
		}
	}
	public Pos() {	}
	@Override
	public int hashCode(){
		return x+y;
	}
	@Override 
	public boolean equals(Object obj){
		if(obj instanceof Pos){
			Pos tmp = (Pos)obj;
			if(this.x == tmp.x && this.y ==tmp.y){
				return true;
			}
		}
		return false;
	}
}

public class Main {
	static int L;
	static int turn;
	static LinkedList<Pos> snake;
	static HashSet<Pos> snakeBody;
	static int dx[] = { 0, -1, 0, 1 };
	static int dy[] = { 1, 0, -1, 0 };
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		L = sc.nextInt();
		snake = new LinkedList<Pos>();
		snakeBody = new HashSet<Pos>();
		snake.addFirst(new Pos(0, 0, 3)); // right방향으로 움직이는 Pos를 넣는다.
		snakeBody.add(new Pos(0,0,3));
		turn = sc.nextInt();
		char direction[] = new char[turn];
		int time[] = new int[turn];
		for (int i = 0; i < turn; i++) {
			time[i] = sc.nextInt();
			String tmp = sc.next();
			direction[i] = tmp.charAt(0);
		}
		for (int i = 0; i < turn; i++) {
			char d = direction[i];
			int t = time[i];
			boolean x = move(d,t);	
			if(!x)break;
		}
		System.out.println(snake.size());		
	}

	public static boolean move(char direct, int time) {
	
		for (int i = time; i > 0; i--) {
			Pos tmp = snake.getFirst();//(snake.size() - 1); // 가장 최근에 입력된 tmp를 얻는다.
			Pos tmpAdd = new Pos(tmp.x+dx[tmp.dir], tmp.y+dy[tmp.dir], tmp.dir); //snake에 삽입할 Pos 생성.dir은 가장 마지막에 넣었던 방향대로
			//새로 넣을게 범위 밖이면 false
			
			if (i == 1) {
					if(snakeBody.contains(tmpAdd)){
						return false;
					}
					
					else if(tmpAdd.x>L || tmpAdd.y>L || tmpAdd.x<(-L)||tmpAdd.y<(-L)){
						return false;
					}
				
				tmpAdd.changeDir(direct);
				snake.addFirst(tmpAdd);
				snakeBody.add(tmpAdd);
			}
			else{
				if(snakeBody.contains(tmpAdd)){
					return false;
				}
				snake.addFirst(tmpAdd);
				snakeBody.add(tmpAdd);
			}
		}
		return true;
	}
}

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

hwj0623 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말