[코드트리/NOVICE MID] 선두를 지켜라 3 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX_N = 1_000;
 
    static int N, M;
 
    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[] arr1 = new int[MAX_N * MAX_N + 1];    // 매 초마다 위치 기록
        int time1 = 0;
        int dist1 = 0;
 
        int[] arr2 = new int[MAX_N * MAX_N + 1];
        int time2 = 0;
        int dist2 = 0;
 
        // A가 매 초마다 서 있는 위치 기록
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int v = Integer.parseInt(st.nextToken());   // 속도
            int t = Integer.parseInt(st.nextToken());   // 시간
 
            for(int j = 0 ; j < t ; j++) {
                dist1 += v;
                arr1[++time1] = dist1;
            }
        }
 
        // B가 매 초마다 서 있는 위치 기록
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int v = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
 
            for(int j = 0 ; j < t ; j++) {
                dist2 += v;
                arr2[++time2] = dist2;
            }
        }
 
        // 선두 기록 배열 (A가 리더면 1, B가 리더면 2, 둘다 리더면 3 기록)
        int[] leader = new int[time1 + 1];  
        for(int i = 1 ; i <= time1 ; i++) {
            if(arr1[i] > arr2[i])       leader[i] = 1;
            else if(arr1[i] < arr2[i])  leader[i] = 2;
            else                        leader[i] = 3;
        }
 
        // 현재 값이 다음 값과 달라질 때마다 정답 갱신
        int cnt = 0;
        for(int i = 0 ; i < leader.length - 1 ; i++) {
            if(leader[i] != leader[i + 1]) {
                cnt++;
            }
        }
        
        System.out.println(cnt);
   }
}

 

 

🧩  해결 아이디어

• 배열 기록 (시뮬레이션)

- A,B 각각 매 초마다 어떤 위치에 있는지 값을 저장한다.

- 누가 선두에 오르는지 선두 기록 배열에 값을 저장한다. (A가 리더면 1, B가 리더면 2, 둘다 리더면 3)

 

- 선두 기록 배열을 돌면서 현재 값이 다음 값과 달라질 때마다 조합 상태가 달라지므로 정답 + 1을 한다.

 

 

---

🔺 다른 풀이들

- 매 초마다 서있는 위치 기록할 때 이렇게 배열의 기존 값을 사용해도 된다...

while(t --> 0) {
    posA[timeA] = posA[timeA - 1] + v;
    timeA++;
}

 

---

💬 느낀 점

빠르게 풉시다.. 시간 왜 이리 오래 걸려!ㅠ

 

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