941. Valid Mountain Array

 

https://leetcode.com/problems/valid-mountain-array/

Valid Mountain Array - LeetCode

 

 

---

 

 

문제 해결 6단계

 

1. 문제를 읽고 이해한다. 

 

Given an array of integers arr, return true if and only if it is a valid mountain array. => 정수의 배열이 주어지고, mountain array일 시 true, 그렇지 않으면 false를 반환.

 

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

이게 mountain array.

 

제한사항:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

 

---

 

 

2. 문제를 익숙한 용어로 재정의한다. 

 

배열이 계속 증가하다 피크 찍고 계속 내려가는 모양이면 mountain array. 중간에 같은 값이 있거나 값이 왔다갔다 하면 mountain array가 아님.

 

---

 

3. 어떻게 해결할지 계획을 세운다. 

 

1. state를 0으로 지정. for문을 돌면서 만일 값이 감소했을 시 state를 1로 바꿈. 이후 state가 1일 시 계속 값이 감소하는지 확인하고, 아니면 false 반환. => 구현 실패. 코드 짜다가 구현 아이디어가 부족했음.

 

2. 투포인터로 배열의 맨 앞, 맨 뒤를 변수로 지정하고, 각각 증가 혹은 감소하면서 값을 확인. 각각의 지점에서 값이 같거나 감소할 시, break. 두 지점이 같으면 true를 반환, 아니면 false를 반환.

 

 

 

---

 

4. 계획을 검증한다. 

 

1. 시간 복잡도는 O(n)이며, 배열 내 숫자가 같은 경우에도 가능. 올라가기만, 내려가기만 하는 경우에도 가능.

 

2. 시간 복잡도는 동일하게 O(n). 배열 내 숫자가 같은 경우에도 가능. 올라가기만, 내려가기만 하는 경우 따로 케이스 구현(오류떠서 고쳤음).

 

 

---

 

 

5. 프로그램으로 구현한다. 

 

1. 구현 실패 => 생각해야하는 if의 수가 많아, 생각이 꼬였음.

2. 

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if (arr.size() < 3) return false;
        
        int front = 1;
        int front_max = 0, rear_max = arr.size() - 1;
        int rear = arr.size() - 2;
        
        while (front < arr.size()) {
            if (arr[front] <= arr[front - 1]) 
                break;
            front_max = front;
            front++;
        };

        if (front_max == arr.size() - 1) return false;        
        
        
        while (rear > -1) {
            if (arr[rear] <= arr[rear + 1])
                break;
            rear_max = rear;
            rear--;
        };

        
        if (rear_max == 0) return false;
                
        
        if (front_max == rear_max)
            return true;
        return false;
    }
};

 

 

 

---

 

6. 어떻게 풀었는지 되돌아보고, 개선할 방법이 있는지 찾아본다.

 

첫번째 접근을 구현한 코드. 투포인터 접근으로 굳이 리스트를 두번 돌 이유는 없었음.

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if(arr.size()<3)
            return false;
        if(arr[0]>arr[1])
            return false;
        int i=1;
        bool check=false;
        for(;i<arr.size();i++)
        {
            if(check && arr[i]>arr[i-1])
                return false;
            
            else if(arr[i]<arr[i-1])
                check=true;
            
            if(arr[i]==arr[i-1])
                return false;
        }
        if(check)
          return true;
        return false;
    }
};