본문 바로가기

Fundamentals/Algorithms

[해커랭크] Counting Valleys

문제링크

 

Counting Valleys | HackerRank

Count the valleys encountered during vacation.

www.hackerrank.com

등산가는 등산을 해수면에서 시작하여 해수면에서 끝내며, 각 걸음은 해발 고도에서 한 단위의 변화를 나타냅니다. 등산 경로는 'U'(오르막)와 'D'(내리막)로 구성된 문자열로 주어지며, 등산가는 이 경로를 따라 걷습니다. 문제의 목표는 등산가가 걸은 경로를 분석하여 등산 중 걸었던 계곡의 총 수를 찾는 것입니다. 여기서 '계곡'은 해수면 아래에서 시작하여 해수면으로 다시 올라오는 연속된 걸음들의 시퀀스를 의미합니다. 예를 들어, 'DDUU' 경로는 한 개의 계곡을 형성합니다. 이 문제에서는 주어진 경로에 따라 등산가가 걸었던 계곡의 수를 계산하는 함수를 작성해야 합니다.

 

풀이 :

 

function countingValleys(steps, path) {
    let level = 0;
    let count = 0
    for(let i=0; i < steps; i++){
        if(path[i] === 'U'){
            level ++
        }else{
            level --
        }
        if(path[i] === 'U' && level === 0 ){
            count ++ 
        }
    }
    return count
}

반복문에서 path의 값에 따라 level 값을 갱신합니다. 계곡은 level 이 음수에서 0으로 되는 시점을 가르키므로 해당 조건에서만 계곡 수를 카운팅합니다.

 

다른 풀이 :

 

function countingValleys(steps, path) {
    let valleys = 0;
    let level = 0;

    for (let i = 0; i < steps; i++) {
        if (path[i] === 'U') {
            level++;
        } else {
            if (level === 0) {
                valleys++;
            }
            level--;
        }
    }

    return valleys;
}

위 함수와 다르게 path가 'U'가 아닐때 level 값을 내리기 전 level이 0인지를 체크합니다. 만약 0일 경우 level을 감소하기전에 0이 되었다는 건 level이 이전에 -1이였만 가능하므로 계곡을 나타내는 시점으로 볼 수 있습니다.

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

[해커랭크] Cats and a Mouse  (0) 2023.12.06
[해커랭크] Electronics Shop  (0) 2023.12.06
[해커랭크] Sales by Match  (0) 2023.12.05
[해커랭크] Bill Division  (0) 2023.12.05
[해커랭크] Day of the Programmer  (0) 2023.12.05