이번 문제에서 배우는 것은?
일단 반복문(Loops)를 사용하여 푸는 문제입니다. 그리고 이 퍼즐은 가장 간단한 해결책으론 충분한 성능이 나오지 않습니다. 그리고 우리는 거대한 배열을 다룰것이고 이 것을 처리하는 시간에 대한 경험을 얻을 수 있습니다.
Sorting, Lists를 사용할 수 있습니다.
문제 요약
스토리 : 경마장 주인이 두 마리 말이 듀얼로 경기하는 '듀얼'경기를 만듭니다. 이 경기를 흥미롭게 하기 위해선 가지고 있는 말 중 힘이 가장 비슷한 말 2마리를 쌍으로 붙여야합니다.
문제 : N마리의 말 중에서 가장 힘이 비슷한 두 마리의 말을 골라서 그 차이를 출력하는 프로그램을 만드시오.
문제 풀기
class Solution
{
static void Main(string[] args)
{
int N = int.Parse(Console.ReadLine()); //N마리의 말 입력
for (int i = 0; i < N; i++)
{
int pi = int.Parse(Console.ReadLine()); //N마리의 말 힘 입력
}
Console.WriteLine("answer"); //결과 출력
}
}베이스로 입력된 화면입니다. N마리의 말을 첫째줄에 입력받았고, 그 다음 줄에는 N번째에 해당하는 말의 힘을 입력받았습니다.
일단 생각나는데로 적어보자면, n마리의 말을 힘 별로 정렬시켜야합니다. 이어서 반복문을 통해 인덱스별로 차이값을 구해 제일 낮은 값을 저장합니다. 이때 해당인덱스가 몇번인지 기록합니다. 가장 낮은 값이 갱신되지 않으면 이 값을 가진 인덱스 2개를 힘이 가장 비슷한 말이라고 보면 됩니다.
이렇게 풀리는지 살펴보겠습니다.
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
//n마리를 힘대로 차례대로 나열한다
//루프를 통해 인덱스별로 차이값을 도출한다
//차이값이 최소인 인덱스 두 개를 고른다
class Solution {
static void Main(string[] args)
{
int N = int.Parse(Console.ReadLine()); //N마리의 말
List<int> horseList = new List<int>(); //N마리의 말을 보관할 LIst
for (int i = 0; i < N; i++)
{
int pi = int.Parse(Console.ReadLine()); //말 한마리의 힘
horseList.Add(pi); //List에 그대로 저장
}
SelectionSort(horseList); //선택정렬로 힘 별로 정렬
int result = FindMinimumValue(horseList); //제일 차이가 적은 값을 찾기
Console.WriteLine(result);
}
///////////////////////// 차이값을 구하는 코드
static int FindDifferenceValue(List<int> list, int startIndex)
{
if (list.Count == 1) return list[0];
int firstValue = list[startIndex];
int minSub = Math.Abs(list[0] - list[1]);
for (int i = startIndex + 1; i < list.Count; i++)
{
if (Math.Abs(firstValue - list[i]) < minSub)
{
minSub = Math.Abs(firstValue - list[i]);
}
}
return minSub;
}
///////////////////////// 배열 내에서 최소 차이값을 구하는 코드
static int FindMinimumValue(List<int> list)
{
int minNum = FindDifferenceValue(list, 0);
for (int i = 0; i < list.Count; i++)
{
if (FindDifferenceValue(list, i) < minNum)
{
minNum = FindDifferenceValue(list, i);
}
}
return minNum;
}
//////////////////////// 스왑 함수
static void Swap(List<int> list, int a, int b)
{
int tmp = list[a];
list[a] = list[b];
list[b] = tmp;
}
//////////////////////// 배열에서 최솟값 찾는 함수
static int IndexOfMinimum(List<int> list, int startPoint)
{
int minNum = list[startPoint];
int minIndex = startPoint;
for (int i = startPoint + 1; i < list.Count; i++)
{
if (list[i] < minNum)
{
minNum = list[i];
minIndex = i;
}
}
return minIndex;
}
//////////////////////// 선택정렬 함수
static void SelectionSort(List<int> list)
{
for (int i = 0; i < list.Count; i++)
{
var minIndex = IndexOfMinimum(list, i);
Swap(list, i, minIndex);
}
}
}
우선 함수로 (1)선택정렬 함수를 만들고 수를 정렬시킵니다. 그 후 (2)배열의 특정인덱스를 다른 모든 수와 비교하여 최소차이값을 구하는 함수를 만들었습니다. 그리고 이 함수를 이용해서 (3)전체 배열 중 최소차이값을 구하는 함수를 만들었습니다. 이렇게 배열 내 최소의 차이값을 출력하는 프로그램을 만들었습니다.
첫 번째, 두 번째 테스트 케이스를 무난하게 통과했습니다.
하지만 세 번째 경우는 통과하지 못했습니다. 역시나 선택정렬(O(n^2))을 쓴 결과 타임 초과가 나버리고 말았습니다. 그럼 위 코드에서 선택정렬 코드를 시간처리가 빠른 다른 정렬 코드로 바꿔줘야합니다. 이런게 가능한 정렬로는 대표적으로 퀵 정렬이 있습니다.
그럼 정렬 부분을 다르게해서 다시 풀어보겠습니다.
//19.10.02작성완료 이후 정렬에 대해 배우고나서 다시 작성예정