2022.02.05 [백준] C# 좌표 압축

 

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

18870번: 좌표 압축

 

---

풀이

이 문제는 각 좌표의 대소 관계에 대한 순위를 메기는 문제인거같다.

아래 정답코드에서 lower bound함수를 사용했다. lower bound함수는 이진탐색(Binary Search)기반의 탐색 방법이다.

이 함수는 num[mid] >= target이면서 num[mid] < target 인 최소값을 찾는다.

이 함수에 대해서는 아래의 블로그를 참고했다. 사용하고도 이해하기가 어려운거같다...

 

 

https://blockdmask.tistory.com/168

[탐색] lower_bound, upper_bound

using System;
using System.Text;
using System.IO;
using System.Linq;
using System.Collections.Generic;
 
class Program
{
    public static int lower_bound(int[] num, int target, int n)
    {
        int start = 0;
        int end = n-1;
        while (start < end)
        {
            int mid = (start + end) / 2;
            if (num[mid] >= target)
            {
                end = mid;
            }
            else
            {
                start = mid + 1;
            }
        }
        return end;
    }
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        string[] s = sr.ReadLine().Split();
        int[] num = new int[n];
        for(int i=0;i<n; i++)
        {
            num[i] = int.Parse(s[i]);
        }
        int[] num_Dis = num.Distinct().ToArray();
        Array.Sort(num_Dis);
        
        foreach(int i in num)
        {
            sb.Append(lower_bound(num_Dis, i, num_Dis.Length) + " ");
        }
        sw.WriteLine(sb.ToString());
        sr.Close();
        sw.Close();
    } 
}