스파르타 코딩 클럽 내일배움캠프 6주차 1일

★★★★★★★★★★★ 이진탐색은 정렬되지않은 임의의 숫자에서 절대 찾을수 없음... 중요!!!

해결법 : 정렬해도 된다면 정렬함... 하지만 정렬해서 원본값이 회손된다면 그냥 O(N)에 탐색으로 값을 찾자..!!

 

1. 팩토리얼

5 4 3 2 1 이런식으로 쭉쭉 곱해줘야하니 스택에 쌓아놨다가 한번에 연산을 해줘야 하기 때문에

n * factorial(n-1);

이런 연산을 해줘야 합니다. 풀이를 해주면 n * n-1 * factorial(n-2) ......

public class Main {
    static int result =0;
    public static int factorial(int n)
    {
        if(n<=1)
        {
            return 1;
        }
        else
        {
            result = n * factorial(n-1);
        }
        return result;
    }
    public static void main(String[] args)
    {
        System.out.println(factorial(5));
    }
}

끝나는 조건 : n이 1이될때

 

2. 이즈 팰린드롬(회문검사) - 재귀사용

public class Main {
    static int result =0;
    public static boolean is_palindrome(String name)
    {
        if(name.length()==1)
        {
            return true;
        }
        if(name.charAt(0) != name.charAt(name.length()-1))
        {
            return false;
        }
        name = name.substring(1,name.length()-1);
        is_palindrome(name);
        return true;
    }
    public static void main(String[] args)
    {
//        String input = "소주만병만주소";
        String input = "tomato";
        System.out.println(is_palindrome(input));
    }
}

알고리즘 : 첫글자 끝글자를 점점 비교하면서 없애면서 확인한다.

끝나는 조건 : 첫글자와 끝글자가 다르거나, 입력받은 글자의 길이가 1일때 종료한다.

 

n의 배수 찾기

import static java.util.Arrays.sort;
import java.util.ArrayList;
import java.util.List;
    class Solution
    {
        public static int[] solution(int n, int[] numlist)
        {
            int[] answer = {};
            int cnt=0;
            List<Integer> calcul = new ArrayList<Integer>();
            for(int i=0;i<numlist.length;i++)
            {
                if(numlist[i]%n==0)
                {
                    calcul.add(numlist[i]);
                    cnt++;
                }
            }
            answer = calcul.stream().mapToInt(Integer::intValue).toArray();
            return answer;
        }
    }

생각 흐름 : 처음에는 while과 for문을 돌려서 무식하게 n^2만큼의 시간복잡도가 나오게 막짰는데 시간 초과가 나서... 나중에 다른방법을 생각해보니 %연산자가 생각나서 적용시켰더니 통과 했다.