뚝딱뚝딱

자바 문법 정도만 레퍼런스를 받고, 알고리즘 자체는 직접 구현한 풀이 방법이다.

set을 활용한 부분에 있어서는 다른 사람들의 코드를 살펴보니 대부분 사용하는 편인 것 같았다.

전체적인 진행 방향은 다음과 같다.

1. 문자열에 들어 있는 0~9 숫자들을 INT 타입으로 바꾸어 int배열에 저장한다.
2. 배열에 저장된 수를 가지고, 직접 짠 조합 알고리즘을 통해 가능한 모든 숫자 조합을 찾아 SET 자료구조에 저장한다.
3. SET에 저장된 숫자가 소수인지 판별하여, 소수인 경우에만 카운트를 한다.

SET 자료구조

- 중복된 값을 저장하지 않아서 유니크한 값으로만 구성된다.
- Set 자료구조는 인터페이스라서 HashSet로 Integer를 명시해서 생성해야 한다.

• 문자열에 들어있는 숫자를 조합해 나올 수 있는 모든 수를 구해야 한다.
• permutation 함수를 이용할 수 있었는데, 존재를 까먹고 조합 알고리즘을 직접 구현함.
• 문자열의 각 숫자를 INT 형식으로 바꾸어 INT타입의 배열에 저장해줌.
• 그 INT배열을 가지고 숫자를 조합하는데, 중복된 숫자 값이 생성될 수 있으므로 Set 자료구조를 사용해서 중복된 값이 들어가지 않도록 하였음.
• 일단, 자리수 하나의 숫자들을 set에 저장.
• 그리고 각각의 저장된 숫자를 제외한 배열 값을 갖는 새로운 배열을 만들어서 재귀적으로 가능한 조합을 만들 수 있도록 하는 함수의 인자로 넣어줌.
• 그 함수가 makePrime인데, 함수이름만 makePrime이고, 사실상 조합을 만드는 함수임. 나의 실수.
• makePrime함수에서는 주어진 배열과, set, 이전에 이미 방문?했던 앞자리 수를 인자로 받음.
• 그리고 앞자리수가 하나 제외되어있는 주어진 배열에 있는 값을 하나씩 앞자리 수에 더하여 수를 만들고 set에 집어 넣음.
• 이때 앞자리 수에 10을 곱하고 배열에 있는 값 중 현재 가리키는 값을 더함으로써 새로운 수를 만들 수 있음.
• 그리고 makePrime함수를 재귀호출함으로써 위의 과정을 반복하다 보면, set에는 모든 가능한 숫자 조합이 만들어져 있음.
• 이 set을 가지고, 순회하면서, 만약 값이 0,1이라면 소수로 포함하지 않고, 2,3,5,7이라면 소수로 카운팅 함.
• 그리고 2의 배수라면 소수로 포함하지 않고, 2의 배수가 아니라면 해당 값을 3부터 (해당값/3)을 한 값까지로 나누었을 때 나머지가 0이면 => 1과 자기 자신 말고도 나눠지는 값이 있다는 것이므로 소수가 아니고, 카운팅 하지 않는다. 만약 그런 값이 하나도 없었다면(=>불리언 값으로 판단함) 소수로 카운팅한다.
• 위의 과정을 거침으로써 소수의 개수를 찾을 수 있다.
• 다소 복잡하게 보이지만, 스스로 짰다는 것에 의의를 둔다.
• 메소드를 익히는 것도 중요해 보인다.

전체 코드이다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] removeValue(int[] arr, int remove){
        int[] newarr = new int[arr.length-1];
        int first = 0;
        int index = 0;
        for(int i : arr){
            if(i==remove && first==0){
                first = 1;
            }else{
                newarr[index]=i;
                index++;
            }
        }
        
        return newarr;
    }
    
    public void makePrime(int[] arr, Set<Integer> set, int prev){
        for(int i=0; i<arr.length; i++){
            set.add(prev*10+arr[i]);
            int[] newarr = removeValue(arr, arr[i]);
            makePrime(newarr, set, prev*10+arr[i]);
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;//count
        
        int[] nums = new int[numbers.length()];
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<numbers.length(); i++){
            nums[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        for(int i=0; i<nums.length; i++){
            set.add(nums[i]);
            int[] newarr = removeValue(nums, nums[i]);
            makePrime(newarr, set, nums[i]);
        }
        
        //set에는 가능한 모든 값들이 생성된다.
        
        for(int i : set){
            if(i==0 || i==1){//0이거나 1이면 패스
                continue;
            }
            if(i==2 || i==3 || i==5 || i==7){//2,3,5,7이면 count
                answer++;
                continue;
            }
            if(i%2==0){//2의 배수이므로 패스
                continue;
            }else{
                int isPrime = 1;
                for(int j=3; j<=(i/3); j++){
                    if(i%j==0){
                        isPrime=0;
                        break;
                    }
                }
                if(isPrime==1) answer++;
            }
        }
        
        return answer;
    }
}

이 문제를 푸는데만 1시간 반이 걸렸지만, 성공한게 뿌듯했다. 

스택 알고리즘에서 자주 다루는 () 괄호 문제.

전공 책만 봐도 기본으로 나오는 예제인 것 같다.

그래서 막힘없이 술술 풀릴정도라, 왜 LV2인지는 모르겠으나.. 안 접해본 사람이라면 고민은 해볼 수 있을정도!

본론으로 들어가자면..

스택 (Stack)

• 후입선출(LIFO) 방식의 자료구조.
• 즉, 나중에 들어간 것이 가장 먼저 나오는 구조이다.

이 스택을 어떻게 괄호 문제에 활용할 수 있을까?

괄호가 열리면, 반드시 짝이되는 닫는 괄호가 있어야 한다.

괄호가 열릴 때마다 저장해 두었다가 닫는 괄호를 만나면 하나씩 삭제해 나가면 된다.

만약 열린 괄호의 내역이 없는데, 닫힌 괄호를 만난다면 ? 열린괄호가 없었으므로 닫힌 괄호는 올수없고 이는 규칙을 위반한 사례이므로 false를 반환한다.

그럼 열린 괄호를 어떻게 저장할 수 있을까?

바로 스택을 활용한다.

문자열 타입의 빈 스택을 생성해두고, 인자로 받은 (,)로만 이루어진 문자열 s의 첫번째 문자부터 순회한다.

문자가 열린괄호 ( 이면 스택에 넣어둔다. 그리고 ) 괄호이면, 짝을 하나 찾은 것이므로 스택에서 가장 마지막에 들어간 ( 을 빼주면 된다 = pop으로 가장 마지막 요소가 삭제된다.

그런데 여기서 주의할 점은, 스택이 만약 비어있었다면, 이전에 열린괄호 (가 없었다는 뜻이기 때문에, 규칙을 위반한 것이다. 따라서 이런 경우에는 바로 false를 리턴하도록 한다.

s 문자열을 다 순회하였는데, 스택이 비어있지 않다면?

스택이 비어있지 않다는 건, 이전에 들어왔던 열린 괄호 개수만큼  짝이 될 닫힌 괄호가 없었다는 뜻과 같기 때문에, 이 경우에도 false를 리턴해야 한다.

따라서 결과가 true가 되려면, string 순회 후에 스택이 비어있어야 함을 알 수 있다.

위를 바탕으로 코드를 짜면 아래와 같다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Stack<String> st = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                st.push("(");
            }else{
                if(st.isEmpty()){
                    return false;
                }else{
                    st.pop();
                }
            }
        }
     
        if(!st.isEmpty()) answer = false;
        
        return answer;
    }
}

<자바 문법>

** Stack을 사용하려면 java.util.Stack을 import 해야함.

** 문자열의 특정 위치의 문자에 접근하려면, s.charAt(인덱스) 를 사용하여 접근해야함.

** 문자의 경우 ' ', 문자열의 경우 " " 임을 명심하자.