알고리즘(소수 만들기, 점프와 순간이동, 영어 끝말잇기)

[소수 만들기]

 

* 로직

• 주어진 숫자 중 3개의 수를 더했을 때 만들 수 있는 경우의 수를 만든다(조합)
• 조합이 만들어질 때마다 해당 숫자가 소수인지 판별한다
• 소수라면 답을 카운팅해준다

 

//소수 만들기
public class Problem_Decimal {
    static int result;

    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        int answer = solution(nums);

        System.out.println(answer);
    }

    public static int solution(int[] nums) {
        int answer = -1;

        //조합 구하기
        int count = 0;
        int index=0;
        int limit = 3;
        int acc=0;
        result = 0;

        doProcess(index, nums, acc, count, limit);

        return answer = result;
    }

    private static void doProcess(int index, int[] nums, int acc, int count, int limit) {
        if(count >= limit) {
            //소수 판별
            if(deterDecimal(acc)){
                result++;
            }
            return;
        }

        for(int i=index; i<nums.length; ++i){
            doProcess(i+1, nums, acc + nums[i], count+1, limit);
        }
    }

    private static boolean deterDecimal(int num) {
        for(int i=2; i<=Math.sqrt(num); ++i){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
}

 

[점프와 순간이동]

 

* 로직

• 거꾸로 생각해봤을 때,
  • n이 2로 나누어 떨어진다면 => 순간 이동이 가능하다
  • 나누어 떨어지지 않는다면 => 한칸 이동을 해야한다, 사용량++
• 우선 순간이동부터 가능한지 먼저 보고, 더이상 안된다면 한칸 이동하는 방식은 그리디라고 볼 수 있다

 

//점프와 순간이동
public class Problem_JumpTeleportation {

    public static void main(String[] args) {
        int n = 5;
        int answer = solution(n);
        System.out.println(answer);
    }

    public static int solution(int n) {
        int ans = 0;
        while (n > 0){

            //나누어 떨어진다면 순간이동 가능
            if(n % 2 == 0)
                n /= 2;

            //그렇지 않다면 한칸 점프
            else {
                n -= 1;
                ans++;
            }
        }

        return ans;
    }
}

 

 

[영어 끝말잇기]

 

* 로직

• 단어의 중복 여부를 체크하기 위해 Hashmap을 사용하였다
• 한 사이클씩 돌면서
  • 만약 현재 단어가 이미 사용되었다면 => 현재 단어를 사용한 사람 idx와 사이클을 담고 탐색을 종료한다
  • 만약 이전 단어의 끝 글자와 현재 단어의 앞 글자가 다르다면 => 현재 단어를 사용한 사람 idx와 사이클을 담고 탐색을 종료한다
  • 위 2가지 조건을 만족하지 않는다면 => map에 단어를 key값으로 추가한다
• 만약 정상적으로 모든 탐색이 끝났다면 [0,0] 리턴
• 그렇지 않다면 [idx, 사이클] 을 리턴한다

 

//영어 끝말잇기
import java.util.HashMap;

public class Problem_EndingEnglish {

    public static void main(String[] args) {
        int n = 5;
        String[] words = {
                "hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish",
                "hang", "gather", "refer", "reference", "estimate", "executive"
        };

        int[] answers = solution(n, words);
        for(int ans : answers){
            System.out.print(ans + " ");
        }
    }

    public static int[] solution(int n, String[] words) {
        int[] answer = {};

        int cycle = 1;
        int findIdx = 0;
        boolean check = false;

        //중복여부 체크
        HashMap<String, Integer> hashMap = new HashMap<>();
        hashMap.put(words[0], 1);

        for(int i=1; i<words.length; ++i){
            if(i % n == 0) {
                cycle++;
            }

            String word_end = words[i-1].substring(words[i-1].length()-1);
            String word_start = words[i].substring(0, 1);

            //만약 이전에 쓰였던 단어라면
            if(hashMap.containsKey(words[i])) {
                check = true;
                findIdx = i % n;
                break;
            }

            //앞단어의 끝 글자와 현재 글자의 앞 글자가 다르다면
            if(!word_end.equals(word_start)){
                check = true;
                findIdx = i % n;
                break;
            }

            //사용된 단어로 추가
            hashMap.put(words[i], 1);

        }

        answer = new int[2];
        if(!check) {
            answer[0] = 0;
            answer[1] = 0;
        }

        else {
            answer[0] = findIdx + 1;
            answer[1] = cycle;
        }
        return answer;
    }
}