본문 바로가기

Fundamentals/Algorithms

[해커랭크] Number Line Jumps

문제링크

 

Number Line Jumps | HackerRank

Can two kangaroo meet after making the same number of jumps?

www.hackerrank.com

두 마리의 캥거루가 숫자선 위에서 점프를 하며, 두 캥거루가 동일한 횟수의 점프 후 같은 위치에서 만날 수 있는지를 판단하는 문제입니다.첫 번째 캥거루는 위치 x1에서 시작하여 v1 미터 단위로 점프합니다.

두 번째 캥거루는 위치 x2에서 시작하여 v2 미터 단위로 점프합니다.

두 캥거루가 같은 위치에서 만날 수 있다면 "YES"를, 그렇지 않다면 "NO"를 반환합니다.

풀이 :

 

function kangaroo(x1: number, v1: number, x2: number, v2: number): string {
  while(true){
      if(v2 >= v1) return 'NO'
      x1 += v1;
      x2 += v2;
      if(x1 === x2) return 'YES'
      if(x1 > x2) return 'NO'
  }
}

 

while 문으로 문제를 풀이했으나 조건이 항상 true이므로 특정 조건이 만족하지 않을 경우 무한 루프에 빠질 수 있으며 종료 조건 또한 작성되어 있지 않아 효율성이나 가독성이 떨어지는 코드라고 생각합니다.

 

 

다른 풀이(AI) :

 

function kangaroo(x1: number, v1: number, x2: number, v2: number): string {
    if (v1 > v2 && (x2 - x1) % (v1 - v2) === 0) {
        return "YES";
    }
    return "NO";
}

 

선형 방정식으로 접근하여 풀이

 

- 캥거루 1의 위치: x1 + v1 * t

- 캥거루 2의 위치: x2 + v2 * t

 

두 캥거루가 같은 위치에서 만나기 위해서는 x1 + v1 * t = x2 + v2 * t가 되어야 합니다. 이를 재정리하면, x1 - x2 = (v2 - v1) * t가 됩니다. 여기서 중요한 점은 t가 항상 정수여야 한다는 것입니다(캥거루가 점프하는 횟수이므로). 따라서, x1 - x2는 v2 - v1로 나누어 떨어져야 합니다. 이것이 (x2 - x1) % (v1 - v2) === 0 조건의 의미입니다.

'Fundamentals > Algorithms' 카테고리의 다른 글

[해커랭크] camelcase  (0) 2023.11.26
[해커랭크] Breaking the Records  (0) 2023.11.26
[해커랭크] Apple and Orange  (0) 2023.11.16
[해커랭크] Grading Students  (0) 2023.11.16
[해커랭크] Time Conversion  (0) 2023.11.16