패스트캠퍼스 챌린지 43일차

카테고리 없음

패스트캠퍼스 챌린지 43일차

JUN0126 2022. 3. 7. 23:37

실전 알고리즘 문제풀이 - 패캠 제작 문제 해설 1

전구 문제

- 단순히 문제 요구사항 구현 문제

- 조건상 데이터의 개수 N과 명령어의 개수 M이 모두 4000 이하 입니다

- 따라서 시간 복잡도 O(NM)의 알고리즘으로 문제 해결 가능

- 구현이 복잡해 지지 않도록 별도 메서드로 분리하여 작성

구현 코드

import java.util.*;

public class Main{

	// 전구 개수 N, 명령어 개수 M
	public static int N,M;
    
    public static int[] arr = new int[4001];
    
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      
      N = sc.nextInt();
      M = sc.nextInt();
      
      for(int i = 1; i <=N; i++){
        arr[i] = sc.nextInt(); 
      }
      
      // 각 명령어를 입력 받으며 처리
      for (int i = 0; i < M; i++){
        int a,b,c;
        a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        oper(a,b,c)
      }
    }
    
    public static void oper(int a, int b, int c){
      if(a ==1){ // 상태 변경
        arr[b] = c;
      }else if(a == 2){ // 스위치
        for(int i = b; i < c; i++){
          if(arr[i] == 0) arr[i] = 1;
          else arr[i] = 0;
        }
      }else if(a==3){ // 전구 끄기
        for(int i =b; i <=c; i++){
          arr[i] = 0;
        }
      }else if(a==4){ // 전구 키기
        for(int i =b; i<=c; i++){
          arr[i] = 1;
        }
      }
    }

}

소수 최소 공배수 문제 풀이

- 약수의 성질 파악 => 모든 약수가 가운데 약수를 기준으로 곱셈에 대하여 대칭

문제 : 길이가 N인 수열 A에서 소수들을 골라 최소공배수를 구하시오

첫째 줄에 소수들의 최소공배수를 출력하고 소수가 없다면 -1 출력

구현

import java.util.*;

public class Main{

	// 수열의 길이(N)
	public static int N;
    
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      
      N = sc.nextInt();
      long ans = 1;
      
      for(int i = 1; i <=N; i++){
        long a;
        a = sc.nextInt();
        if(isPrimeNumber(a)){
          ans = lcm(ans,a);
        } 
      }
      
      if(ans == 1) System.out.println(-1);
      else System.out.println(ans);
    }
    
    // 소수 판별 함수 (2이상 자연수에 대하여)
    public static boolean isPrimeNumber(long x){
      // 2부터 x의 제곱근까지의 모든 수를 확인하며
      for(long i = 2; i < Math.sqrt(x); i++){
        // x가 해당 수로 나누어 떨어진다면
        if(x%1==0) return false; //소수가 아님
      }
      return true; // 소수
    }
    
    // 최대 공약수 GCD
    public static long gcd(long x, long y){
      while(y!=0){
        long temp = x % y;
        x = y;
        y = temp;
      }
      return x;
    }
    
    // 최소 공약수 lcm
    public static long lcm(long x, long y){
      return x / gcd(x,y) * y;
    }

}