[코드트리/NOVICE MID] 좌우로 움직이는 로봇 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        int[] A = new int[1_000_001];
        int time1 = 0;
        int pos1 = 0;
 
        int[] B = new int[1_000_001];
        int time2 = 0;
        int pos2 = 0;
 
        while(N --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int  t = Integer.parseInt(st.nextToken());
            char d = st.nextToken().charAt(0);
 
            if(d == 'L') {
                while(t --> 0) {
                    A[++time1] = --pos1;
                }
            }
            else {
                while(t --> 0) {
                    A[++time1] = ++pos1;
                }                
            }         
        }
 
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int  t = Integer.parseInt(st.nextToken());
            char d = st.nextToken().charAt(0);
 
            if(d == 'L') {
                while(t --> 0) {
                    B[++time2] = --pos2;
                } 
            }
            else {
                while(t --> 0) {
                    B[++time2] = ++pos2;
                }
            }         
        }
 
        // 움직임 종료 이후에는, 같은 위치에 계속 머무르게 만들기
        if(time1 > time2) {
            for(int i = time2 + 1 ; i <= time1 ; i++) {
                B[i] = B[time2];
            }
        }
        else {
            for(int i = time1 + 1 ; i <= time2 ; i++) {
                A[i] = A[time1];
            }           
        }
 
        int cnt = 0;
        for(int i = 1 ; i <= Math.max(time1, time2) ; i++) {
            if(A[i] == B[i] && A[i -1] != B[i - 1]) {
                cnt++;
            }
        }
 
        System.out.println(cnt);
    }
}

 

 

🧩  해결 아이디어

• 배열 기록

1) A와 B 배열을 만들어 시간에 따른 위치를 저장한다.

 

2) 움직임 종료 이후에는, 같은 위치에 계속 머무르도록 한다.

 

그런데 이 때 두 배열이 이동하면서 소요된 시간이 다르므로, 

두 배열 중 시간이 덜 소요된 값의 나머지 칸은 시간이 더 많이 소요된 값의 길이만큼 마지막 값으로 채워준다.

 

3) 두 배열을 비교하며, 현재 값은 같지만 이전 값은 다른 경우의 갯수를 센다.

 

 

💥 유의사항

- 런타임 에러 : 배열 크기 주의!

 

---

🔺 다른 풀이들

- 시간 약 80ms 정도 빠르길래...

import java.io.*;
import java.util.*;

public class Main {
    static final int MAX_TIME = 1_000_000;
    static int N, M;
    static int[] A = new int[MAX_TIME+1];
    static int[] B = new int[MAX_TIME+1];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int aTime = 1;
        for(int a=0;a<N;a++){
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            char command = st.nextToken().charAt(0);
            
            if(command == 'L'){
                while(value-- > 0){
                    A[aTime] = A[aTime-1] - 1;
                    aTime++;
                }
            }
            else{
                while(value-- > 0){
                    A[aTime] = A[aTime-1] + 1;
                    aTime++;
                }
            }
        }

        int bTime = 1;
        for(int b=0;b<M;b++){
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            char command = st.nextToken().charAt(0);
            

            if(command == 'L'){
                while(value-- > 0){
                    B[bTime] = B[bTime-1] - 1;
                    bTime++;
                }
            }
            else{
                while(value-- > 0){
                    B[bTime] = B[bTime-1] + 1;
                    bTime++;
                }
            }
        }

        int time;
        if(aTime < bTime){
            time = bTime;
            for(int i=aTime;i<bTime;i++){
                A[i] = A[i-1];
            }
        }
        else{
            time = aTime;
            for(int i=bTime;i<aTime;i++){
                B[i] = B[i-1];
            }
        }

        int answer = 0;
        for(int i=1;i<time;i++){
            if(A[i] == B[i] && A[i-1] != B[i-1]) answer++;
        }
        System.out.println(answer);
    }
}

 

---

💬 느낀 점

아 어려운 문제 아닌데 시간 너무 많이 잡아먹었다ㅠ

담에는 꼭 빨리 푸는 걸로!!

 

 

1회독	2회독	3회독	4회독	5회독
V