[Codility] 3. Time Complexity | FrogJmp 🐸

ncheΒ·2021λ…„ 9μ›” 2일


λͺ©λ‘ 보기

❓ Task

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

class Solution { public int solution(int X, int Y, int D); }

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

X = 10
Y = 85
D = 30
the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Write an efficient algorithm for the following assumptions:

X, Y and D are integers within the range [1..1,000,000,000];
X ≀ Y.

πŸ’‘ Solution

λ¬Έμ œλŠ” κΈΈ~게 μ„€λͺ…λ˜μ–΄μžˆμ§€λ§Œ μ•„μ£Ό κ°„λ‹¨ν•œ 1μ°¨ λΆ€λ“±μ‹μœΌλ‘œ 정리가 κ°€λŠ₯ν•©λ‹ˆλ‹€.

a = μ ν”„μˆ˜
Y ≀ X+aD

∴ a β‰₯ (Y-X)/D

μœ„ 뢀등식을 ν™œμš©ν•˜λ©΄ μ•„μ£Ό κ°„λ‹¨ν•œ μ½”λ“œκ°€ μ™„μ„±λ©λ‹ˆλ‹€!

class Solution {
	public int solution (int X, int Y, int D){
    	return (int) Math.ceil((Y-X)/(D*1.0));

πŸ’¬ Note

  1. 계산 결과의 μ†Œμˆ˜μ μ„ λ³΄μ‘΄ν•˜κΈ° μœ„ν•΄ double둜 λ³€ν™˜ν•˜κ³ μž 1.0을 κ³±ν•΄μ£Όμ—ˆμŠ΅λ‹ˆλ‹€. λͺ…μ‹œμ  ν˜•λ³€ν™˜μ„ ν•  μˆ˜λ„ μžˆμŠ΅λ‹ˆλ‹€.
Math.ceil((Y-X)/(D * 1.0));	//λ¬΅μ‹œμ  ν˜•λ³€ν™˜
Math.ceil((Y-X)/(double) D);	//λͺ…μ‹œμ  ν˜•λ³€ν™˜
  1. Y μ΄μƒμ˜ 값을 μ°ΎκΈ° μœ„ν•΄ Math class의 μ–΄λ¦Ό ν•¨μˆ˜ 쀑 μ˜¬λ¦Όμ„ μ‚¬μš©ν•˜μ˜€μŠ΅λ‹ˆλ‹€.

    Math.around()반올림Math.around(1.1) => 1.0
    Math.around(1.9) => 2.0
    Math.ceil()올림Math.ceil(1.1) => 2.0
    Math.floor()λ‚΄λ¦ΌMath.floor(1.9) => 1.0

0개의 λŒ“κΈ€