[프로그래머스] 완전탐색 > 소수찾기 (java)

레벨에 비해서 꽤나 푸는데 시간이 걸렸다...

아직은 알고리즘에 대한 지식이 너무 부족함을 느꼈다.

 

우선 나의 코드이다.

public int solution(String number) {

		List<String> numbers = stringToStringList(number);

		List<String> result = new ArrayList<>();
		Set<Integer> resultSet = new HashSet<>();
		for (int i = 1; i <= numbers.size(); i++) {
			permutation(numbers, result, resultSet, numbers.size(), i);
		}

		int answer = resultSet.size();

		return answer;
	}

	/**
	 * 순열 구하기
	 * 
	 * @param arr    : 기준 리스트
	 * @param result : 순열 부분집합을 담아줄 리스트
	 * @param resultSet : 소수인 값을 저장하기 위한 집합
	 * @param n      : 전체 갯수
	 * @param r      : 뽑을 갯수
	 */
	private void permutation(List<String> arr, List<String> result, Set<Integer> resultSet, int n, int r) {

		if (r == 0) {

			String numStr = "";
			for(int i = 0; i < result.size(); i++) {
				numStr = numStr + result.get(i);
			}
			int num = Integer.parseInt(numStr);
			if(isPrime(num)) {
				resultSet.add(num);
			}
			
			return;
		}

		for (int i = 0; i < n; i++) {
			result.add(arr.remove(i));
			permutation(arr, result, resultSet, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}
	}

	private List<String> stringToStringList(String num) {
		List<String> strList = new ArrayList<>();

		for (int i = 0; i < num.length(); i++)
			strList.add(Character.toString(num.charAt(i)));

		return strList;
	}

	private boolean isPrime(int num) {
		if (num < 2)
			return false;
		if (num == 2)
			return true;

		int i = 2;
		for (; i < num; i++) {
			if (num % i == 0)
				return false;
		}

		return true;
	}
}

[오늘의 배움]

    feat. 다른 사람의 코드 보기

 

1. 나는 String으로 되어있는 숫자를 하나씩 다루기 위해 List<String>으로 변환하였다.

결국 String도 Character의 배열임은 알고 있었지만 배열처럼 사용할 줄 몰라서 저렇게 List로 변환하였던 것이었는데,

몇몇 똑똑한 사람들은(내가 멍청한건가..) String.substring()이랑 String.charAt()을 이용해서 String자체를 배열처럼 사용하셨다...

 

2. 이 문제는 순열만을 사용하면 되었지만,

처음 구현하였을 때는 조합을 이용해서 제공된 숫자로 구할 수 있는 부분집합 들을 구하고

각 부분집합을 이용해서 순열을 적용해 풀었던 것이다.

글로 쓰니 나의 헛다리가 무슨 소리인지 모르겠어서 예를 들자면,

제공된 숫자가 12이면

1, 2 로 만들 수 있는 모든 조합을 구한다.

[1]

[2]

[1, 2]

그다음 이 각 부분 집합에 순열을 적용하였다.

[1] -> [1]

[2] -> [2]

[1, 2] -> [1, 2], [2, 1]

결국 순열의 결과가 나오는데, 그 당시에 이 아이디어를 생각해낸 나는 "유레카"를 외쳤다...

여튼 조합은 순열과 다르게 순서를 요하지 않기 때문에, 순열에서 중복을 제거한 것이 조합이므로,

나처럼 조합과 순열을 혼합하여 코드를 사용하는 일이 없어야 겠다.

 

3. isPrime() 함수를 구현하였는데,

나의 코드 같은 경우에는 모든 만들어진 수에 대해 isPrime() 함수를 이용해서 소수 여부를 판단한다.

또한 소수인 경우 소수인 수 - 1 까지 소수인지 판단하기 위해 for 문을 돌 것이다.

만약 엄청나게 큰 수를 판단해야한다면 엄청난 비용이 들 수도 있다.

하지만 좋은 코드에서는 isPrime을 다르게 구현하였다.

이는 다른 포스트에서 자세히 다뤄보겠다.

 

이상 오늘 한 문제를 가지고도 많은 헛다리와 많은 배움을 하게 되었다.