[백준] 1756 - 피자 굽기

1. 문제

1756번: 피자 굽기

2. 개요

깊이에 따라 지름이 제각각인 오븐과 지름이 제각각인 피자 반죽이 주어진다.

가장 위의 피자 반죽의 깊이를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

이중 반복문을 사용하면 시간초과가 나온다.

큐를 이용해 밑부터 탐색해가며 오븐 지름이 더 크거나 같다면 피자를 빼내는 방식을 이용해봤는데,

오븐의 윗부분의 지름이 더 작아 들어올 수 없는 경우가 있었다.

그래서 오븐에 들어갈 수 있는 피자의 지름을 다시 설정했다.

오븐은 위쪽의 지름보다 클 수가 없다. 따라서 아래가 더 크다면 위의 지름으로 갱신해준다.

다시 밑에서부터 탐색하며 해당 지름이 피자의 크기보다 크거나 같다면 피자를 하나씩 빼낸다.

빼내면서 해당 인덱스를 저장한다.

오븐을 다 탐색했는데 피자가 아직 남아있다면 다 넣을수 없는 것이기 때문에 0을 출력하고,

아니라면 저장된 인덱스를 출력한다.

3-2. Python

import sys
from collections import deque

D, N = map(int, sys.stdin.readline().split())

ovenR = list(map(int, sys.stdin.readline().split()))
pizzaR = deque(map(int, sys.stdin.readline().split()))
answer = D

for i in range(D - 1):
    if ovenR[i + 1] > ovenR[i]:
        ovenR[i + 1] = ovenR[i]

for i in range(D-1, -1, -1):
    if ovenR[i] >= pizzaR[0]:
        pizzaR.popleft()
        answer = i + 1

    if not pizzaR:
        break

if pizzaR:
    print(0)

else:
    print(answer)

3-3. C#

namespace boj_1756
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int answer = 0;

            string[] input = Console.ReadLine().Split();
            int D = int.Parse(input[0]);
            int N = int.Parse(input[1]);

            int[] ovenR = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            for (int i = 0; i < D - 1; i++)
            {
                if (ovenR[i + 1] > ovenR[i])
                    ovenR[i + 1] = ovenR[i];
            }

            Queue<int> pizzaR = new Queue<int>(Array.ConvertAll(Console.ReadLine().Split(), int.Parse));

            for (int i = D - 1; i > -1; i--)
            {
                if (ovenR[i] >= pizzaR.Peek())
                {
                    pizzaR.Dequeue();
                    answer = i + 1;
                }

                if (pizzaR.Count == 0)
                    break;
            }

            if (pizzaR.Count > 0)
                Console.WriteLine(0);

            else
                Console.WriteLine(answer);
        }
    }
}