[코딩테스트 일지 - 99클럽] 4일차 - 소수 찾기
코딩 테스트 준비 일지 4 일차
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbers return
"17" 3
"011" 2
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.
문제 풀이 접근
어제와 별다를 것 없이 시원하게 1차로 생각했던 방식은 1시간동안 풀어도 답이안나와서 시원하게 날려먹었다.
결국 어제보다 더 돌아가서 1시간 날려먹기 + 1시간 30분만에 새로운 방식 찾고 문제 풀이하여 2시간 30분만에 정답을 찾았다.
여기서 날려먹은 방식은 내가 임의로 모든 카드를 다 사용하여 만드는 숫자겠지? 라는 생각에 빠져서 시간을 허비했다. 결국 총 3장을 주던, 5장을 주던, 마음대로 카드를 사용하여 숫자를 만들고, 이 숫자들의 집합에서 소수 판별을 하여 갯수를 리턴해라가 핵심이다.
결국 처음 생각한 문제 해결 플로우는 정답이었으나, 내부 로직에 대한 판단이 실패를 해버린 결과가 2시간 30분이다.
이 문제의 핵심은 아래와 같다.
1. 주어진 수를 분리하라.
2. 분리하여 만들 수 있는 모든 가지의 수 조합을 생성하라
3. 이 수 조합을 숫자로 변환하여 소수 판별을 진행하고, 혹시 모르니 판별 상 통과한 수에 대해 담고 있을 List<int> Collector 를 만들어서 이미 한번 패스한 숫자에 대한 필터링을 진행해라.
여기서 2번은 조합을 써도되고 순열을 써도되고, BFS, DFS 하고싶은 방식으로 만든다
나는 DFS 방식으로 순회하고 String 값에 Depth 마다 하나씩 더해주면서 소수 판단을 하여 답을 이끌어 냈다.
방향 잘못 잡은 코드 작성 ( C# )
using System;
using System.Collections.Generic;
public class Solution {
public int solution(string numbers) {
List<int> numberList = new List<int>();
for (int i = 0; i < numbers.Length; ++i) //분리
numberList.Add(numbers[i] - 48);
List<int> result = new List<int>(); // 모음을 담아놓을 것
// 한자릿 수는 먼저 결과에 넣어두기
for(int i = 0; i < numberList.Count; ++i)
{
if (result.Contains(numberList[i]) == true) continue;
result.Add(numberList[i]);
}
for (int i = 0; i < numberList.Count; ++i)
{
for (int j = 0; j < numberList.Count; j++)
{
//if (i == j) continue;
char[] numToString = numbers.ToCharArray();
char temp = numToString[j];
numToString[j] = numToString[i];
numToString[i] = temp;
numbers = new string(numToString);
int value = int.Parse(numbers);
if (result.Contains(value) == true) continue;
result.Add(value);
}
}
// 0, 1 인 수 빼기 == 소수의 정의에 맞지 않음
result.RemoveAll(rhs => rhs == 1);
result.RemoveAll(rhs => rhs == 0);
// 1과 나 자신 이외의 나머지가 0 이 되는수 ==> 나눠지는 수,
//소수에 부합하지 않음. 삭제
int answer = result.Count;
for (int i = 0; i < result.Count; ++i)
{
int resultValue = result[i];
for (int j = 2; j < resultValue; ++j)
{
if(j == 2) continue;
if (resultValue % j == 0)
{
--answer;
break;
}
}
}
return answer;
}
}오답 채점 결과
정답 작성 코드 ( C# )
public class Solution
{
static List<int> resultCollector = new List<int>();
public int solution(string numbers)
{
bool[] isVisit = new bool[10];
int[] numberArr = new int[numbers.Length];
for (int i = 0; i < numbers.Length; ++i)
numberArr[i] = numbers[i] - 48;
string newString = string.Empty;
int answer = 0;
DFS(numberArr, isVisit, 0, newString, ref answer);
return answer;
}
public void DFS(int[] arr, bool[] isVisit, int depth, string numberString, ref int answerCnt)
// DFS 로 찾는다.
{
for (int i = depth; i < arr.Length; ++i)
{
var element = arr[i];
SwapCharacter(arr, i, depth);
DFS(arr, isVisit, depth + 1, numberString + element, ref answerCnt);
int parseInt = int.Parse(numberString + element);
if (resultCollector.Contains(parseInt) == false && isPrimeCheck(parseInt) == true)
{
resultCollector.Add(parseInt);
++answerCnt;
}
SwapCharacter(arr, depth, i);
}
}
public void SwapCharacter(int[] arr, int x, int y)
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
public bool isPrimeCheck(int number)
{
if (number == 0) return false;
if (number == 1) return false;
// 0, 1 은 소수가 아니다.
if (number == 2) return true;
// 2는 소수다.
for (int i = 2; i < number; ++i)
{
if (number % i == 0)
return false;
}
// 0 으로 나눠진다면 소수가 아니다.
return true;
}
}코드 결과
