코딩테스트에서 알고리즘 문제는 점점 더 중요해지고 있으며, 많은 기업들이 알고리즘 문제 해결 능력을 중요하게 평가합니다. 이번 강좌에서는 주어진 선분들을 그룹으로 나누는 문제를 다뤄보겠습니다. 이 문제는 효율적인 분류 및 정렬, 그리고 그루핑 로직을 통해 해결할 수 있습니다.
문제 설명
주어진 선분들이 맵상의 점으로 표현될 때, 이 선분들을 오버랩되는 선분 그룹으로 나누는 프로그램을 작성하세요. 선분은 시작점과 끝점을 가지며, 다음과 같은 입력 형식으로 주어집니다:
51 32 56 87 910 12
위의 입력에서 첫 번째 줄은 선분의 개수를 나타내고, 다음 줄들은 각 선분의 시작점과 끝점을 의미합니다. 오버랩하는 선분들은 같은 그룹으로 묶여야 합니다. 예를 들어, 입력된 선분들은 다음과 같이 나뉠 수 있습니다:
그룹 1: (1, 5)그룹 2: (6, 9)그룹 3: (10, 12)
문제 풀이 접근법
이 문제를 해결하기 위해 다음과 같은 접근법을 사용할 수 있습니다:
- 입력으로 주어진 선분들을 리스트에 저장합니다.
- 리스트를 시작점 기준으로 정렬합니다.
- 정렬된 리스트를 순회하며 오버랩하는 선분들을 그룹화합니다.
- 최종적으로 그룹별로 연속된 선분의 범위를 출력합니다.
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: 알고리즘 연습을 위한 국내외 문제를 제공하는 사이트입니다.
- 백준 온라인 저지: 다양한 난이도의 알고리즘 문제를 해결할 수 있는 사이트입니다.
이번 글이 코딩테스트 준비에 도움이 되기를 바랍니다. 궁금한 점이나 추가적인 질문이 있으면 댓글로 남겨주세요. 감사합니다!