코드트리 토끼와 경주 질문

Question

안녕하세요. 코드트리 토끼와 경주 문제에 대해서 질문이 있습니다문제: 토끼와_경주먼저 생각해본 과정과 코드는 아래와 같습니다.현재 주어진 테스트케이스는 통과하지만, 2%에서 걸리고 있습니다.어떤부분이 잘못되었는지 알려주실 수 있으신가요?토끼 클래스 {행r, 열c, 방향 dir, 이동거리 dist, 점프횟수 jump, 행+열 값 rc, 토끼번호 pid, 점수 score}경주진행 시, 네가지 방향으로 거리를 미리 계산하기 위한 distSimul 리스트(List distSimul)pid번 토끼가 참여했는지 마킹하는 boolean 배열 rabbitTurn[2001] (번호는 최대 2000 까지)토끼들을 담고 있는 리스트 List rabbits1.경주 시작 준비초기값으로 토끼 위치를 1행 1열로 잡기pid값, dist값을 넣기(입력값)토끼 리스트에 토끼 넣기2. 경주 진행1)토끼 리스트 정렬점프 오름차순 > 행+열 오름차순 > 행 오름차순 > 열 오름차순2)'1)' 에서 정렬된 토끼 중 맨 앞 토끼를 선택 (ra 토끼라고 하겠습니다)3)네가지 방향으로 ra토끼의 dist 거리만큼 이동시켜보기4)ra토끼가 이번에 참여했으므로 rabbitTurn[ra.pid] = true로 마킹해주기5)ra토끼의 4가지 방향으로 계산해본 결과가 담긴 distSimul 리스트를 rc 내림차순 > r 내림차순> c 내림차순 정렬하기6)distSimul에서 0번째 토끼(choice 토끼라고 하겠습니다) 가져오기7)choice 토끼값으로 ra토끼를 덮어써주기8)나머지 토끼들의 점수에 ra토끼의 rc값을 더해주기여기까지 k번 반복하기9)토끼리스트를 rc 내림차순 > r 내림차순> c 내림차순 > pid 내림차순 정렬해주기10)정렬된 토끼리스트에서 rabbitTurn값이 true인 경우까지 이동하기11)그 토끼가 참여한 토끼 중 9) 우선순위에 해당되는 토끼이므로, 그 토끼 점수에 s점 더해주기4. 이동거리 변경토끼리스트에서 pid값을 가진 토끼를 찾아서, 그 토끼의 dist값에 l값을 곱해주기5. 최고의 토끼 선정모든 토끼의 점수 중 최댓값을 찾아서 반환 후 종료package 토끼와경주; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.StringTokenizer; public class Main { static class Rabbit{ int r; int c; int dir; int dist; int score; int jump; int rc; int pid; public Rabbit() { super(); // TODO Auto-generated constructor stub } @Override public String toString() { return "Rabbit [r=" + r + ", c=" + c + ", dir=" + dir + ", dist=" + dist + ", score=" + score + ", jump=" + jump + ", rc=" + rc + ", pid=" + pid + "]"; } } static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int q,n,m,p,k,s,pidt,l; static List rabbits; static List distSimul; static boolean[] rabbitTurn; static int[][] dir= { {-1,0}, {1,0}, {0,-1}, {0,1} }; static int max = Integer.MIN_VALUE; public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub q = Integer.parseInt(br.readLine()); for(int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); String cmd = st.nextToken(); switch(cmd) { case "100": //경주 시작 준비 n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); p = Integer.parseInt(st.nextToken()); rabbits = new ArrayList<>(); rabbitTurn = new boolean[2001];//인덱스가 번호이므로 2000까지 고려! distSimul = new ArrayList<>(); for(int j = 0; j < p; j++) { Rabbit ra= new Rabbit(); ra.r=1; ra.c=1; ra.rc=2; ra.pid = Integer.parseInt(st.nextToken()); ra.dist = Integer.parseInt(st.nextToken()); rabbits.add(ra); } //System.out.println("rabbits: "+rabbits); break; case "200": //경주진행 k = Integer.parseInt(st.nextToken()); s = Integer.parseInt(st.nextToken()); doRace(); //System.out.println("---"); break; case "300": //이동거리 변경 pidt = Integer.parseInt(st.nextToken()); l = Integer.parseInt(st.nextToken()); for(int j = 0; j < rabbits.size(); j++) { if(rabbits.get(j).pid == pidt) { //이동거리 l배 해주기 rabbits.get(j).dist *= l; } } break; case "400": //최고의 토끼 선정 for(int j = 0; j < rabbits.size(); j++) { Rabbit rabbit = rabbits.get(j); max = Math.max(max, rabbit.score); } System.out.println(max); return; } } } //200 k s 경주진행 static void doRace() { for(int i = 0; i < k; i++) { //1.토끼 리스트 정렬(점프 오름차순-> rc 오름차순->r오름차순->c오름차순 Collections.sort(rabbits, new Comparator() { @Override public int compare(Rabbit o1, Rabbit o2) { // TODO Auto-generated method stub if(o1.jump < o2.jump) return -1; else if(o1.rc < o2.rc) return -1; else if(o1.r < o2.r) return -1; else if(o1.c < o2.c) return -1; else if(o1.pid < o2.pid) return -1;//고유번호 return 0; } }); //이동할 토끼 선택 Rabbit ra = rabbits.get(0); //System.out.println("이동할 토끼: "+ra); //4 방향으로 ra.dist만큼씩 이동 //단, 경계를 만나면 반대방향으로 1만큼 이동 distSimul = new ArrayList<>(); for(int d = 0; d < 4; d++) { Rabbit tmp = new Rabbit(); tmp.pid = ra.pid; //r,c는 계속 변동될 것(해당 방향으로 나아가기 때문) int r = ra.r; int c= ra.c; tmp.dir = d; for(int dist = 1; dist<= ra.dist; dist++) { int nr = r + dir[tmp.dir][0]; int nc = c + dir[tmp.dir][1]; if(nr < 1 || nr > n || nc < 1 || nc > m) { //경계를 벗어나면 방향을 반대로 바꾸어 이동 tmp.dir = reverseDir(tmp.dir); nr = r+dir[tmp.dir][0]; nc = c+dir[tmp.dir][1]; } //이동시키기 tmp.r = nr; tmp.c= nc; tmp.rc= nr+nc; //r도 갱신 r = nr; c= nc; } tmp.score= ra.score; tmp.jump= ra.jump+1; tmp.dist+= ra.dist;//이동거리 갱신 //System.out.println("tmp: "+tmp); //결과 저장 distSimul.add(tmp); } //토끼 이번에 참여했음 rabbitTurn[ra.pid] = true; //3. ra 토끼의 4 방향 중 우선순위 높은 것을 고르기 //rc 내림차순-> r 내림차순->c 내림차순 Collections.sort(distSimul, new Comparator() { @Override public int compare(Rabbit o1, Rabbit o2) { // TODO Auto-generated method stub if(o1.rc > o2.rc) return -1; else if(o1.r > o2.r) return -1; else if(o1.c > o2.c) return -1; return 0; } }); //System.out.println("[distSimul]: "+distSimul); //4.ra의 여러 케이스 중 우선순위에 의해 정렬된 케이스 하나 고르기 Rabbit choice = distSimul.get(0); //System.out.println("선택된 케이스: "+choice); //지금 이 선택으로 ra토끼를 이동/변경시킬 것 ra.r = choice.r; ra.c= choice.c; ra.dir= choice.dir; ra.dist = choice.dist; ra.rc = choice.rc; ra.jump++; //System.out.println("[rabbits]: "+rabbits); //rabbits 리스트에 반영시켜주어야 함 for(Rabbit rabbit: rabbits) { if(rabbit.pid == ra.pid) rabbit = ra; } //System.out.println("distSimul: "+distSimul); //5.나머지 토끼들의 점수를 ra.rc만큼 올려주기 for(int j = 0; j < rabbits.size(); j++) { Rabbit cur = rabbits.get(j); if(cur.equals(ra)) continue; cur.score+=ra.rc; } } //k번 돌음 //6.rabbitTurn==true인 토끼들 중 rc 내림차순->r 내림차순-> c 내림차순->pid 내림차순 정렬하기 Collections.sort(rabbits, new Comparator() { @Override public int compare(Rabbit o1, Rabbit o2) { // TODO Auto-generated method stub if(o1.rc > o2.rc) return -1; else if(o1.r > o2.r) return -1; else if(o1.c > o2.c) return -1; else if(o1.pid > o2.pid) return -1; return 0; } }); //6.그때의 토끼가 정말 참여한 토끼인지 확인하기 int idx = 0; while(!rabbitTurn[rabbits.get(idx).pid]) idx++; Rabbit fin = rabbits.get(idx); //System.out.println("fin: "+fin+", s: "+s); //7.그 토끼에 s점 더해주기 fin.score+=s; //System.out.println("[race]rabbits: "+rabbits+" , size: "+rabbits.size()); } //반대방향 static int reverseDir(int d) { switch(d) { case 0: return 1; case 1: return 0; case 2: return 3; case 3: return 2; } return -1;//garbage value } }

코드트리 토끼와 경주 질문

0개의 답변

Q&A 목록