스파르타 코딩클럽 2주차 5일

최대값, 최빈값, 소수, 중복되지 않는값, 모든숫자를 같게 만드는 최소의 갯수의 알고리즘을 자바로 풀어보았다.

 

특히 소수의 알고리즘은 에라토스테네스의 체를 이용하면 구현이 쉽고 시간 복잡도 상에서 유리하다고 한다. 꼭한번 풀어봐야겠다. 

 

import java.util.ArrayList;
import java.util.List;

public class main
{
    static int[] input = new int[] {3,5,6,1,2,4};
    static String name ="hello my name is sparta";

    static void find_max_char(String name)
    {
        int[] val =new int[26];

        for(int i=0; i<name.length(); i++)
        {
            if(name.charAt(i) == ' ') continue;
            int idx = (int)(name.charAt(i) - 'a');
            val[idx]++;
        }
        int max =0;
        for(int i=0; i<name.length(); i++)
        {
            if(val[i]>max)
            {
                max = val[i];
            }
        }
        System.out.println((char)(val[max]+'a'));
    }

    static void find_max_num(int a[])
    {
        int max = input[0];
        for(int i=1;i< input.length;i++)
        {
            if(max < input[i])
            {
                max = input[i];
            }
        }
        System.out.println(max);
    }

    static String input_char = "abadabac";
    static void find_not_repeating_one_character()
    {
        int[] result = new int[26];

        for(int i=0;i<input_char.length();i++)
        {
            int idx = (int)(input_char.charAt(i)-'a');
//            System.out.println(idx);
            result[idx]++;
        }

        for(int i=0;i<input_char.length();i++)
        {
            if(result[i] == 1)
            {
                System.out.println((char)(i+'a'));
                break;
            }
        }
    }

    static String input_val = "01010";

    static void find_count_to_turn_out_to_all_zero_or_all_one(String val)
    {
        int min =999999;
        int check_cnt=0;
        // zero to one check
        int cnt_zero=0;
        int cnt_one=0;
        if(val.charAt(0) =='0')
        {
            cnt_one++;
        }
        else
        {
            cnt_zero++;
        }
        for(int i=0;i<val.length()-1;i++)
        {
            if(val.charAt(i) != val.charAt(i+1))
            {
                if(val.charAt(i+1)=='0')
                {
                    cnt_one++;
                }
                else
                {
                    cnt_zero++;
                }
            }
        }

        // min check one and zero
        min = cnt_zero;
        if(cnt_zero>cnt_one)
            min = cnt_one;
        System.out.println(min);
    }

    static List<Integer> prime_solution(int n)
    {
//        소수들로만 나누어본다. 나누어 떨어지면 소수가 아니다.
//
//        9는 3의 배수이다. 3은 소수이다.
//        10은 2, 5의 배수이다. 2,5는 소수이다.
//        14는 2, 7의 배수이다. 2, 7은 소수이다
//        => 입력받은 수보다 작은 수의 소수들로 나누어 떨어지면 소수가 아니다 (소수의 배수는 소수가 아니다)
//
//        이를 위해 먼저 list에 가장 작은 소수(2)를 넣어두고, 반복문을 돌리며 소수로 나누어 떨어지는지 여부를 확인한다.

        int answer =0;
        List<Integer> list = new ArrayList<Integer>();
        list.add(2);

        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<list.size();j++)
            {
                if(i%list.get(j)==0) break; // 나누어 떨어지면 소수가 아니다.
                if(list.size()==j+1) list.add(i); // 나누어 떨어지지 아니면 list의 추가
            }
        }
        return list;
    }


    static void find_prime_list_under_number()
    {
        int input = 20;
        List<Integer> result = prime_solution(input);
        for(int i=0;i<result.size();i++)
        {
            System.out.println(result.get(i));
        }
    }


    public static void main(String[] args)
    {
//        find_max_num(input);
//        find_max_char(name);
//        find_not_repeating_one_character();
//        find_count_to_turn_out_to_all_zero_or_all_one(input_val);
        find_prime_list_under_number();

    }
}