알고리즘 :: From Here To Here, 슬라이딩 윈도우

알고리즘 공부하며 배운내용

 

 

여기서부터 여기까지(From here to here)

재밌는 문제다.

"여기서부터 여기까지 전부 주세요"를 시전 하기 위한 알고리즘

 

진열된 상품의 가격이 이렇다(단위: 만원 생략)

4, 2, 6, 5, 8, 6, 2, 4, 2, 1

 

나는 정확히 20만원 어치 살거다

그럼 8부터 4까지 달라고 하면 된다.

4, 2, 6, 5, [8, 6, 2, 4,] 2, 1

 

But 정확히 10만원 어치 사는 방법은 없네

 

 

INPUT - 제공되는 것

살 금액 M과 금액 리스트가 두 줄로 나온다, 이렇게

20

4 2 6 5 8 6 2 4 2 1

 

 

OUTPUT - 출력 결과

정해진 금액 M에 구매가능 하면 밑의 텍스트 출력

"Could you get me from here to here?"

 

못 사는 경우

"See you later..."

출력

 

 

핵심 포인트 - 슬라이딩 윈도우

20

4 2 6 5 8 6 2 4 2 1

이렇게 들어오면 우선 맨 앞의 4를 20(가진 금액)과 비교

당연히 4 < 20 이다 그럼 오른쪽으로 한 칸 확장

 

즉 4+2를 20과 비교

그래도 6 < 20 그럼 오른쪽으로 한 칸 확장

 

4+2+6을 20과 비교

12 < 20으로 아직도 작다, 오른쪽 한 칸 확장

 

4+2+6+5와 20과 비교

17 < 20 아쉽네, 오른쪽 확장

 

4+2+6+5+8과 20과 비교

25 > 20으로 더한 수가 더 크다, 그럼 왼쪽 한 칸 축소

 

즉 4를 제외한 2+6+5+8과 20 비교

21 > 20으로 그래도 더한 수가 크네, 왼쪽 한 칸 축소

 

6+5+8과 20 비교

. . . . . .

 

결국 8+6+2+4와 20을 비교

20 = 20이 된다! 그럼 종료

left의 인덱스가 제일 오른쪽에 도착하면 원하는 답이 없는 걸로 종료!

 

이렇게 합을 기준이 되는 수와 비교해서 꼬물꼬물 이동한다.

이 방법을 슬라이딩 윈도우라고도 하나보다.

 

 

코드

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 sliding_window.txt로 저장했다.
let fs = require('fs');
let input = fs.readFileSync('sliding_window.txt').toString().split('\n')

// 내가 가진 돈을 M에 저장
const M = +input[0]

// 상품 리스트의 가격을 배열에 저장(현재 문자열 상태)
let item_list = input[1].split(' ')

// left, right, answer 변수 생성
let left_index = 0
let right_index = 0
let answer = "See you later..."

// left 인덱스가 맨 오른쪽 도착하면 종료되도록
while (left_index < item_list.length) {

	// left부터 right까지 합을 구한다.
    let sum = 0
    for(let i = left_index; i <= right_index; i++) {
        sum += +item_list[i]
    }
    
    // 합이 작은 경우
    if(sum < M) {
    	
        // right이 맨 끝에 도착했는데 합이 M보다 작으면 그냥 나가는 코드도 추가
        // 더 추가될 금액이 없어 가망이 없으니까
        if(right_index === item_list.length - 1) {
            break;
        }
        // 합이 작은 경우 오른쪽으로 확장
        right_index++
    }
    
    // 합이 큰 경우 왼쪽 1개 축소
    else if(sum > M) {
        left_index++
    }
    
    // 합이 같은 경우 답변 변경하고 break
    else {
        answer = "Could you get me from here to here?"
        break;
    }
}

console.log(answer)