코딩테스트 : 4948번 베르트랑 공준
| 1 초 | 256 MB | 114091 | 45375 | 36187 | 39.127% |
문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
제한
- 1 ≤ n ≤ 123,456
using System;
using System.Text;
public class Solution
{
private static void Main()
{
bool[] isPrime = new bool[300000];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < isPrime.Length; i++)
{
for (int j = 2; j <= (int)MathF.Sqrt(i)+1; j++)
{
if (i % j == 0)
{
break;
}
if (j > MathF.Sqrt(i))
{
isPrime[i] = true;
}
}
}
isPrime[2] = true;
StringBuilder sb = new StringBuilder();
while (true)
{
int n = Int32.Parse(Console.ReadLine());
if (n == 0) break;
int count = 0;
for (int i = n+1; i <= 2 * n; i++)
{
if (isPrime[i]) count++;
}
sb.AppendLine(count.ToString());
}
Console.WriteLine(sb.ToString());
}
}
소수 판별을 조금 바꿔봤는데 2를 예외처리를 따로 해 주어야 한다.
다른 사람의 흥미로운 풀이
리스트를 만들고, 리스트에 2,3 그리고 그 이후로는 2씩 더해가며 숫자를 넣는다.
그리고 다음처럼 검사한다.
while (list[0] < f) // 리스트의 첫 번째 원소(가장 작은 수)가 f(498)보다 작을 때만 실행
{
answer.Add(list[0]); // 첫 번째 원소를 소수로 저장
list = list.Where(x => x % answer.Last() != 0).ToList(); // 소수의 배수를 제거
}f 는 (우리의 배열 숫자를 제곱근한 값)
이해하느라 한 오 분 걸렸다.
리스트의 첫 번째 원소 (첫 실행에는 2)를 answer, 즉 소수 확정인 리스트에 저장하고
새로운 리스트를 만드는데 이 리스트는 원래 리스트에서 answer의 마지막 값(현재 2)의 배수를 모두 제거한 리스트이다.
이를 반복하다보면 리스트의 첫 번째 원소가 점차 커져 ( 배수들이 계속 제거되므로) f보다 큰 값이 될 텐데 그러면 종료된다.
이는 내가 알고 있었던 소수를 검사할 때 검사할 수의 제곱근까지만 검사하면 그 이후는 검사하지 않아도 된다는 사실에서부터 에라토스테네스의 체 방식을 사용하는 색다른 방식이라 신기했다.
코딩테스트 : 17103번 골드바흐 파티션
| 0.5 초 | 512 MB | 37539 | 13821 | 10657 | 34.735% |
문제
- 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
입력
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
출력
각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
List<int> list = new List<int>() { 2 };
List<int> Prime = new List<int>();
for (int i = 3; i <= 1000000; i += 2)
{
list.Add(i);
}
int n = (int)MathF.Sqrt(1000000.0f) +1;
while (list[0] < n)
{
Prime.Add(list[0]);
list = list.Where(x => x % Prime.Last() != 0).ToList();
}
Prime.AddRange(list);
StringBuilder sb = new StringBuilder();
int number = int.Parse(Console.ReadLine());
for (int i = 0; i < number; i++)
{
int temp = int.Parse(Console.ReadLine());
int count = 0;
for (int j = 0; j <= Prime.Count-1; j++)
{
int exits = temp - Prime[j];
if (exits > 1)
{
if (Prime.Contains(exits))
{
count++;
if (exits == Prime[j]) count++;
}
}
}
// 하나일 가능성이 있다. Ex) 3+3 = 6
if (count >= 2)
{
count /= 2;
}
sb.AppendLine(count.ToString());
}
Console.WriteLine(sb.ToString());
}
}
시간...초과가 떴다. 위의 코드를 응용해보려고 했는데 시간 제한이 0.5초다.
아마 검사하는 시간이 오래 걸리는 것 같다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
List<int> list = new List<int>() { 2 };
List<int> Prime = new List<int>();
for (int i = 3; i <= 1000000; i += 2)
{
list.Add(i);
}
int n = (int)MathF.Sqrt(1000000.0f) +1;
while (list[0] < n)
{
Prime.Add(list[0]);
list = list.Where(x => x % Prime.Last() != 0).ToList();
}
Prime.AddRange(list);
Dictionary<int, bool> primeDict = Prime.ToDictionary(x => x, x => true);
StringBuilder sb = new StringBuilder();
int number = int.Parse(Console.ReadLine());
for (int i = 0; i < number; i++)
{
int temp = int.Parse(Console.ReadLine());
int count = 0;
for (int j = 0; j <= Prime.Count-1; j++)
{
int exits = temp - Prime[j];
if (exits > 1)
{
if (primeDict.ContainsKey(exits))
{
count++;
if (exits == Prime[j]) count++;
}
}
}
// 하나일 가능성이 있다. Ex) 3+3 = 6
if (count >= 2)
{
count /= 2;
}
sb.AppendLine(count.ToString());
}
Console.WriteLine(sb.ToString());
}
}Dictionary로 바꿔서 성공... 이나 남들보다 많은 메모리와 긴 시간이 걸렸다.
다른 사람의 흥미로운 풀이
for (int p = 2; p <= 1_000_000; p += p == 2 ? 1 : 2) 이런 식으로 더하는 방법도 있었다. 2일때만 1을 더하고 나머지는 2를 더함 !!
코딩테스트 : 28278번 스택2
| 2 초 | 1024 MB | 45563 | 16721 | 13876 | 37.031% |
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
- 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
- 3: 스택에 들어있는 정수의 개수를 출력한다.
- 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
- 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.
입력
첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
출력을 요구하는 명령은 하나 이상 주어진다.
출력
출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
int s = int.Parse(Console.ReadLine()!);
List<int> list = new List<int>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s; i++)
{
int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
if (nums[0] == 1)
{
list.Add(nums[1]);
}
else if (nums[0] == 2)
{
if (list.Count > 0)
{
sb.AppendLine(list[list.Count - 1].ToString());
list.RemoveAt(list.Count - 1);
}
else
{
sb.AppendLine("-1");
}
}
else if (nums[0] == 3)
{
int n = list.Count;
sb.AppendLine(n.ToString());
}
else if (nums[0] == 4)
{
if (list.Count > 0)
{
sb.AppendLine("0");
}
else
{
sb.AppendLine("1");
}
}
else if (nums[0] == 5)
{
if (list.Count > 0)
{
sb.AppendLine(list[list.Count - 1].ToString());
}
else
{
sb.AppendLine("-1");
}
}
}
Console.WriteLine(sb.ToString());
}
}
왜 한번에 되는거지 불안하게..
다른 사람의 흥미로운 풀이
아니 보니까 그냥 Stack이란 자료형이 있다. 난 바보다.
코딩테스트 : 10773번 제로
| 1 초 | 256 MB | 111249 | 76020 | 61464 | 68.420% |
문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.
재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.
재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.
재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!
입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.
using System;
using System.Runtime.CompilerServices;
using System.Text;
public class Solution
{
private static void Main()
{
int k = Convert.ToInt32(Console.ReadLine());
Stack<int> stack = new Stack<int>();
for (int i = 0; i < k; i++)
{
int number = Convert.ToInt32(Console.ReadLine());
if (number == 0)
{
stack.Pop();
}
else
{
stack.Push(number);
}
}
int result = 0;
while (stack.Count > 0)
{
int n= stack.Pop();
result += n;
}
Console.WriteLine(result);
}
}
주의할 점
for (int i = 0; i < stack.Count; i++)
{
int n= stack.Pop();
result += n;
}뭐가 이상하냐구 ?
내 의도와는 달리 stack.Count가 가변적이다. stack.Pop하면서 하나씩 사라진다.
'코딩테스트' 카테고리의 다른 글
| 28279번 덱 2, 2346번 풍선 터뜨리기 (0) | 2025.02.07 |
|---|---|
| C# 백준 - 9012번 괄호, 4949번 균형잡힌 세상, 12789번 도키도키 간식드리, 18258번 큐 2, 11866번 요세푸스 문제 O (1) | 2025.02.05 |
| 13909번 창문 닫기, 1929번 소수 구하기, 4134번 다음 소수 (0) | 2025.02.04 |
| 10816번 숫자 카드 2, 1764번 듣보잡 , 1269번 대칭 차집합 , 11478번 서로 다른 부분 문자열의 개수, 1934번 최소공배수, 1735번 분수 합, 2485번 가로수 (0) | 2025.02.03 |
| 1620번 나는야 포켓몬 마스터 이다솜 (0) | 2025.02.02 |