[Algorithm] 백준 알고리즘 2983번 개구리 공주

문제 : https://www.acmicpc.net/problem/2983

Github : https://github.com/ddulhddul/algorithm/blob/master/src/Baekjoon2983.java

1. x+y 와 x-y 의 케이스로 나눠 각각의 케이스 탐색

2. 시간초과로 실패...

소스코드

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

/*



 */

public class Baekjoon2983 {
//class Main {
	
	static double initX = 0;
	static double initY = 0;
	
	public static void main(String[] args) 
			throws IOException 
	{

//		long start = System.currentTimeMillis();
		
		FileReader fr = new FileReader("D:\\dev\\worksspace\\Solution\\src\\Baekjoon2983");
//		InputStreamReader fr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(fr);
		String s = null;
		
		while ((s=br.readLine())!=null) {
			int N = Integer.parseInt(s.split(" ")[0]);
			int K = Integer.parseInt(s.split(" ")[1]);
			
			String jumpStr = br.readLine();
			
			String[] jumbIndex = null; 
			double X;
			double Y;
			double xySumTemp;
			double xMinusYTemp;
			
			HashMap<Double, ArrayList<Double>> xySum = new HashMap<Double, ArrayList<Double>>();
			HashMap<Double, ArrayList<Double>> xMinusY = new HashMap<Double, ArrayList<Double>>();
			
			initX = 0;
			initY = 0;
			for (int i = 0; i < N; i++) {
				jumbIndex = br.readLine().split(" ");
				X = Double.parseDouble(jumbIndex[0]);
				Y = Double.parseDouble(jumbIndex[1]);
				if(initX == 0) initX = X; 
				if(initY == 0) initY = Y; 
				
				xySumTemp = X+Y;
				xMinusYTemp = X-Y;
				if(xySum.get(xySumTemp) == null){
					ArrayList<Double> tempList = new ArrayList<Double>();
					tempList.add(X);
					xySum.put(xySumTemp, tempList);
				}else{
					xySum.get(xySumTemp).add(X);
				}
				
				if(xMinusY.get(xMinusYTemp) == null){
					ArrayList<Double> tempList = new ArrayList<Double>();
					tempList.add(X);
					xMinusY.put(xMinusYTemp, tempList);
				}else{
					xMinusY.get(xMinusYTemp).add(X);
				}
			}
			
			String gubun = null;
			
			for (int i = 0; i < jumpStr.length(); i++) {
				double nextX = 0;
				double nextY = 0;
				gubun = jumpStr.substring(i, i+1);
				int index = -1;
				
				double tempXMinusY = initX-initY;
				double tempXPlusY = initX+initY;
				double diffWithX = 1000000001;
				boolean tb;
				
				if("A".equals(gubun)){
					
					ArrayList<Double> tempList = xMinusY.get(tempXMinusY);
					for (int j = 0; j < tempList.size(); j++) {
						double tempJ = tempList.get(j);
						if(tempJ > initX && (tempJ-initX < diffWithX)){
							nextX = tempJ;
							nextY = tempJ-tempXMinusY;
							diffWithX = tempJ-initX;
							index = j;
						}
					}
					if(nextX != 0){
						tb = xMinusY.get(tempXMinusY).remove(initX);
						tb = xySum.get(tempXPlusY).remove(initX);
						initX = nextX;
						initY = nextY;
					}
					
				}else if("D".equals(gubun)){
					
					ArrayList<Double> tempList = xMinusY.get(tempXMinusY);
					for (int j = 0; j < tempList.size(); j++) {
						double tempJ = tempList.get(j);
						if(tempJ < initX && (initX-tempJ < diffWithX)){
							nextX = tempJ;
							nextY = tempJ-tempXMinusY;
							diffWithX = initX-tempJ;
							index = j;
						}
					}
					if(nextX != 0){
						tb = xMinusY.get(tempXMinusY).remove(initX);
						tb = xySum.get(tempXPlusY).remove(initX);
						initX = nextX;
						initY = nextY;
					}
				}else if("B".equals(gubun)){  //(x+P, y-P)
					
					ArrayList<Double> tempList = xySum.get(tempXPlusY);
					for (int j = 0; j < tempList.size(); j++) {
						double tempJ = tempList.get(j);
						if(tempJ > initX && (tempJ-initX < diffWithX)){
							nextX = tempJ;
							nextY = tempXPlusY-tempJ;
							diffWithX = tempJ-initX;
							index = j;
						}
					}
					if(nextX != 0){
						tb = xMinusY.get(tempXMinusY).remove(initX);
						tb = xySum.get(tempXPlusY).remove(initX);
						initX = nextX;
						initY = nextY;
					}
				}else if("C".equals(gubun)){  //(x-P, y+P)
					
					ArrayList<Double> tempList = xySum.get(tempXPlusY);
					for (int j = 0; j < tempList.size(); j++) {
						double tempJ = tempList.get(j);
						if(initX > tempJ && (initX-tempJ < diffWithX)){
							nextX = tempJ;
							nextY = tempXPlusY-tempJ;
							diffWithX = initX-tempJ;
							index = j;
						}
					}
					if(nextX != 0){
						tb = xMinusY.get(tempXMinusY).remove(initX);
						tb = xySum.get(tempXPlusY).remove(initX);
						initX = nextX;
						initY = nextY;
					}
				}
			}
			
		}
		System.out.println((int)initX+" "+(int)initY);
		
//		long end = System.currentTimeMillis();
//		System.out.println("time "+ (end-start)/1000.0);
	}
}