HackerRank Counting Valleys

2021-06-21

hackerrank

1. 문제

An avid hiker keeps meticulous records of their hikes. During the last hike that took exactly steps, for every step it was noted if it was an uphill, , or a downhill, step. Hikes always start and end at sea level, and each step up or down represents a unit change in altitude. We define the following terms:

A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.
A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.
Given the sequence of up and down steps during a hike, find and print the number of valleys walked through.

1.1. Example

The hiker first enters a valley units deep. Then they climb out and up onto a mountain units high. Finally, the hiker returns to sea level and ends the hike.

1.2. Function Description

Complete the countingValleys function in the editor below.

countingValleys has the following parameter(s):

int steps: the number of steps on the hike
string path: a string describing the path
Returns

int: the number of valleys traversed

1.3. Input Format

The first line contains an integer , the number of steps in the hike.
The second line contains a single string , of characters that describe the path.

1.4. Constraints

2 <= steps <= 10^6
path[i] {UD}를 포함한다.

1.5. Sample Input

8
UDDDUDUU

1.6. Sample Output

1.7. Explanation

If we represent _ as sea level, a step up as /, and a step down as , the hike can be drawn as:

_/\ _
\ /
//
The hiker enters and leaves one valley.

1.1. 컴퓨팅적 사고

해당 문제는 등산객에 하이킹에 대한 기록을 처리하는데 등산객이 계곡을 들어가게 되는데 계곡에 들어가서 다시 해수면으로 올라오는것의 갯수를 구하는되는 문제입니다.

처음에 왜 등산객이 해수면으로 들어갈까 라는 의문을 갖긴…? 했지만 문제를 다시 살펴보면 문제에서 예제를 준것을 잘 살펴보면 쉽게 이해하실 수 있습니다.

8
UDDDUDUU
_/\      _
   \    /
    \/\/

입력이 8이고 UDDDUDUU의 순서대로 등산객의 행동이 주어졌다고 가정하겠습니다.

_는 현재 해수면을 나타냅니다.
/ 해수면 위로 간 것을 나타냅니다.
\ 해수면 아래로 간것을 나타냅니다.

1 0 -1 -2 -1 -2 -1 0

해당되는 의미만 잘 살피면 해당되는 문제를 쉽게 푸실 수 있습니다.
현재 해수면 _ 에서 시작해서 해당되는 명령을 처리한다고 할때 올라가면 +1, 내려가면 -1로 생각을 하여 문제를 풀었습니다. 즉, valleyCount라는 변수를 선언하여 해당되는 현재의 상태를 나타낼 수 있도록 하여 현재 해수면의 아래에 진입했는지를 확인하여 isCheck 변수로 boolean 체크를 해주었습니다. 즉, 해수면 아래로 진입해서 해수면 즉, 0 의 값에 도달하였을때 하나의 해수면에 올라온 기록을 체크할 수 있기때문입니다.

생각해보기

'U’가 주어지면 +1, 'D’가 주어지면 -1
해수면 아래로 진입하였는지?
해수면 아래로 진입하였고 다시 해수면 _(0의 값)에 도달하였으면 기록의 개수를 증가시켜줍니다. 그리고 체크를 해제하여 다시 해수면의 아래로 들어가는경우를 찾아냅니다.

1.2. 소스코드

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

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

    public static int countingValleys(int steps, String path) {
        // Write your code here
        int valleyCount = 0;
        boolean isCheck = false;
        int answer = 0;
        for(char c : path.toCharArray()){
            if(c == 'U'){
                valleyCount++;
            }else {
                valleyCount--;
            }
            if(valleyCount < 0 && !isCheck){
                isCheck = true;
                continue;
            }
            if(isCheck && valleyCount == 0){
                answer++;
                isCheck = false;
            }
        }
        return answer;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int steps = Integer.parseInt(bufferedReader.readLine().trim());

        String path = bufferedReader.readLine();

        int result = Result.countingValleys(steps, path);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Algorithmhackerrank