C# 코딩테스트 강좌, 선분을 그룹으로 나누기

코딩테스트에서 알고리즘 문제는 점점 더 중요해지고 있으며, 많은 기업들이 알고리즘 문제 해결 능력을 중요하게 평가합니다. 이번 강좌에서는 주어진 선분들을 그룹으로 나누는 문제를 다뤄보겠습니다. 이 문제는 효율적인 분류 및 정렬, 그리고 그루핑 로직을 통해 해결할 수 있습니다.

문제 설명

주어진 선분들이 맵상의 점으로 표현될 때, 이 선분들을 오버랩되는 선분 그룹으로 나누는 프로그램을 작성하세요. 선분은 시작점과 끝점을 가지며, 다음과 같은 입력 형식으로 주어집니다:

위의 입력에서 첫 번째 줄은 선분의 개수를 나타내고, 다음 줄들은 각 선분의 시작점과 끝점을 의미합니다. 오버랩하는 선분들은 같은 그룹으로 묶여야 합니다. 예를 들어, 입력된 선분들은 다음과 같이 나뉠 수 있습니다:

문제 풀이 접근법

이 문제를 해결하기 위해 다음과 같은 접근법을 사용할 수 있습니다:

1. 입력으로 주어진 선분들을 리스트에 저장합니다.
2. 리스트를 시작점 기준으로 정렬합니다.
3. 정렬된 리스트를 순회하며 오버랩하는 선분들을 그룹화합니다.
4. 최종적으로 그룹별로 연속된 선분의 범위를 출력합니다.

1단계: 입력 처리

먼저 사용자가 입력한 선분을 받을 수 있는 구조체를 정의하고, 입력을 처리하겠습니다. 구조체를 통해 선분의 시작점과 끝점을 저장하고, 리스트 형태로 관리합니다.

using System;
using System.Collections.Generic;

public class Segment{
    public int Start { get; set; }
    public int End { get; set; }
    
    public Segment(int start, int end){
        Start = start;
        End = end;
    }
}

2단계: 정렬

선분 리스트를 시작점 기준으로 정렬하는 코드입니다. 이를 통해 비슷한 선분들이 가까이 위치하게 되어 우리를 그룹 지을 준비를 할 것입니다.

public List<Segment> SortSegments(List<Segment> segments){
    segments.Sort((a, b) => a.Start.CompareTo(b.Start));
    return segments;
}

3단계: 그룹화 로직

그룹화 로직은 각 선분을 순회하면서 현재 그룹에 추가할 수 있는지 여부를 판단합니다. 현재 선분의 시작점이 마지막 선분의 끝점보다 작거나 같으면 같은 그룹에 포함됩니다. 반대로 새로운 그룹을 시작합니다.

public List<List<Segment>> GroupSegments(List<Segment> segments){
    List<List<Segment>> groups = new List<List<Segment>>();
    groups.Add(new List<Segment>());
    
    foreach(var segment in segments){
        var lastSegment = groups[groups.Count - 1];
        if(lastSegment.Count == 0 || segment.Start > lastSegment[lastSegment.Count - 1].End){
            groups.Add(new List<Segment>());
        }
        groups[groups.Count - 1].Add(segment);
    }

    return groups;
}

4단계: 최종 출력

마지막으로 그룹화 된 결과를 출력합니다. 각 그룹의 시작점과 끝점을 기반으로 간단한 텍스트 형식으로 결과를 보여줍니다.

public void PrintGroups(List<List<Segment>> groups){
    for(int i = 0; i < groups.Count; i++){
        var group = groups[i];
        if(group.Count > 0){
            Console.WriteLine($"그룹 {i + 1}: ({group[0].Start}, {group[group.Count - 1].End})");
        }
    }
}

전체 코드

이제 모든 단계를 결합하여 최종 코드를 작성해 보겠습니다:

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

class Program
{
    public class Segment
    {
        public int Start { get; set; }
        public int End { get; set; }

        public Segment(int start, int end)
        {
            Start = start;
            End = end;
        }
    }

    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        List<Segment> segments = new List<Segment>();

        for (int i = 0; i < n; i++)
        {
            var input = Console.ReadLine().Split(' ');
            int start = int.Parse(input[0]);
            int end = int.Parse(input[1]);
            segments.Add(new Segment(start, end));
        }

        segments = SortSegments(segments);
        var groups = GroupSegments(segments);
        PrintGroups(groups);
    }

    public static List<Segment> SortSegments(List<Segment> segments)
    {
        segments.Sort((a, b) => a.Start.CompareTo(b.Start));
        return segments;
    }

    public static List<List<Segment>> GroupSegments(List<Segment> segments)
    {
        List<List<Segment>> groups = new List<List<Segment>>();
        groups.Add(new List<Segment>());

        foreach (var segment in segments)
        {
            var lastSegment = groups[groups.Count - 1];
            if (lastSegment.Count == 0 || segment.Start > lastSegment[lastSegment.Count - 1].End)
            {
                groups.Add(new List<Segment>());
            }
            groups[groups.Count - 1].Add(segment);
        }

        return groups;
    }

    public static void PrintGroups(List<List<Segment>> groups)
    {
        for (int i = 0; i < groups.Count; i++)
        {
            var group = groups[i];
            if (group.Count > 0)
            {
                Console.WriteLine($"그룹 {i + 1}: ({group[0].Start}, {group[group.Count - 1].End})");
            }
        }
    }
}

결론

이번 강좌를 통해 선분 그룹화 문제를 해결하는 방법과 함께 C#을 활용하여 코드를 작성하는 방법을 살펴보았습니다. 코딩테스트에서는 다양한 문제를 통해 알고리즘적 사고를 키우는 것이 중요합니다. 반복적인 연습을 통해 다양한 유형의 문제를 풀어보세요!

추가 학습 리소스

이 문제를 해결하는 과정에서 유용한 몇 가지 리소스를 소개합니다:

• 프로그래머스: 다양한 알고리즘 문제를 제공하는 플랫폼입니다.
• LeetCode: 알고리즘 연습을 위한 국내외 문제를 제공하는 사이트입니다.
• 백준 온라인 저지: 다양한 난이도의 알고리즘 문제를 해결할 수 있는 사이트입니다.

이번 글이 코딩테스트 준비에 도움이 되기를 바랍니다. 궁금한 점이나 추가적인 질문이 있으면 댓글로 남겨주세요. 감사합니다!