[코드트리/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());
        
        // A 이동
        int[] arr1 = new int[1_000_001];
        int now1 = 0;
        int idx1 = 0;
 
        // B 이동
        int[] arr2 = new int[1_000_001];
        int now2 = 0;
        int idx2 = 0;
 
        for(int i = 0 ; i < N ; i++) {
            String[] str = br.readLine().split(" ");
            int move = Integer.parseInt(str[1]);    
 
            if(str[0].equals("R")) {
                for(int j = 0 ; j < move ; j++) {
                    arr1[++idx1] = ++now1;
                }
            }
            else {
                for(int j = 0 ; j < move ; j++) {
                    arr1[++idx1] = --now1;
                }                
            }
        }
 
        for(int i = 0 ; i < M ; i++) {
            String[] str = br.readLine().split(" ");
            int move = Integer.parseInt(str[1]);    
 
            if(str[0].equals("R")) {
                for(int j = 0 ; j < move ; j++) {
                    arr2[++idx2] = ++now2;
                }
            }
            else {
                for(int j = 0 ; j < move ; j++) {
                    arr2[++idx2] = --now2;
                }                
            }
        }
 
        // 최초로 만나는 시간 출력
        for(int i = 1 ; i <= idx1 ; i++) {
            if(arr1[i] == arr2[i]) {
                System.out.println(i);
                return;
            }
        }
 
        System.out.println(-1);
    }
}

 

 

 

🧩  해결 아이디어

• 시뮬레이션

두 배열을 이동시키면서 몇 초에 어디 위치에 있는지 따로 기록하고, 두 배열이 만나는 순간의 초를 출력한다.

두 배열이 만나지 않는다면, -1을 출력한다.

 

 

💥 유의사항

- 런타임 에러 : 배열의 크기를 1_000_001으로 !

---

🔺 다른 풀이들

나는 위치 변수 idx를 따로 만들고 업데이트하면서 위치를 저장했는데,

배열의 이전 값을 갱신하면서 현재 위치를 저장하면 되는 것이었다..

posA[timeA] = posA[timeA - 1] + 1;

import java.util.Scanner;

public class Main {
    public static final int MAX_T = 1_000_000;

    public static int n, m;
    public static int[] posA = new int[MAX_T + 1];
    public static int[] posB = new int[MAX_T + 1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        n = sc.nextInt();
        m = sc.nextInt();

        // A가 매 초마다 서있는 위치를 기록
        int timeA = 1;
        for(int i = 0; i < n; i++) {
            char d = sc.next().charAt(0); 
            int t = sc.nextInt();
            
            while(t-- > 0) {
                if(d == 'R')
                    posA[timeA] = posA[timeA - 1] + 1;
                else
                    posA[timeA] = posA[timeA - 1] - 1;
                
                timeA++;
            }
        }
        
        // B가 매 초마다 서있는 위치를 기록
        int timeB = 1;
        for(int i = 0; i < m; i++) {
            char d = sc.next().charAt(0); 
            int t = sc.nextInt();
            
            while(t-- > 0) {
                if(d == 'R')
                    posB[timeB] = posB[timeB - 1] + 1;
                else
                    posB[timeB] = posB[timeB - 1] - 1;
                
                timeB++;
            }
        }
        
        // 최초로 만나는 시간을 구합니다.
        int ans = -1;
        for(int i = 1; i < timeA; i++) {
            if(posA[i] == posB[i]) {
                ans = i;
                break;
            }
        }
        
        // 출력
        System.out.print(ans);
    }
}

 

---

💬 느낀 점

배열 기록 레쓰고..

 

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