[C++ HackerRank 코드 챌린지] 0-2. Counting Valleys

 

지난글에이어 HackerRank에 있는 interview-preparation-kit에 속한 문제중 Counting Valleys에 관해 풀어보도록 하겠습니다.

counting valley는 U(Up)와 D(Down)로 이루어진 string입력을 받고 이를통해 계곡이 몇개 포함되어 있는지 찾는 문제입니다.

출발은 sea level에서 하고 sea level 아래로 내려갔다가 다시 sea level로 복귀하면 계곡이 1개 카운트가 되는 법칙입니다.

예를들어서 입력이 다음과 같다면,

8
UDDDUDUU

UDDDUDUU 

위 그림과 같이 나타낼 수 있고 sea level에서 출발해서 sea level로의 복귀가 1번있었으므로 계곡은 1개 카운트가 되게 됩니다. 이러한 형태의 random input을 받아서 올바른 return을 해주는 countingValley 함수를 작성하는 것이 이 문제의 목적입니다. 

먼저 제가 submission한 답변을 보시면,

int countingValleys(int n, string s) {
    int count=0, valley_count=0;
    bool valley_flag=false;
    for(int i=0; i<n; i++){
        if(s[i] == 'U') count++;
        else if(s[i] == 'D') count--;
        
        if(count < 0) valley_flag=true;
        if(valley_flag==true && count >=0){
          
          valley_count++;
          valley_flag = false;
        } 
    }
    return valley_count;
}

총입력된 string의 수만큼 for문을 돌립니다. 이때 string 입력이 U이면 count 를 +1 하고 D이면 count를 -1 하도록 할 경우 sea level보다 낮아진다는 것은 count의 값이 0보다 작아진다는 것을 의미합니다. 

 if(s[i] == 'U') count++;
 else if(s[i] == 'D') count--;
        
 if(count < 0) valley_flag=true;

위 코드에서 보시는 것과 같이 sea level아래로 내려가면 (count 가 0보다 작으면) valley_flag를 켜주고 다음과 같이 count의 값이 0보다 커지게 되면 (sea level위로 다시 올라오게 되면) 비로소 1개의 계곡을 count 하도록 하였습니다.

    if(valley_flag==true && count >=0){
          
          valley_count++;
          valley_flag = false;
    } 

이렇게 코드를 작성하고 submission 버튼을 누르면 다음과 같이 잘 통과되는 것을 확인할 수 있습니다.

submission 을 하고나면 다음과 같이 리더보드를 확인할 수 있는데요 여기서 View Solution 버튼을 누르면 다른사람이 작성한 코드도 확인해 볼 수 있습니다.

그럼 다음 글에서 또 계속해서 풀어보도록 하겠습니다.