코딩테스트 준비_F - 올바른 배열

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

• 응시 사이트 : BOJ

• 문제 : 1337.올바른_배열

• 사용언어 : C#

• 난이도 :

• 풀이시간 : 51m

• 유형 : 투 포인터, 정렬

  문제

  올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)

  예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.

  배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.

  입력

  첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 배열에 중복되는 수는 없다.

  출력

  첫째 줄에 입력으로 주어진 배열이 올바른 배열이 되게 하기 위해서 추가되어야할 원소의 최소 개수를 출력한다.

  예제 입력 1 복사

  3
  5
  6
  7
  

  예제 출력 1 복사

  2
  

  예제 입력 2 복사

  6
  5
  7
  9
  8492
  8493
  192398
  

  예제 출력 2 복사

  2
  

  예제 입력 3 복사

  4
  1000
  2000
  3000
  4000
  

  예제 출력 3 복사

  4
  

  예제 입력 4 복사

  7
  6
  1
  9
  5
  7
  15
  8
  

  예제 출력 4 복사

  0
  

문제 풀이 접근

이 문제를 풀면서 처리 방식에 대해서는 2가지 정도가 생각났다.

먼저, 연속적인 배열이란, 말 그대로 1의 간격씩을 두면서 "연속적"인 배열을 뜻한다.

여기서 우리는 투포인터 알고리즘을 사용하여 진행할 것이기 때문에, 정렬이 되어있다라고 가정을 하던가, 로직에 들어가기 전 _arr를 오름차순 정렬한 뒤 로직에 들어가야한다.

아무튼 이런 선처리를 한 이후의 로직은 아래와 같이 아이디어를 생각했다.

1. 연속적인 정렬이기때문에, left는 오름차순으로 ++ 의 경우만 생각한다.
   고로, arr[Left] 에 기준을 두고 arr[Left + i] 와 같이 5번 순회하면서 원소를 찾고, 이 값이 내가 기준으로 선정한 값보다 오차 +- 5에 속하는 지 찾는다 ( Left 기준은 +5, Right 기준은 -5 )
   여기서 내가 생각한 방법 1이 i 가 결국 인덱스고, 인덱스 값 만큼 기준값 arr[Left] 에 더해주면 되는지 알고 if(arr[Left +i] == arr[Left] + i) 와 같은 조건식을 수립했으나, 1 3 5 7 과 같은 수 연속이 나오면 인덱스와 값이 같이 증가해 원하는 것을 찾지 못했다.

2. 이후 나온 방법은 HashSet을 하나 선언해, 중복에 대한 회피를 할 준비를 해두고,arr[Left+i] == arr[Left] +i 와 같은 까다로운 연산 포기하고 (arr[Left] <= Value) && (arr[Left+i] < Value) 를 하여 기준 수 오차 5에 속하는지 체크한다.
   물론 중복 체크를 위해 세팅해둔 HashSet을 이용해 중복은 필터링한다.

이렇게 했는데도 불구하고 정답을 받지못해 아직 반례를 못찾은 상태다.

작성 코드 (C#)

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

///*
// * Difficulty : 
// * URL : https://www.acmicpc.net/problem/1337
//  * Time : 
// */

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

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

            for (int i = 0; i < _n; i++)
                _arr[i] = int.Parse(Console.ReadLine());

            Array.Sort(_arr);

            int _left = 0;
            int _right = _arr.Length - 1;
            int _ret = int.MaxValue;

            bool _isSwitching = false;

            HashSet<int> _hs_Candidate = new HashSet<int>();

            while(_left < _right)
            {
                _hs_Candidate.Clear();

                int _val = _arr[_left];

                for(int i = 0; i < 5; ++i)
                {
                    if (_left + i > _right)
                        break;

                    int _target = _arr[_left+ i];

                    if(_val <= _target && _target < (_val + 5))
                    {
                        if(!_hs_Candidate.Contains(_target))
                            _hs_Candidate.Add(_target);
                    }
                }
                
                if(_ret > 5 - _hs_Candidate.Count)
                    _ret = 5- _hs_Candidate.Count;

                _hs_Candidate.Clear();
                //left

                _val = _arr[_right];

                for (int i = 0; i < 5; ++i)
                {
                    if (_right - i < _left)
                        break;

                    int _target = _arr[_right- i];

                    if (_val >= _target && _target > (_val - 5))
                    {
                        if (!_hs_Candidate.Contains(_target))
                            _hs_Candidate.Add(_target);
                    }
                }
                //right

                if (_isSwitching == true)
                {
                    _isSwitching = !_isSwitching;
                    ++_left;
                }
                else
                {
                    _isSwitching = !_isSwitching;
                    --_right;
                }
            }

            Console.WriteLine(_ret);
        }
    }
}

코드 결과

** 아직 정답을 받지 못했다.