코딩테스트 : 1010번 다리 놓기
문제
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)
재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
using System;
using System.Text;
public class Solution
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
int[] nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int N = nums[0];
int M = nums[1];
sb.AppendLine(Combinaition(M, N).ToString());
}
Console.WriteLine(sb.ToString());
}
public static int Combinaition(int M, int N)
{
int result = 1;
for (int i = 0; i < N; i++)
{
result *= (M-i);
result /= (i+1);
}
return result;
}
}
처음에 문제를 보고 왜... 이게 어렵지.. ? 생각하다가 '조합'과 '순열'에 대한 개념을 다시 찾아봤다.
그리고 문제를 다시 읽어보니, 결국 조합을 선택하라는 것과 같은 문제였다.
어떤 조합을 선택하든, 가장 위에 선택된 오른쪽 다리는 , 왼쪽 다리에서 남은 것 중 가장 위의 다리와 연결된다.
즉, 오른쪽 다리를 선택하는 경우의 수.. 만 구하면 된다는 것이다. 그리고 다리는 모두 다르므로 조합으로 !
오래 걸렸던 것은 int 타입, long 타입으로 구했을 때 모두 숫자가 부족했다.
(가짓수가 최대 29 X 29 였기 때문에 팩토리얼로 구하면 숫자가 넘치게 된다)
그래서 중간에 나누어 주면서 진행해야 하고, 이를 생각해 내는데까지 조금 오래 걸렸다.
내 생각에는 / 는 나머지를 연산하지 않기에, 숫자에 오류가 있을 것이라고 생각했기 때문이다.
하지만, 생각해보면 '임의의 N개의 연속된 정수에는 반드시 1부터 N까지의 배수가 포함된다'
예를 들어 N은 2일 때, 어떤 연속된 정수 중 하나는 반드시 짝수이다. (2를 약수로 갖는다).
또, N이 3일 때 어떤 연속된 N개의 정수 중 하나는 반드시 3을 약수로 갖는다.
왜냐하면 어떤 정수가 %3을 했을 때 나올 수 있는 경우의 수는 0 , 1, 2가 되는데, 0은 3의 배수이므로 1 혹은 2가 나온다.
연속된 3개의 정수라면, 1을 더해주고, 2를 더해준 것이기 때문에 결국 연속된 3개의 정수 중 하나는 3의 배수이다.
이런 식으로, 순차적으로 진행했을 때에도 잘 작동되는 것을 알 수 있다.
DP로도 푸는 방법이 있다고 하는데 나중에 또 해봐야지.
코딩테스트 : 2108번 통계학
문제
수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.
산술평균 : N개의 수들의 합을 N으로 나눈 값
중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
최빈값 : N개의 수들 중 가장 많이 나타나는 값
범위 : N개의 수들 중 최댓값과 최솟값의 차이
N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.
출력
첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
둘째 줄에는 중앙값을 출력한다.
셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
넷째 줄에는 범위를 출력한다.
using System;
using System.Text;
public class Solution
{
public static void Main()
{
int[] array = new int[8001];
int n = int.Parse(Console.ReadLine());
for (int i = 0; i < n; i++)
{
int x = int.Parse(Console.ReadLine());
array[x + 4000]++;
}
int sum = 0;
for (int i = 0; i < array.Length; i++)
{
sum += array[i] * (i - 4000);
}
double divided = (double)sum / n;
sum =(int)Math.Round(divided);
int averageIndex = n / 2 + 1;
int count = 0;
int middle = 0;
for (int i = 0; i < array.Length; i++)
{
count += array[i];
if (count >= averageIndex)
{
middle = i - 4000;
break;
}
}
// 최빈'값'
int mode = 0;
// 최빈값 등장 수
int modeIndex = 0;
// 같을때 저장해두기 위한 리스트
List<int> modeList = new List<int>();
for (int i = 0; i < array.Length; i++)
{
if (array[i] > modeIndex)
{
modeIndex = array[i];
modeList.Clear();
mode = i - 4000;
modeList.Add(mode);
}
else if (array[i] == modeIndex)
{
mode = i - 4000;
modeList.Add(mode);
}
}
if (modeList.Count > 1)
{
mode = modeList[1];
}
int max = int.MinValue;
int min = int.MaxValue;
for (int i = 0; i < array.Length; i++)
{
if (array[i] > 0)
{
min = i - 4000;
break;
}
}
for (int i = array.Length - 1; i >= 0; i--)
{
if (array[i] > 0)
{
max = i - 4000;
break;
}
}
int answer = max - min;
Console.WriteLine(sum);
Console.WriteLine(middle);
Console.WriteLine(mode);
Console.WriteLine(answer);
}
}
이 노다가 문제를 왜 가져왔는고 하니.. .바로 int 형이나 float 형으로 산술평균을 구했을 때는 안되던 것이
Double형으로 바꿔줬을 때 되었기 때문이다. 왜..그런걸까... 소숫점 이하 첫 번째 자리에서 반올림하는거면 상관 없지 않나 ?
내 생각은 바로 0.49999라도 0.4에서 반올림 하는 것.. 이라고 생각했는데 이 글을 보니 아닌 것 같다.
반올림 할 때에는 끝에서부터 하나씩 올라가면서 계산하기에 이런 오류가 발생한 것 같다.
--- 가 아니였다. 같은 숫자가 되는게 아니라 나눌 때 부동소수점 오차가 발생한다.
다른 사람의 흥미로운 풀이
Linq나... Dictionary를 사용하면 더 간편하게 할 수 있었다.
코딩테스트 : 20920번 영단어 암기는 괴로워
문제
화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.
- 자주 나오는 단어일수록 앞에 배치한다.
- 해당 단어의 길이가 길수록 앞에 배치한다.
- 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.
입력
첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1≤N≤100000, 1≤M≤10)
둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.
단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.
출력
화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.
using System;
using System.Text;
public class Solution
{
public static void Main()
{
int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int rows = input[0];
int M = input[1];
Dictionary<string,int> dic = new Dictionary<string, int>();
for (int row = 0; row < rows; row++)
{
string line = Console.ReadLine();
if (line.Length >= M)
{
if (!dic.ContainsKey(line)) dic.Add(line, 1);
else dic[line]++;
}
}
var sorted = dic.OrderByDescending(x => x.Value).ThenByDescending(x => x.Key.Length).ThenBy(x => x.Key);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < sorted.Count(); i++)
{
sb.AppendLine(sorted.ElementAt(i).Key);
}
Console.WriteLine(sb.ToString());
}
}
이렇게 해서 시간 초과가 떴고,
foreach (var item in sorted)
{
sb.AppendLine(item.Key);
}
이것만 바꿔서 맞았다.
찾아보니 , OrderBy로 리턴한 타입은 IEnumerable 타입이 되어서 ElementAt(i)로 접근하면 처음부터 순회하면서 찾기에
각각 O(N)의 시간복잡도를 갖고 있고, 반복문이 더해져 O(N2)의 시간복잡도를 갖게 되어서 시간초과가 나왔던 것이다.
IEnumerable 타입에 대한 더 자세한 이해가 필요할 것 같다.
다른 사람의 흥미로운 풀이
'코딩테스트' 카테고리의 다른 글
| 2447번 별 찍기 -10, 11792번 하노이 탑 이동 순서 (0) | 2025.03.09 |
|---|---|
| 24060번 알고리즘 수업 병합 정렬 -1 , 4779번 칸토어 집합 (1) | 2025.03.03 |
| 비밀 코드 해독, 2884번 알람 시계, 가장 많이 받은 선물 (0) | 2025.02.23 |
| 신고 결과 받기, 택배 상자 꺼내기, [PCCP 기출문제] 1번 / 동영상 재생기 (0) | 2025.02.21 |
| 달리기 경주, 공원 산책 , 유연근무제 (0) | 2025.02.21 |