[Hackerrank] Kangaroo 문제 해설 - Algorithms > Implementation / Easy

Kangaroo

1. 문제 설명

이 문제는 서로 다른 시작 지점과 점프 크기를 가진 두 마리의 캥거루가 경주를 할 때, 뒤에서 출발한 캥거루와 앞선 지점에서 출발한 캥거루가 똑같은 시점에 같은 지점에 있을 수 있는지 묻는 문제이다(마치 어렸을 적 수학 책에서 나왔던 문제와 비슷하다..).

* 원본 링크 : https://www.hackerrank.com/challenges/kangaroo/problem

변수 설명

• x1 : 첫번째 캥거루의 시작 지점
• x2 : 두번째 캥거루의 시작 지점
• v1 : 첫번째 캥거루가 한 번에 점프 할 수 있는 거리
• v2 : 두번째 캥거루가 한 번에 점프 할 수 있는 거리

2. Input Format

첫번째 줄에 x1, v1, x2, v2의 값이 주어진다.

3. Output Format

두 캥거루가 똑같은 지점에 똑같은 타이밍에 존재 할 수 있다면 YES 출력,

그렇지 않다면 NO 출력

4. 제약 조건

Sample Input1

0 3 4 2

Sample Output1

YES

Sample Input2

0 2 5 3

Sample Output 2

NO

---

Solution

이 문제를 처음 접하고 떠올린 풀이 방법은 다음과 같다.

1. x1 < x2이므로, v1 < v2면 두 캥거루는 만날 수 없으므로 NO 출력
2. 1 <= v1, v2 <= 10000이므로 10000번 반복문을 수행하면서 두 캥거루가 같아지는 지점이 존재하면 YES 출력, 아니면 NO 출력

1번은 괜찮지만, 2번의 경우 시간 복잡도가 최대 O(10000)까지 올라갈 수 있는 무적이나 비효율적인 알고리즘이 탄생할 것 같았다. 그래서 조금 더 생각해보니 아래와 같은 식이 도출 되었다.

두 캥거루가 동일한 지점에서 만나려면 아래 식이 성립해야 한다.

x1 + n * v1 = x2 + n * v2 //n = 점프 횟수

이를 n에 관한 식으로 풀면 다음과 같다.

n = (x2 - x1) / (v1 - v2)

만약 n값에 소수점이 발생한다면, 두 캥거루는 x.xx번 뛰었을 때 동일한 지점에서 만날 수 있다는 의미이다. 하지만 점프 횟수는 정수여야 하므로, 이는 두 캥거루가 동일 지점에서 만날 수 없음을 의미한다.

때문에 아래와 같은 조건을 통해 두 캥거루가 만날 수 있는지 여부를 판단한다.

((x2 - x1) % (v1 - v2)) === 0 //나머지가 0이면 정수로 떨어지므로 YES, 아니면 NO

최종 코드는 다음과 같다.

function kangaroo(x1, v1, x2, v2) {
	let result = 'YES';

	if(v1 <= v2){
		result = 'NO';
	} else {

		if(((x2 - x1) % (v1 - v2)) === 0){
			result = 'YES';
		} else {
			result = 'NO';
		}
	}
	
	return result;
}

function main() {
    var x1_temp = readLine().split(' ');
    var x1 = parseInt(x1_temp[0]);
    var v1 = parseInt(x1_temp[1]);
    var x2 = parseInt(x1_temp[2]);
    var v2 = parseInt(x1_temp[3]);
    var result = kangaroo(x1, v1, x2, v2);
    process.stdout.write("" + result + "\n");

}