Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Note: sequence a0, a1, ..., an is considered to be a strictly increasing if a0 < a1 < ... < an. Sequence containing only one element is also considered to be strictly increasing.

Example

• For sequence = [1, 3, 2, 1], the output should be

  solution(sequence) = false.

  There is no one element in this array that can be removed in order to get a strictly increasing sequence.

• For sequence = [1, 3, 2], the output should be

  solution(sequence) = true.

  You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer sequence

  Guaranteed constraints:

  2 ≤ sequence.length ≤ 105,

  • 105 ≤ sequence[i] ≤ 105.

• [output] boolean

  Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

풀이

• 증가수열이 성립되는지 묻는 문제
• 이전 값과 비교 및 이전 값 혹은 현재 값을 제거하는 상황이 발생하므로 Stack 을 사용하였다.
• 수를 제거할 수 있는 기회는 단 한 번 뿐이다.

boolean solution(int[] sequence) {
		// 제거 기회는 한 번
    boolean chance = true;
		// 증가 수열을 담을 자료구조
    Stack <Integer> stack = new Stack<>();
		// 첫 수는 수열에 담고 시작
    stack.add(sequence[0]);
    
		// 두 번째 수 부터 시작
    for (int i = 1; i < sequence.length; i ++) {
				// 제거 기회가 없고 증가 수열에 수가 존재할 때
        if (!chance && !stack.isEmpty()) {
						// 수열 마지막 값이 현재 값보다 크거나 같을 경우, 수열은 성립하지 못한다.
            if (stack.peek() >= sequence[i]) return false;
        }
        
				// 수열에 수가 존재하며, 수열의 마지막 수가 현재값보다 크거나 같을 때
        if (!stack.isEmpty() && stack.peek() >= sequence[i]) {
						// 제거 기회가 있을 때
            if (chance) {
								// 제거 기회는 사라짐
                chance = false;
                
								// 현재 인덱스가 마지막 인덱스가 아니고
								// 수열 마지막 수가 다음 수 보다 크면
								// 수열 마지막 수를 제거하고 다시 현재 수와 수열을 비교하도록 유도한다.
                if (i < sequence.length - 1 && !(stack.peek() < sequence[i + 1])) {
                    stack.pop();
                    i --;
                }
                
								// 수열 마지막 수가 다음 수 보다 작으면 현재 수는 수열에 추가하지 않는다.
                continue;
						// 제거 기회가 없을 경우 수열은 성립되지 않는다.
            } else {
                return false;
            }
        }
        
				// 현재 수를 수열에 추가
        stack.add(sequence[i]);
    }
    
    return true;
}