[Hackerrank] Apple and Orange 문제 해설 - Algorithms

[Hackerrank] Apple and Orange 문제 해설 - Algorithms > Implementation / Easy

1월 02, 2018

Apple and Orange

1. 문제 설명

이 문제는 사과 나무와 오랜지 나무 사이에 있는 Sam의 집에 사과와 오랜지 열매가 얼마나 많이 떨어졌는지 구하는 알고리즘 문제다. 자세한 내용은 아래 링크에서 확인 할 수 있다.

* 원본 링크 : https://www.hackerrank.com/challenges/apple-and-orange/problem

문제 이해를 위한 이미지

위의 이미지에서 볼 수 있듯이 모든 사물은 x-축 상에 있다고 가정한다.

주어지는 변수를 설명하면 다음과 같다.

s: Sam의 집이 시작되는 지점
t: Sam의 집이 끝나는 지점
a: 사과 나무의 위치
b: 오랜지 나무의 위치
m: 사과의 갯수
n: 오랜지의 갯수
d: 각각의 열매(사과, 오랜지)가 해당 과일 나무와 떨어져있는 거리. 값이 음수(-)일 경우 x-축의 좌측에, 양수(+)일 경우 우측에 존재한다는 의미이다.

2. Input Format

첫번째 줄에는 s와 t값이 구분되어 주어진다.

두번째 줄에는 a와 b값이 구분되어 주어진다.

세번째 줄에는 m과 n값이 주어진다.

네번쨰 줄에는 m개의 사과가 떨어진 지점과 a지점까지의 거리를 표시한다.

다섯번쨰 줄에는 n개의 오랜지가 떨어진 지점과 b지점까지의 거리를 표시한다.

3. Output Format

첫번째 줄에는 Sam의 집에 떨어진 사과의 갯수를 표시한다.

두번째 줄에는 Sam의 집에 떨어진 오랜지의 갯수를 표시한다.

4. 제약조건

Sample Input

Sample Output

1
1

Solution

처음 이 문제를 접했을 때 내가 생각한 해결 방법은 너무 단순했다.

a < s < t < b 이므로,

떨어진 각 사과(apple[i])의 좌표와 사과 나무의 위치를 더한 값이 s보다 크면 Sam의 집에 떨어졌다고 가정
떨어진 각 오랜지(orange[i])의 좌표와 오랜지 나무의 위치를 더한 값이 t보다 작으면 Sam의 집에 떨어졌다고 가정

이를 바탕으로 아래와 같은 코드가 작성되었다.

function appleAndOrange(s, t, a, b, apple, orange) {
 let appleCnt = 0;
 let orangeCnt = 0;

 const appleLength = apple.length;
 const orangeLength = orange.length;

 for(let i = 0; i < appleLength; i ++){
  if(a + apple[i] >= s){
   appleCnt++;
  }
 }

 for(let i = 0; i < orangeLength; i ++){
  if(b + orange[i] <= t){
   orangeCnt++;
  }
 }

 return [appleCnt, orangeCnt];
}

하지만, 여기서 문제는 apple[i]과 orange[i]의 값이 너무 큰 값이 올 경우

apple[i] + a > t일 경우 카운트가 되지 않아야 하지만 그대로 카운트 됨
orange[i] + b < s일 경우 카운트가 되지 않아야 하지만 그대로 카운트 됨

이러한 문제점을 발견 후 조건식을 다음과 같이 수정했다.
s <= 과일이 떨어진 지점 <= t 일 경우에만 카운트

최종 코드는 다음과 같다.

function appleAndOrange(s, t, a, b, apple, orange) {
 const appleCnt = calcFallPoint(s, t, a, apple);
 const orangeCnt = calcFallPoint(s, t, b, orange);
 return [appleCnt, orangeCnt];
}

function calcFallPoint(s, t, point, fruits){
 const fruiteCnt = fruits.length;
 let cnt = 0;

 for(let i = 0; i < fruiteCnt; i ++){
  const fallPoint = point + fruits[i];

  if(fallPoint >= s && fallPoint <= t){
   cnt++;
  }
 }

 return cnt;
}

이 블로그 검색

armadillo.ko