코딩테스트 준비 F - 세워라 반석 위에

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 21967.세워라 반석위에
사용언어 : C#
난이도 : Middle
풀이시간 : 1h 14m ++
유형 : 브루트포스, 투 포인터

문제

드높은 남산 위에 우뚝 선

(중략)

세워라 반석 위에

선린의 터를

반석: 넓고 펀펀한 큰 돌, 너럭바위

어떤 수열이 반석이라는 것은, 수열의 최댓값과 최솟값의 차이가 2 이하임을 의미한다.

예를 들어 1 2 3 3 1 2는 최댓값(3)과 최솟값(1)의 차이가 2이므로 반석이고, 2 6 5 4는 최댓값(6)과 최솟값(2)의 차이가 4이므로 반석이 아니다.

수열이 주어지면 수열의 연속한 부분 수열(부분 문자열, substring) 중, 가장 긴 반석의 길이를 구하는 프로그램을 작성하자.

입력

첫 번째 줄에 수열의 길이 $N$ 이 주어진다.

두 번째 줄에는 수열 A $A$ 의 원소 A1,A2,⋯,AN
$A_1, A_2, \cdots , A_N$ 이 공백으로 구분되어 주어진다.

출력

수열 A $A$ 의 연속한 부분 수열 중 가장 긴 반석의 길이를 출력한다.

제한

1 ≤ N ≤ 1000000, $1 \leq N \leq 1\,000\,000$

1 ≤ Ai ≤ 10, $1 \leq A_i \leq 10$

예제 입력 1 복사

5
1 2 1 3 1

예제 출력 1 복사

예제 입력 2 복사

7
1 2 3 4 2 5 7

예제 출력 2 복사

문제 풀이 접근

문제 풀이는 2가지 방식으로 접근했다.
1. Brute Force 방식
2. 이분 탐색 방식

Brute Force

1. while(left <= right)를 사용하여 일반적인 투 포인터 알고리즘 구성
2. int leftElement = arr[left] 로 기준으로 잡은 후에, for문을 arr.Length-1 까지 순회하여, 가장 긴 반석을 검색, 오른쪽도 동일하게 검색
3. TC 통과, 시간 초과 판정
4. 반복 조건 변경 left < (right/2)로 검색 가능할 것이라고 판단
5. 시간 초과 판정, 알고리즘 변경

이분 탐색

logN의 시간 복잡도를 가진 이분 탐색이 적합하다고 판단.
for문으로 arr.Length 까지 순회
현재 i 의 값 부터, 이분 탐색을 실행해, 현재 원소의 값+2 보다 큰 값을 찾는다.
탐색 시작한 left 값과 찾아낸 FindIndex 값을 연산하여 값 도출
* 식 : FindIndex - left +1 ( 순열 갯수로 +1)
시간 복잡도 Pass, 값 Fail

작성 코드 (C#) - 이분 탐색 실패

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : Middle
// * URL : https://www.acmicpc.net/problem/21967
//  * Time : 1h 14m
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int[] _arr;
        public void solve()
        {
            _n = int.Parse(Console.ReadLine());
            _arr = new int[_n];

            string[] _in = Console.ReadLine().Split(' ');

            for (int i = 0; i < _in.Length; ++i)
                _arr[i] = int.Parse(_in[i]);

            int _ret = int.MinValue;
            //Array.Sort(_arr); // 오름차순 정렬

            for (int i = 0; i < _arr.Length; ++i)
            {
                int _val = _arr[i];
                int _bsIdx = BinarySearch(_arr, i, _val);

                if (_bsIdx >= _ret)
                    _ret = _bsIdx;
            }

            Console.WriteLine(_ret);
        }

        public int BinarySearch(int[] arr, int left, int val)
        {
            int sleft = left;
            int right = _arr.Length - 1;

            while (sleft < right)
            {
                int mid = (sleft + right) / 2;

                int min = Math.Min(val, arr[mid]);
                int cur = Math.Max(val, arr[mid]);

                if(min +2 <= cur)
                    right = mid;
                else
                    sleft = mid + 1;
            }

            return sleft-left+1;
        }
    }
}

코드 결과

* 코드 실패로 미 첨부