10816번 숫자 카드 2, 1764번 듣보잡 , 1269번 대칭 차집합 , 11478번 서로 다른 부분 문자열의 개수, 1934번 최소공배수, 1735번 분수 합, 2485번 가로수
코딩테스트 : 10816번 숫자 카드 2
| 1 초 | 256 MB | 172445 | 68832 | 48975 | 38.230% |
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
string n = Console.ReadLine();
Dictionary<int, int> numbers = new Dictionary<int, int>();
int[] array = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int i = 0; i < array.Length; i++)
{
if (!numbers.ContainsKey(array[i]))
{
numbers.Add(array[i], 1);
}
else
{
numbers[array[i]]++;
}
}
StringBuilder sb = new StringBuilder();
string m = Console.ReadLine();
int[] array2 = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int i = 0; i < array2.Length; i++)
{
if (numbers.ContainsKey(array2[i]))
{
sb.Append(numbers[array2[i]] + " ");
}
else
{
sb.Append(0 + " ");
}
}
Console.WriteLine(sb);
}
}왜.. 한 번에 맞지.. ?
코딩테스트 : 1764번 듣보잡
| 2 초 | 256 MB | 129745 | 56395 | 44109 | 41.741% |
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int n = NM[0];
int m = NM[1];
Dictionary<string, int> dic = new();
List<string> list = new();
for (int i = 0; i < n; i++)
{
string s = Console.ReadLine();
dic.Add(s,1);
}
StringBuilder sb = new();
int count = 0;
for (int i = 0; i < m; i++)
{
string s = Console.ReadLine();
if (dic.ContainsKey(s))
{
list.Add(s); count++;
}
}
list.Sort();
Console.WriteLine(count);
for (int i = 0; i < list.Count; i++)
{
sb.AppendLine(list[i]);
}
Console.WriteLine(sb);
}
}다른 사람의 흥미로운 풀이
HashSet에서 SortedSet을 사용하는 방법도 있다. 다만 나는 Dic 연습을 위해서 !
코딩테스트 : 1269번 대칭 차집합
| 2 초 | 256 MB | 39130 | 25278 | 20964 | 65.136% |
문제
자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.
예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.
입력
첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.
출력
첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int n = NM[0];
int m = NM[1];
Dictionary<int, int> dic = new Dictionary<int, int>();
int[] N = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int[] M = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int i = 0; i < n; i++)
{
dic.Add(N[i], 1);
}
for (int i = 0; i < m; i++)
{
if ( !dic.ContainsKey(M[i]))
{
dic.Add(M[i], 1);
}
else
{
dic[M[i]]++;
}
}
int count = 0;
foreach (int key in dic.Keys)
{
if (dic[key] == 1) count++;
}
Console.WriteLine(count);
}
}다른 사람의 흥미로운 풀이
HashSet에 SymmetricExceptWith이라는 것도 있다..
코딩테스트 : 11478번 서로 다른 부분 문자열의 개수
| 1 초 | 512 MB | 36208 | 22927 | 18480 | 63.823% |
문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.
입력
첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.
출력
첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.
using System;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
string s = Console.ReadLine();
int n = s.Length;
int count = 0;
for (int i = 1; i <= n; i++)
{
List<string> str = new();
for (int j = 0; j <= n-i; j++)
{
string temp = s.Substring(j, i);
str.Add(temp);
}
str = str.Distinct().ToList();
count += str.Count;
}
Console.WriteLine(count);
}
}
distinct 기능을 알고 있어서 쉽게 풀었다.
다른 사람의 흥미로운 풀이
이것도 HashSet이용해서, ( 중복으로 넣을 수 없는 부분을 이용) 쉽게 풀 수 있다.
이제 다음 부분인 약수, 배수와 소수 2 !
코딩테스트 : 1934번 최소공배수
| 1 초 | 128 MB | 89880 | 48739 | 41389 | 55.045% |
문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)
출력
첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.
using System;
using System.Collections.Immutable;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int s = int.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s; i++)
{
int[] numbers = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
List<int> list = new List<int>();
list.AddRange(numbers);
list.Sort();
list.Reverse();
int a = numbers[0];
int b = numbers[1];
int c = a * b;
int result = 0;
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
result = a;
}
int answer = c/result;
sb.AppendLine(answer.ToString());
}
Console.WriteLine(sb.ToString());
}
}유클리드 호제법이라는 것을 검색해서 풀었다.
신기한 방법이고 수학 문제인 것 같다.
코딩테스트 : 1735번 분수 합
| 2 초 | 128 MB | 42391 | 19737 | 17235 | 47.217% |
문제
분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.
두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.
입력
첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.
출력
첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.
using System;
using System.Collections.Immutable;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int[] N = Console.ReadLine().Split().Select(int.Parse).ToArray();
int[] M = Console.ReadLine().Split().Select(int.Parse).ToArray();
int Na = N[0];
int Nb = N[1];
int Ma = M[0];
int Mb = M[1];
int numerator = Na * Mb + Nb * Ma;
int denominator = Nb * Mb;
int min = Math.Min(numerator, denominator);
for (int i = 2; i <= min; i++)
{
if (numerator % i == 0 && denominator % i == 0)
{
numerator /= i;
denominator /= i;
i--;
}
}
Console.WriteLine($"{numerator} {denominator}");
}
}다른 사람의 흥미로운 풀이
다른 사람들보다 시간을 너무 많이 써서 확인해 봤더니, 이 문제도 유클리드 호제법을 사용해서 풀면 더 빠르고 쉽게 풀린다. 나는 지금 더 이상 나눌 수 없더라도 모든 진행을 다 해야하는 for문을 사용했기 때문이다.
코딩테스트 : 2485번 가로수
| 1 초 | 128 MB | 30886 | 12870 | 10594 | 42.466% |
문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.
입력
첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.
출력
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.
using System;
using System.Collections.Immutable;
using System.Net.Sockets;
using System.Text;
public class Program
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] numbers = new int[n];
for (int i = 0; i < n; i++)
{
numbers[i] = int.Parse(Console.ReadLine());
}
int[] minus = new int[n - 1];
for (int i = 0; i < n-1; i++)
{
minus[i] = numbers[i+1] - numbers[i];
}
int gcd = GCD(minus[0], minus[1]);
for (int i = 1; i < minus.Length -1 ; i++)
{
gcd = GCD(gcd, minus[i + 1]);
}
int GCD(int a, int b)
{
int A = Math.Max(a, b);
int B = Math.Min(a, b);
while (B != 0)
{
int temp = B;
B = A % B;
A = temp;
}
return A;
}
int D = numbers[numbers.Length - 1] - numbers[0];
int result = D / gcd;
int answer = result + 1 - numbers.Length;
Console.WriteLine(answer);
}
}마찬가지로 지금 심어져 있는 가로수 사이의 거리들의 최소공약수를 구하고, 전체 길이에서 몇 개를 심어야 하는지 구한 뒤, 이미 심어져 있는 것들을 빼 주면 된다.
다른 사람의 흥미로운 풀이
arr[^1] 이란 표기가 있었다. 이건 '배열의 마지막 요소'를 의미한다는 뜻인걸 처음 알았다.