백준#3020 - 개똥벌레

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

정렬로 분류된 3020번 개똥벌레 문제 입니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _3020
{
    class Program
    {
        static void Main(string[] args)
        {
 
            //입력.
            string[] input = Console.ReadLine().Split(' ');
            int width = int.Parse(input[0]);
            int height = int.Parse(input[1]);
 
            var ansList = new List<int>();
            var reverses = new List<int>();
            var normals = new List<int>();
 
            for(int i = 0; i < width; i++)
            {
                if (i % 2 == 0)
                    normals.Add(int.Parse(Console.ReadLine()));
                else
                    reverses.Add(int.Parse(Console.ReadLine()));
            }
 
            reverses.Sort();
            reverses.Reverse();
            normals.Sort();
 
            int rIndex = 0;
            int nIndex = 0;
            //높이 1부터 높이까지
            for(int bug = 1; bug < height + 1; bug++)
            {
                int ans = 0;
 
                //가장 처음 부딫히는 석순.
                while(nIndex < normals.Count)
                {
                    if(bug <= normals[nIndex])
                    {
                        //부딫히는 걸 찾았다면 그 뒤로는 전부 부딫힘.
                        ans += (normals.Count - nIndex);
                        break;
                    }
                    nIndex++;
                }
 
                //가장 처음 부딫히지 않는 종유석
                while(rIndex < reverses.Count)
                {
                    if(height - reverses[rIndex] >= bug)
                    {
                        //찾았다면 그 뒤로는 전부 부딫히지 않음.
                        break;
                    }
                    rIndex++;
                }
 
                ans += rIndex;
                ansList.Add(ans);
            }
 
            ansList.Sort();
 
            Console.WriteLine("{0} {1}", ansList.First(), ansList.FindAll(x => x == ansList.First()).Count);
        }
    }
}
 

이 문제는 20만 * 50만의 좌표를 전부 받아 일일히 확인하면

시간초과가 반드시 발생하게 됩니다. 부딫혀야 할 장애물의 갯수를 빠르게 찾아주는 것이

이 문제의 핵심이 되겠습니다.

 

 

우선 입력을 받고 종유석과 석순을 나누어 리스트로 세팅했습니다.

다음 종유석은 내림차순 으로 석순은 오름차순으로 정렬 했습니다.

 

이 문제의 해결 방법을 보면

ex) 10 4

reverses(종유석) : 3, 1, 2, 3, 2

normals(석순) : 3, 2, 2, 1, 3

 

이렇게 구성되어 있다고 생각하겠습니다.

 

이를 정렬하면

reverses : 3, 3, 2, 2, 1

normals : 1, 2, 2, 3, 3

이렇게 구성됩니다.

 

1. 벌레가 높이 1지점 부터 출발하는데 석순 (아래서 부터 시작하는 장애물.)

부터 살펴보겠습니다.

 

개똥벌레가 높이 1부터 시작한다고 한다면 모두 부딫힐 수 밖에 없습니다.

 

다음 높이 2에서 시작한다면 높이 2 지점에서 부딫힙니다.

 

여기서 정렬의 효과가 발휘되는데 높이 2지점에서 부딫힌 그 장애물 부터 뒤에 있는

모든 장애물은 반드시 부딫혀야함을 의미합니다. 뒤의 장애물들은 최소한 높이가 같거나

크기 때문이죠.

그 해당 인덱스(nIndex = 1)을 저장해 줍니다.

 

다음 벌레가 높이 3지점에서 출발을 합니다. 

여기서 석순의 높이를 처음부터 다시 보는것이 아니라 가장 최근에 부딫혔던 지점

(여기서는 nIndex = 1) 에서 다시 확인을 시작합니다. 그럼 두개의 높이 2인 석순을 지나

높이 3인 석순에서 부딫혀야 합니다.

마찬가지로 해당 석순부터 뒤의 모든 석순은 부딫혀야 합니다.

 

이런 식으로 진행한다면 벌레가 모든 높이에서 출발해 보면서 많아야 한번의 석순들만

모두 확인해 보면 됩니다.

 

 

2. 종유석을 살펴보겠습니다.

 

종유석은 내림차순으로 정렬 했습니다. 종유석은 반대로 가장 처음 만나는 부딫히지 않는

장애물을 발견할 겁니다.

 

reverses : 3, 3, 2, 2, 1 이렇게 있을 때

벌레가 높이 1에서 시작한다면 아무것도 부딫히지 않습니다.

 

다음 높이 2에서 시작한다면 두개의 높이 3인 종유석에 부딫혀야 합니다.

다음 높이 2인 종유석에서 부딫히지 않습니다. 그 부딫히지 않는 인덱스를 저장합니다.

(rIndex = 2) 그럼 발견한 부딫히지 않는 종유석 부터 뒤에있는 종유석은 부딫힐 필요가

없음을 알 수 있습니다.

 

이를 벌레의 높이를 올려가며 진행해 주시면 되겠습니다.

 

 

3. 조금더 효과적인 방법.

 

석순과 종유석이 정렬되어 있다는 가정하에 효과적인 방법이 있습니다.

BinarySearch를 이용하는 것입니다. 이는 List<T>에 기본적으로 구현되어 있습니다.

 

reverses 예시에서 높이 2에서 벌레가 시작한다면 3 두개를 부딫히고 새로운 부딫히지 않는

종유석을 찾아야 합니다. 이 때 rIndex에서 부터 마지막까지 BinarySearch를 이용하면

더 빠르게 찾을 수 있습니다.