RPG와 쿼리(프로그래머스 Lv5)
기본 개념 설명
import java.util.*;
class Solution
{
int z_c;
int start;
int cur_point=0;
int cur_turn=0;
long quotient;
int remainder=0;
int limit;
int moving;
long temp;
int comparator;
int[] cur_node;
int[] comp_node;
Set<Integer> keys1;
Set<Integer> keys2;
Queue<int[]> queue = new LinkedList<int[]>();
HashMap<Integer,int[]> minimums = new HashMap<Integer,int[]>();
HashMap<Integer,int[]> t_p = new HashMap<Integer,int[]>();
HashMap<Integer,ArrayList<int[]>> map = new HashMap<Integer,ArrayList<int[]>>();
public ArrayList<Long> solution(int n, int z, int[][] roads, long[] queries)
{
//테스트 2(따로 추가한 테스트 케이스)
//n=5,z=7, roads =[[0, 1, 6], [0, 2, 6], [1, 3, 6], [2, 3, 5], [3, 4, 5], [4, 0, 6]]
//queries =[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
// 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
// 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
//result = [0, -1, -1, -1, -1, 2, 1, 1, -1, -1, 3, 2, 2, 2, 2, 5, 3, 3, 3, 3, 3, 3,
// 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7]
//현제 노드에서 순간이동 없이 갈 수 있는 노드의 번호, 경로를 따라 이동시 얻을수 있는 포인트를
//배열의 요소로 집어넣는다. 이후 해당 배열을 map에 추가한다.
int cur;
for(int i=0; i<roads.length; i++)
{
cur = roads[i][0];
if(map.get(cur) == null)
{
map.put(cur, new ArrayList<int[]>());
}
map.get(cur).add(new int[]{roads[i][1],roads[i][2]});
}
/*
반복문 실행후 map 출력(테스트 2)
{"0":[[1,6],[2,6]],"1":[[3,6]],"2":[[3,5]],"3":[[4,5]],"4":[[0,6]]}
*/
/*참고
Queue => First In First Out(FIFO)
Queue<int[]> queue = new LinkedList<int[]>();
Stack => First In Last Out(FILO)
Stack<int[]> stack = new Stack<int[]>();
*/
z_c = z;
//Math.pow(z, 2)의 실행결과는 double이므로, int형으로 바꿔주어야 한다.
limit = (int)Math.pow(z, 2); //(limit=z^2)
//1번 행동(처음에 순간이동 후 경로를 따라 이동하거나 ,0번 노드부터 경로를 따라 이동)을 한 경우
for(int i : map.keySet())
{
start = (i!=0) ? 1 : 0;
//queue에 들어가는 값 : 시작 노드, 소요된 턴, 포인트, 행동1로 움직인 횟수
queue.add(new int[]{i,start,0,1});
calc(i);
}
/*
위의for문 실행 후 t_p 출력(테스트 2)
=> calc(initial)에서 t_p, queue에 값 추가시 조건 : cur_point < limit
{
"22":[4,0,0,4,1],"29":[5,0,1,5,1], => z로 나눈 나머지가 1
"16":[3,0,4,3,1],"23":[4,0,0,4,1],"44":[8,0,0,8,2], => z로 나눈 나머지가 2
"10":[3,2,4,2,2],"17":[3,0,4,3,1],"38":[7,0,4,7,2],"45":[8,0,0,8,2], => z로 나눈 나머지가 3
"11":[2,0,3,2,1],"18":[4,4,3,3,2],"32":[7,2,4,6,3],"39":[7,0,4,7,2],"46":[8,0,0,8,2], => z로 나눈 나머지가 4
"5":[2,2,3,1,2],"12":[2,0,3,2,1],"33":[6,0,3,6,2],"40":[7,0,4,7,2], => z로 나눈 나머지가 5
"6":[1,0,1,1,1],"27":[6,2,3,5,3],"34":[6,0,3,6,2],"41":[8,4,3,7,3], => z로 나눈 나머지가 6
}
※"46":[8,0,0,8,2]은 0번 노드에서 5턴 동안 가만히 있은후 3번으로 이동하는 것(7턴)보다 많은 시간을 소모한다.
즉 행동 1으로 움직인 횟수는 z_c+1(=8)를 넘지 말아야 한다.
=> calc(initial)에서 t_p, queue에 값 추가시 조건 : cur_point < limit && cur_node[3]< z_c+1
{
"22":[4,0,0,4,1],"29":[5,0,1,5,1], => z로 나눈 나머지가 1
"16":[3,0,4,3,1],"23":[4,0,0,4,1], => z로 나눈 나머지가 2
"10":[3,2,4,2,2],"17":[3,0,4,3,1],"38":[7,0,4,7,2], => z로 나눈 나머지가 3
"11":[2,0,3,2,1],"18":[4,4,3,3,2],"32":[7,2,4,6,3],"39":[7,0,4,7,2], => z로 나눈 나머지가 4
"5":[2,2,3,1,2],"12":[2,0,3,2,1],"33":[6,0,3,6,2],"40":[7,0,4,7,2], => z로 나눈 나머지가 5
"6":[1,0,1,1,1],"27":[6,2,3,5,3],"34":[6,0,3,6,2],"41":[8,4,3,7,3], => z로 나눈 나머지가 6
}
위와 같은 결과가 나오게 calc() 코딩하면, 테스트6에서 시간초과가 된다.
calc()메소드 안, if(cur_point < limit && cur_node[3]< z_c+1){...}에서
조건문 끝부분에 queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});을 하는대신
아래와 같은 새로운 조건문에서 queue에 값을 추가하면 t_p를 더욱 간략하게 만들수 있다.
void calc(int initial)
{
while(queue.size() !=0)
{
...
if(map.get(cur_node[0]) != null)
{
...
for(int connect[] : map.get(cur_node[0]))
{
if(cur_point < limit && cur_node[3]< z_c+1)
{
...
↑ if(minimums.size() < z_c)
{
새 queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});
로 }
운
else
{
if(minimums.get(cur_point%z_c)[1] > cur_turn-cur_point/z_c)
{
조 queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});
건 }
문 else if(minimums.get(cur_point%z_c)[0] > cur_point)
{
queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});
}
↓ }
}
}
}
}
}
새로운 조건문 추가 후 t_p출력
{
"22":[4,0,0,4,1],
"16":[3,0,4,3,1],
"10":[3,2,4,2,2],"17":[3,0,4,3,1],
"11":[2,0,3,2,1],
"5":[2,2,3,1,2],"12":[2,0,3,2,1],
"6":[1,0,1,1,1],
}
minimums 출력결과
{"0":[28,1], "1":[22,1],"2":[16,1],"3":[17,1],"4":[11,1],"5":[12,1],"6":[6,1]}
*/
//2번 행동(=순간이동)을 1번 행동하는 중간에 하는 경우를 고려해 보자
keys1 = new HashSet<Integer>(t_p.keySet());
for(int f : keys1)
{
comp_node=t_p.get(f);
start = comp_node[3];
while(start < z_c)
{
keys2 = new HashSet<Integer>(t_p.keySet());
for(int g : keys2)
{
cur_node=t_p.get(g);
moving = (cur_node[1] == 0) ? cur_node[0]+1 : cur_node[0];
if(f+g < limit && comp_node[3]+cur_node[3]<z_c+1 && (f+g)%z_c != 0 && (t_p.get(f+g) == null || t_p.get(f+g)[0] > comp_node[0] + moving))
{
//t_p.put(f+g, new int[]{comp_node[0]+moving,cur_node[1],cur_node[2],comp_node[3]+cur_node[3]});라 하면
//moving에서 cur_node[0]+1할 경우 에러가 발생할 수 있다.
t_p.put(f+g, new int[]{comp_node[0]+moving,comp_node[1],cur_node[2],comp_node[3]+cur_node[3], comp_node[0]+moving-(f+g)/z_c});
}
}
start += comp_node[3];
}
}
/*
위의for문 실행 후 t_p 출력(테스트 2)
{
"15":[5,2,4,3,3],"22":[4,0,0,4,1],"29":[5,0,1,5,1],"36":[8,0,3,6,3], => z로 나눈 나머지가 1
"16":[3,0,4,3,1],"23":[4,0,0,4,1],"30":[7,0,3,5,3],"37":[9,0,4,7,4], => z로 나눈 나머지가 2
"10":[3,2,4,2,2],"17":[3,0,4,3,1],"24":[5,0,3,4,2],"31":[8,0,4,6,4],"38":[8,0,0,7,3], => z로 나눈 나머지가 3
"11":[2,0,3,2,1],"18":[4,0,3,3,2],"25":[8,2,4,5,5],"32":[7,0,4,6,3],"39":[8,0,0,7,3], => z로 나눈 나머지가 4
"5":[2,2,3,1,2],"12":[2,0,3,2,1],"26":[6,0,4,5,3],"33":[7,0,4,6,3],"40":[8,0,0,7,3], => z로 나눈 나머지가 5
"6":[1,0,1,1,1],"20":[6,2,4,4,4],"27":[6,0,3,5,3],"34":[6,0,3,6,2],"41":[8,0,1,7,3] => z로 나눈 나머지가 6
}
*/
ArrayList<Long> result = new ArrayList<Long>();
boolean changed = false;
for(long query : queries)
{
remainder = (int) (query % z_c);
temp = Long.MAX_VALUE;
changed = false;
quotient = query/z_c;
//query를 z_c로 나눈 나머지가 0이 아닌경우
if(remainder != 0)
{
//t_p의 key값은 limit 미만이다. 따라서 반복 횟수를 조절하기 위해
//query가 limit보다 클 경우, comparator에 limit의 값을 넣고
//그렇지 않을 경우 query를 int로 변환해 넣어준다.
comparator = (query - (long)limit > 0) ? limit : Math.toIntExact(query);
for(int i=remainder; i<=comparator; i +=z_c)
{
if(t_p.get(i) != null && t_p.get(i)[4]< temp)
{
//반복을 통해 이전에 temp에 들어 있던 값과 t_p.get(i)[4]의 값을 비교하고
//작은 값이 temp에 남게끔 만든다.
changed = true;
temp = t_p.get(i)[4];
}
}
}
//query를 z_c로 나눈 나머지가 0인 경우
else
{
changed=true;
temp = 0;
}
//changed가 false면 query에 해당하는 포인트를 못 얻는경우 이므로
//(long)-1을 반환해 주게 만든다.
temp = changed ? (quotient+temp) : -1L;
result.add(temp);
}
return result;
}
void calc(int initial)
{
while(queue.size() !=0)
{
cur_node = queue.poll();
if(map.get(cur_node[0]) != null)
{
//너비우선 탐색 알고리즘을 사용하여, 특정 노드에서 시작해 순간이동 하지 않고 이동하기 위한
//위한 최소 소요시간(turn)과 목적지에 도착시 얻어지는 포인트(point)등을 key와 value로 묶어
//t_p에 저장한다.
for(int connect[] : map.get(cur_node[0]))
{
//t_p에 cur_node[2]+connect[1]란 key를 가지고 있지 않거나, 해당 키의 vallue가
//cur_node[1]+1보다 큰 경우, t_p에 값을 넣어준다.
cur_point = cur_node[2]+connect[1];
cur_turn = cur_node[1]+1;
if(cur_point < limit && cur_node[3]< z_c+1)
{
//z_c의 나머지를 key로하고, cur_point 및 해당 포인트를 얻기위해 소요되는 턴을 value로 하는 값을 minimums에 집어넣는다.
//(단 새로 추가하려는 value의 key가 이미 minimums에 들어 있다면, 기존의 소요되는 턴과 추가하려는 값의 크기를 바교해서
//새로 넣으려는 값이 적을경우만 작업을 수행한다.)
if(minimums.get(cur_point%z_c) == null || minimums.get(cur_point%z_c)[1] > cur_turn-cur_point/z_c)
{
minimums.put(cur_point%z_c, new int[]{cur_point,cur_turn-cur_point/z_c});
}
//cur_point를 z_c나눈 나머지가 0이 아니며,
//cur_point란 key를 t_p가 가지고 있지 않거나, 있다고 하더라도, 해당key에 대응되는 value의 첫번째
//요소(=key값을 얻기위해 소요된 턴)의 값이 cur_turn보다 작을경우, t_p에 새로운 값을 추가해 준다.
if(cur_point%z_c!=0 && (t_p.get(cur_point) == null || t_p.get(cur_point)[0] > cur_turn))
{
//t_p에 들어갈 키(=key) => 획득 포인트
//t_p에 들어갈 값(=value) => 소요된 턴, 시작위치, 끝 위치, 행동1로 움직인 횟수, 연산한 값
t_p.put(cur_point,new int[]{cur_turn,initial,connect[0], cur_node[3], cur_turn-cur_point/z_c});
}
//아직 minimums에 z_c의 모든 나머지가, key값으로 들어와 있지 않은 상태
if(minimums.size() < z_c)
{
//queue에 들어가는 값 : 시작 위치, 소요된 턴, 획득 포인트, 행동1로 움직인 횟수
queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});
}
// minimums에 z_c의 모든 나머지가, key값으로 들어와 있는 상태
else
{
//minimums에서 cur_point%z_c의[1]해당하는 값(=연산한 값)이 새로 연산한 값(=cur_turn-cur_point/z_c)보다 큰 경우
//queue에 새로운 값을 추가해준다.
if(minimums.get(cur_point%z_c)[1] > cur_turn-cur_point/z_c)
{
queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});
}
//minimums에서 cur_point%z_c의[1]해당하는 값(=연산한 값)이 새로 연산한 값(=cur_turn-cur_point/z_c)보다 작거나 같을지라도
//cur_point%z_c의[1]해당하는 값(=획득 포인트)이 cur_point보다 크다면, queue에 새로운 값을 추가해준다.
else if(minimums.get(cur_point%z_c)[0] > cur_point)
{
queue.offer(new int[]{connect[0],cur_turn,cur_point, cur_node[3]+1});
}
}
}
}
}
}
}
}
실행결과
댓글남기기