C#) [BOJ] 2461 대표 선수 ★★

 

2461번: 대표 선수 (acmicpc.net)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace _230124_1
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            
            int[] NM = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse); //띄어쓰기로 구분한 정수형 배열만들기
            int N = NM[0];
            int M = NM[1];

            List<Tuple<int, int>> people = new List<Tuple<int, int>>();
            Dictionary<int, int> check = new Dictionary<int, int>();

            for(int i = 1; i <= N; i++) //반 정보
            {
                int[] arr = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                for(int j = 0; j < arr.Length; j++) //능력치 정보
                {
                    people.Add(new Tuple<int, int>(arr[j], i));
                }
            }

            people.Sort(); //능력치 값으로 오름차순 정렬

            int left = 0; //왼쪽 포인터
            int right = 0; //오른쪽 포인터
            int result = int.MaxValue; //정수형 자료형 변수가 저장가능한 최대값

            while (true)
            {
                //범위 안에 각 반의 학생이 한명이상 있을때
                if (check.Count == N) //딕셔너리의 요소의 갯수가 반의 갯수와 같다면
                {
                    //최대랑 최소가 같은 반이 아닐때
                    if (people[right - 1].Item2 != people[left].Item2) //오름차순으로 저장되기 때문에 저장된 순으로 (가장 높은 능력치 - 가장 낮은 능력치)가 됨
                        result = Math.Min(result, people[right - 1].Item1 - people[left].Item1); //이미 저장된 result값과 현재 최대 능력치 - 최소 능력치를 비교해 더 낮은 수를 저장
                                                                    
                    //left 왼쪽으로 옮기기
                    check[people[left].Item2]--; //가장 작은 능력치를 가진 수의 반정보를 키값으로 갖는 밸류 값을 --

                    if (check[people[left].Item2] == 0) // 밸류값이 0이되면 가장 작은 수이기 때문에 값을 버림
                        check.Remove(people[left].Item2); // 가장 작은 값을 버리면 딕셔너리의 키가 2개가 되기 때문에 아래 else문 실행

                    left++; // 다음 값부터 계산
                }
                else
                {
                    if (right >= people.Count) //오른쪽 포인터가 리스트의 갯수만큼 검사를 실행하면 반복 종료
                        break;

                    //Console.WriteLine("능력치: {0}, 반: {1}", people[right].Item1, people[right].Item2);

                    var key = people[right].Item2; //현재 포인터가 가리키는 튜플의 2번째 값(반 정보)을 변수에 저장

                    if (!check.ContainsKey(key)) //딕셔너리에 반정보가 들어있지 않으면 반정보 = 키, 밸류 = 1 으로 설정
                        check.Add(key, 1);       //딕셔너리에는 각 반당 몇개의 정보가 저장되어있는지 저장
                    else
                        check[key]++; //같은 반 학생이 딕셔너리에 저장되어있으면 밸류값을 1증가시켜서 구분

                    right++; //리스트의 인덱스를 오른쪽으로 이동
                }
            }

            sw.WriteLine(result);


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

 

겨우 이해는 했는데 주기적으로 봐야겠다....