[코드트리/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[] arr1 = new int[1_000_001]; 
        int pos1 = 0;
        int time1 = 0;
 
        int[] arr2 = new int[1_000_001];
        int pos2 = 0;
        int time2 = 0;
 
        while(N --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int speed = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
 
            for(int j = 0 ; j < time ; j++) {
                pos1 += speed;
                arr1[++time1] = pos1;
                //System.out.println("arr1 : " + time1 + " " + pos1);
            }          
        }
 
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int speed = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
 
            for(int j = 0 ; j < time ; j++) {
                pos2 += speed;
                arr2[++time2] = pos2;
                //System.out.println("arr2 : " + time2 + " " + pos2);
            }
        }
 
        int cnt = 0;
        int[] first = new int[time1 + 1];
        for(int i = 1 ; i < first.length ; i++) {
            if(arr1[i] >= arr2[i]) {
                first[i] = 1;
            }
            else {
                first[i] = 2;
            }
       }    
       
      // 우선순위 바뀌는 시점의 갯수 세기
        for(int i = 1 ; i < time1 ; i++) {
            if(first[i] != first[i + 1]) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

 

 

🧩  해결 아이디어

• 배열 기록

1) A와 B 배열의 값을 시간에 따라 이동한 위치를 따로 기록한다.

 

2) 우선순위를 저장하는 배열 first를 하나 만든다.

 

A 배열의 값이 B 배열의 같은 위치에 있는 값보다

 ㄴ 크거나 같다면 우선순위 저장 배열에 1을,

 ㄴ작다면 우선순위 저장 배열에 2를 저장한다.

 

3) 우선순위 저장 배열을 돌면서, 값이 바뀌는 시점의 갯수를 센다. 

 

 

 

---

🔺 다른 풀이들

import java.util.Scanner;

public class Main {
    public static final int MAX_T = 1000000;
    
    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++) {
            int v = sc.nextInt();
            int t = sc.nextInt();
            
            while(t-- > 0) {
                posA[timeA] = posA[timeA - 1] + v;
                timeA++;
            }
        }
        
        // B 기록
        int timeB = 1;
        for(int i = 0; i < m; i++) {
            int v = sc.nextInt();
            int t = sc.nextInt();
            
            while(t-- > 0) {
                posB[timeB] = posB[timeB - 1] + v;
                timeB++;
            }
        }
        
        // A와 B 중 더 앞서 있는 경우 확인 (A가 리더면 1, B가 리더면 2)
        int leader = 0, ans = 0;
        for(int i = 1; i < timeA; i++) {
            if(posA[i] > posB[i]) {
                if(leader == 2)	// 기존 리더가 B였다면, 답 갱신
                    ans++;
              
                leader = 1;	// 리더를 A로 변경
            }
            else if(posA[i] < posB[i]) {
                if(leader == 1)	// 기존 리더가 A였다면, 답 갱신
                    ans++;
                
                leader = 2; // 리더를 B로 변경
            }
        }
        
        System.out.print(ans);
    }
}

 

---

💬 느낀 점

빨리 풀 수 있었는디 ..

역시 결과를 중간중간 출력해봐야 어디서 틀렸는지 알 수 있는 것 같다!

 

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