Coding Test/HackerRank

HackerRank 문제풀이 - 2 (Counting Valleys)

범데이 2022. 2. 13. 17:23
728x90

HackerRank 두번째 챌린지 문제 풀이이다. 어떻게 풀어갈지 고민하며 로직을 세우다 보면 재밌다.


1. 문제

 

  • 시작 높이를 해수면으로 가정하여, 해수면보다 낮은 지점으로 내려갔다가 다시 해수면으로 돌아오는 순간 하나의 valley로 가정하여, 걸음 기록(상승, 하강)예제가 주어졌을때, 몇개의 valley들을 지나왔는지 계산해 내는 문제이다.
    • 위의 예제에서는 한개의 valley를 지나온것이다. => 해수면으로부터 시작하여 한번 내려왔다가 다시 해수면으로 올라왔기 때문

2.풀이

'use strict';

import { WriteStream, createWriteStream } from "fs";
process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString: string = '';
let inputLines: string[] = [];
let currentLine: number = 0;

process.stdin.on('data', function(inputStdin: string): void {
    inputString += inputStdin;
});

process.stdin.on('end', function(): void {
    inputLines = inputString.split('\n');
    inputString = '';

    main();
});

function readLine(): string {
    return inputLines[currentLine++];
}

/*
 * Complete the 'countingValleys' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER steps
 *  2. STRING path
 */

function countingValleys(steps: number, path: string): number {
    // Write your code here
    
    let valleys = 0
    let position = 0
    let isSteppedVally = false
        
    for(let i=0; i < steps; i++){
        const step = path.charAt(i)
        
        if(step === "U"){
            position += 1  
        } else if(step === "D") {
            position -= 1
        }
        
        if(position < 0){
            if(!isSteppedVally){
                isSteppedVally = true
                valleys += 1        
            } 
        } else {
            isSteppedVally = false
        }
    }
    
    return valleys;
}

function main() {
    const ws: WriteStream = createWriteStream(process.env['OUTPUT_PATH']);

    const steps: number = parseInt(readLine().trim(), 10);

    const path: string = readLine();

    const result: number = countingValleys(steps, path);

    ws.write(result + '\n');

    ws.end();
}

 

  • 나의 풀이 방법은 다음과 같다.
    • 출발 position을 0으로 설정한다.(해수면)
    • "U"을 상승, "D"을 하강으로 처리하도록 파싱한다.
      • 처리 후 position이 0보다 낮고, 이전에 position이 0보다 높았으면 valley 진입으로 간주(isValley=true), valleys 를 +1 카운팅한다.
      • 처리 후 position이 0이상이면 계곡이 아닌것으로 간주한다. (isValley=false)
    • 모든 step을 처리한 후, valley의 개수를 카운팅 했던 valleys 변수를 반환한다.

3.결과

반응형