오늘 배운 내용
에라토스테네스의 체 소수 만들기
주어진 숫자들의 조합으로 만들수 있는 소수의 수를 구하는 문제였다.
전에 코드테스트를 준비할 때 수학문제에서 엄청 힘들었었는데 힘들었던 만큼 기억에 남은것 같다
에라토스테네스의 체의 이름은 정확히 기억은 못했지만 , 어떤식으로 구현하는지는 기억이 났다
에라토스테네스의 체란 prime여부를 저장할 배열을 만들어준 후 앞에서부터 해당 수의 배수를
전부다 prime이 아니라고 저장하면서 반복 해주는 알고리즘이다.
이렇게 해서 생긴 bool 배열에는 각 수들의 소수인지 아닌지에 대한 여부가 저장된다.
using System;
using System.Linq;
using System.Collections.Generic;
class Solution
{
int[] nums;
public int solution(int[] _nums)
{
nums = _nums;
// 일단 3개의 수를 더하는 조합을 리스트로 뽑아서
// 그 수들이 소수인지 검사
// 소수검사는 에리스토의 체? -> 에라토스테네스의 체 ㅋㅋ
List<int> combination = new List<int>();
MakeList(combination);
return primeCheck(combination);
}
public void MakeList(List<int> combination)
{
for (int i = 0; i < nums.Length - 2; i++)
{
for (int j = i+1; j < nums.Length - 1; j++)
{
for (int k = j+1; k < nums.Length; k++)
{
combination.Add(nums[i] + nums[j] + nums[k]);
}
}
}
}
public int primeCheck(List<int> combination)
{
// 2부터 처음 선택하는 수는 소수
// 그런데 선택 된 수의 배수들은 소수가 아님으로
// bool 배열을 통해서 NotPrime = true 처리를한다.
int max = combination.Max();
int count = 0;
bool[] NotPrime = new bool[max+1];
for (int i = 2; i <= max; i++)
{
if (NotPrime[i]) continue;
for (int j = i * 2; j <= max; j += i)
{
NotPrime[j] = true;
}
}
foreach (int num in combination)
{
if (!NotPrime[num])
{
count++;
}
}
return count;
}
}
기사단원의 무기
이번에 문제를 풀기 시작하면서 처음으로 시간 초과가 뜬거같다.
수의 약수의 배열을 만들어서 그 합을 구하는데 limit를 초과하면 power로 바꿔서 더해주는 문제였다.
number가 100,000 배열의길이가 10만이 되고 각 약수를 구할때 100,000 * 100,000의 이중 for문으로 작동하기 때문에 개선이 필요하다
앞에서 부터 해당 수의 배수를 구하면서 전부 +1씩 해주는 방식은 어떤가? 라는 생각이 들었고
그렇게 하니 수가 커질수록 배수의 숫자가 줄어들기 때문에 시간 초과를 해결할 수 있었다.
using System;
public class Solution {
public int solution(int number, int limit, int power) {
// 기사의 번호의 약수에 해당하는 무기를 구매
// 제한 수치보다 큰 무기인 경우 지정해준 무기를 구매해야됨
// 모든기사에게 무기를 만들어주기 위한 철의 무게를 계산해야됨
// 1. 각 기사들의 약수의 개수 즉, 필요한 무기의 공격력을 리스트로 만들어준다.
// 기사의 번호는 1번부터기 떄문에 0을 버림
int[] array = new int[number+1];
int answer = 0;
for(int i =1; i<= number; i++)
{
for (int j = i; j <= number; j+=i)
{
array[j] += 1;
}
}
//이제 배열을 돌면서 limit보다 큰값의 경우 power을 더함
for(int i =1; i< number+1; i++)
{
answer += array[i] > limit ? power : array[i];
}
return answer;
}
}
/*
시간초과 발생 테스트 케이스 : 11~16,18,24~25
number가 100,000 배열의길이가 10만이 되고
각 약수를 구할때 100,000 * 100,000의 이중 for문으로 작동하기 때문에 개선이 필요하다
앞에서 부터 해당 수의 배수를 구하면서 전부 +1씩 해주는 방식은 어떤가?
public class Solution {
public int solution(int number, int limit, int power) {
// 기사의 번호의 약수에 해당하는 무기를 구매
// 제한 수치보다 큰 무기인 경우 지정해준 무기를 구매해야됨
// 모든기사에게 무기를 만들어주기 위한 철의 무게를 계산해야됨
// 1. 각 기사들의 약수의 개수 즉, 필요한 무기의 공격력을 리스트로 만들어준다.
// 기사의 번호는 1번부터기 떄문에 0을 버림
int[] array = new int[number+1];
int answer = 0;
for(int i =1; i<= number; i++)
{
array[i] = NumDivisor(i);
}
//이제 배열을 돌면서 limit보다 큰값의 경우 power을 더함
for(int i =1; i< number+1; i++)
{
answer += array[i] > limit ? power : array[i];
}
return answer;
}
public int NumDivisor(int num)
{
int count =0;
for(int i =1; i <= num ; i++)
{
count += num % i == 0 ? 1 :0;
}
return count;
}
}
*/
옹알이(2)
옛날에 한번 풀어봤던 문제인데 엄청 삽질하면서 오래걸렸다..
Replace를 활용해서 간단하게 만들고 싶었는데 연속적으로 단어를 출력하는 것을 막는 부분도 필요해서 여러 가지 시도해 보다가
제일 먼저 연속 단어를 체크하는 부분을 추가했다.
그리고 나서 또 문제가 발생한 것은 Replace를 사용했기때문에
단어들이 한번에 빠져버려서 원래는 안되는 경우의수가 되는 경우의수로 바뀌어 버리는 결과가 나왔다.
앞에서 순서대로 해야겠다 라는 생각이 들었고 그렇게 하려다보니 뭔가 코드가 복잡해지고 꼬이는 듯했다.
그런데 마지막에 결국 아이디어가 떠올랐는데
결국 통과를 하려면 어떤 단어를 먼저 Replace를 해도 똑같은 결과값이 나와야 한다는 생각이 났고
그러면 순서를 다르게해서 Replace를 여러번 한 다음 결과를 교차 검증하는게 어떨까? 라는 생각이 들었다.
그리고 결국 문제를 해결할 수 있었다.
using System;
public class Solution
{
public int solution(string[] babbling)
{
string[] continous = new string[]{"ayaaya","yeye","woowoo","mama"};
string[][] possible = new string[4][];
possible[0] = new string[]{"aya","ye","woo","ma"};
possible[1] = new string[]{"ye","aya","woo","ma"};
possible[2] = new string[]{"woo","ye","aya","ma"};
possible[3] = new string[]{"ma","ye","woo","aya"};
//string 배열을 순회하면서
// 각각의 스트링을 만들수 있는지 판별
// Replace로 하게되면 원래 안되다가 삭제해서 되는 경우가 발생함
// 순서를 지켜서 확인을 해야된다. - > 교차검증으로 확인함
int count = 0;
foreach(string babStr in babbling)
{
string temp = babStr;
// 연속인것을 걸러내야되고
foreach(string conWord in continous)
{
temp = temp.Replace(conWord,"");
}
if(temp.Length != babStr.Length) continue;
int[] length = new int[4];
for(int i =0; i< 4; i++)
{
temp = babStr;
foreach(string posWord in possible[i])
{
temp= temp.Replace(posWord,"");
}
length[i] = temp.Length;
}
// possible의 순서가 다를때도 0이여됨
bool isSuccess = true;
for(int i =0; i< 4; i++)
{
if(length[i] != 0){
isSuccess = false;
}
}
if(isSuccess){
count++;
}
}
return count;
}
}
