만나는 그 순간 (코드트리)

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (codetree.ai)

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라.      

- 우리가 풀어야 할 문제는 무엇인가?

-> A, B가 움직임을 시작한 이후에 최초로 만나게 되는 시간은 몇 초 뒤인지 구하라

 

- 주어진 자료는 무엇인가?

-> A와 B가 어떻게 이동했는지에 관한 자료

 

- 조건은 무엇인가?

-> 1초에 1m씩 움직임

-> A가 총 이동한 시간과 B가 총 이동한 시간은 항상 동일함

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

- 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?

-> 어떤 자료구조를 사용해야 하는가?

-> 해당 초에 각각이 어느 위치에 있는지를 판단할 수 있어야 한다. 

-> 어떻게 현재의 위치를 나타낼 것인가?

-> 무엇으로 나타낼 것인가?

 

 

 

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

import java.util.*;

class Main{
    public static void main(String[] args){

        int answer = -1; 

        Scanner sc = new Scanner(System.in); 
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arrA = new int[10000010];
        int[] arrB = new int[10000010];
        int total = 0; 
        int timeA = 0; 
        int currA = 0; 
        int timeB = 0; 
        int currB = 0; 

        for(int i=0; i<N; i++){
            String str = sc.next();
            int num = sc.nextInt();
            total += num; 

            if(str.charAt(0) == 'R'){
                for(int j=0; j<num; j++){
                    arrA[++timeA] = ++currA;
                } 
            }else{
                for(int j=0; j<num; j++){
                    arrA[++timeA] = --currA;
                }    
            }
        }


        for(int i=0; i<M; i++){

            String str = sc.next();
            int num = sc.nextInt();

            if(str.charAt(0) == 'R'){
                for(int j=0; j<num; j++){
                    arrB[++timeB] = ++currB;
                } 
            }else{
                for(int j=0; j<num; j++){
                    arrB[++timeB] = --currB;
                }    
            }
        }


        for(int i=1; i<=total; i++){
            if(arrA[i] == arrB[i]){
                answer = i;
                break;
            }
        }

        System.out.println(answer);
    }



}

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 문제를 다른 방식으로 해결할 수 있는가?

- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?

-> 배열을 쓰지 않고 풀 수 있는 방법이 있는가?

-> ArrayList를 쓰는 것이 더 효율적이다 

-> 왜냐하면 필요한만큼 메모리를 할당할 수 있기 때문이다.