[BOJ] 오등큰수 C# 사용 풀이 (복습 대상)

문제

풀이

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


namespace BOJ17229
{
    class Program
    {
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            //StringBuilder sb = new StringBuilder();

            int N = int.Parse(sr.ReadLine()); // 배열의 크기
            //예제 : 1 1 2 3 4 2 1
            int[] A = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);  // 배열 요소 A 배열에 담기
            //A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)
            int[] F = new int[A.Max() + 1];  // 등장 횟수 배열 F = A인덱스 요소들중 최대값 +1 크기의 배열

            for (int i = 0; i < N; i++) //A의 배열 크기만큼 순회
            {
                //F 배열의 인덱스에 A 요소들의 등장 수 만큼 ++
                //F 의 인덱스  0,1,2,3,4  = 0,3,2,1,1
                F[A[i]]++;
            }

            var stack = new Stack<int>(N); //스택 생성
            var ngf = new int[N];  //오등큰수 선언 (크기 N)

            for (int i = 0; i < N; i++) // N만큼 순회
            {
                ngf[i] = -1; //오등큰수 배열의 인덱스 요소 기본값  = -1   
                //스택이 비어있지 않고 F[A[스택의 최 상단 값 ]의 요소값 ]] 이  F[A[i]의 요소값 ] 보다 작다면
                while (stack.Count > 0 && F[A[stack.Peek()]] < F[A[i]])
                {
                    // 오등큰수 배열[스택의 최 상단 값]에 A[i] 넣어주기 
                    ngf[stack.Pop()] = A[i];  //오등큰수 배열[스택 최상단 값 Pop] 에 A[i] 값 할당 
                }
                stack.Push(i); // 스택에 i 값 Push
            }
            //오등큰수 배열을 출력
            for (int i = 0; i < N; i++)
            {
                sw.Write("{0} ", ngf[i]);
            }

            sr.Close();
            sw.Close();
        }
    }
}

결과창

 

F 배열을 선언하여 인덱스를 이용해 A의 배열 요소가 얼마나 중복되었는지 count 하는데 까지는 이해하는데 무리가 없었지만

그 아래 오등큰수 배열을 작성하여 stack 과 연계하는 부분을 그림을 그려야 겨우 이해를 하였다.

코드 자체는 이해가 갔지만 사실 아직 정확하게 어떤 원리로 오등큰수를 구할수 있었는지 헷갈리는 부분이 많아 좀더 문제를 읽어보고 다시 풀어보기 위해 복습 대상으로 두고 비슷 한문제를 좀 더 풀어보아야겠다