[백준] 1037 약수 (JAVA)

suRan·2022년 8월 9일
백준
0

🤖 백준

목록 보기
1/3

📜 문제

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 
어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 
둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 
2보다 크거나 같은 자연수이고, 중복되지 않는다.
출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다..

문제 분석

  • 핵심 포인트
    • A가 1과 N이 아니어야 한다. 👉 진짜 약수의 조건
    • 진짜 약수가 모두 주어진다. 👉 1과 N 자기 자신이 아닌 약수(진짜 약수)가 모두 주어진다.

  • 입력값
    • N은 항상 32비트 부호있는 정수로 표현할 수 있다.
    • java 정수 형식의 특성
    • 타입범위bitbyte
      byte-128 ~ 127
      		81
      short–32,768 ~ 32,767162
      int–2,147,483,648 ~ 2,147,483,647324
      long-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807648



🎯 풀이

알고리즘 알고 풀기

  • 알아야하는 것은 수학의 약수이다.

    나는 수학 개념을 전부 잊어버려서 초등 수학 블로그를 보면서 다시 개념을 숙지했다. 😂
    약수 개념을 알고있는 사람이라면 문제없이 풀 수 있는 문제 같다.

    N을 구하기 위해서는 약수의 성질을 이용하면 된다.

  • EX)
    예를 들어 N이 20이라면
    약수는 1, 2, 4, 5, 10, 20이 된다.
    그 중 1과 자기 자신을 제외한 진짜 약수는
    2, 4, 5, 10이다.

  • 즉, 진짜 약수의 최댓값과 최솟값을 곱하면 N을 구할 수 있다.



  • 코드1 (배열 이용)
import java.util.Scanner;


public class jun_1037 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int divCount = sc.nextInt();
        int[] divArray = new int[divCount];

        for (int i = 0; i < divCount; i++) {
            divArray[i] = sc.nextInt();
        }

        Arrays.sort(divArray); // 정렬

        int divMin = divArray[0];
        int divMax = divArray[divCount - 1];

        System.out.println(divMin * divMax);
    }
}
  • 코드2 (배열 이용x)
import java.util.Scanner;

public class jun_1037 {
        public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
            int divCount = sc.nextInt();
            int divMax = Integer.MIN_VALUE;
            int divMin = Integer.MAX_VALUE;

            while (divCount-- > 0) {
                int tmp =  sc.nextInt();

                divMax = tmp > divMax? tmp : divMax;
                divMin = tmp < divMin ? tmp : divMin;
            }

            System.out.println(divMax * divMin);
    }
}

// 이건 다른 사람 풀이를 보고 솔직히 신기해서 따라 풀어봤다.
// 나는 배열을 사용하는 방법만 생각했는데 이런 발상이 가능하다니..
  • 코드3 (BufferedReader 이용)
public class jun_1037_bufferdReader {
    public static void main(String[] args) throws IOException { // 입출력 예외 처리
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); // 콘솔에서 입력값을 입력받을 BufferedReader 객체 생성
        int divCount = Integer.parseInt(bf.readLine()); // BufferedReader.readLine()은 한 줄의 문자열을 읽어오고 String을 리턴한다.
        int[] divArray = new int[divCount];

        // 입력 문자열을 공백으로 구분하기 위한 StringTokenizer 추가
        StringTokenizer st = new StringTokenizer(bf.readLine(), " "); //readLine()으로 읽어들인 문자열을 공백 구분자를 기준으로 분리

        for (int i = 0; i < divCount; i++) {
            divArray[i] = Integer.parseInt(st.nextToken()); // StringTokenizer.nextToken() 다음 토큰을 String으로 반환
        }

        Arrays.sort(divArray); // 정렬

        int divMin = divArray[0];
        int divMax = divArray[divCount - 1];

        System.out.println(divMin * divMax);
    }
}
  • 코드4 (BufferedReader 이용)
public class jun_1037_bufferdeReader2 {
        public static void main(String[] args) throws IOException {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int divCount = Integer.parseInt(bf.readLine());

            int divMax = Integer.MIN_VALUE;
            int divMin = Integer.MAX_VALUE;

            StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
            while (divCount-- > 0) {
                int tmp = Integer.parseInt(st.nextToken()); // divCount번만큼 반복

                divMax = tmp > divMax ? tmp : divMax;
                divMin = tmp < divMin ? tmp : divMin;
            }

            System.out.println(divMax * divMin);
    }
}
  • BufferedReader 클래스
    • BufferedReader는 버퍼를 이용해서 한 번에 데이터를 입력하기 때문에 메모리 관리가 용이하다.
    • 코드 길이가 가장 길지만 실행 시간이 가장 빠르다.
    • 습관적으로 BufferedReader를 사용하도록 노력하자.
    • 메모리 비교
  • Scanner와 BufferedReader
    • Scanner는 1024 char 만큼의 버퍼를 가지지만, BufferedReader는 그 8배의 버퍼를 가진다.
    • 많은 양의 입출력 수행 시 BufferedReader클래스 활용 -> 더 빠른 처리 가능
  • InputStreamReader 클래스
    • 입력값이 주어지면 String형태로 읽는 클래스
  • Integer.parseInt
    • String타입의 숫자를 int타입으로 변환해준다.
  • StringTokenizer 클래스
    • BufferedReader는 입력을 읽을 때 라인단위로 읽어들인다.
    • String + Tokenizer == 문자열을 토큰화한다!



시간복잡도

코드3과 코드4

  • for문

    • 반복문은 시간복잡도에 영향을 가장 미치는 요소 중 하나
    • 이 문제에서는 단순한 for문이 사용됐다. -> 교환연산만 divCount회 반복
    • 따라서 시간복잡도는 1*n
    • 코드4도 마찬가지로 while문 하나만 존재 -> 1*n

  • Arrays.sort()

    • 내부적으로 DualPivotQuicksort 정렬을 사용한다.

    • Quicksort 정렬 알고리즘은 평균적으로 가장 빠른 정렬 알고리즘

    • Primitive 타입 배열을 입력했을 때 평균 시간복잡도는 O(nlogn), 최악의 경우는 O(n^2)

    • Java에서 사용하고 있는 dual-pivot quicksort는 O(N^2)의 시간 복잡도로 동작할 일은 사실상 없을 수준으로 개선했기 때문에 실무에서 사용하는 데에 문제가 없지만, 그럼에도 불구하고 시간복잡도를 O(N^2)으로 만드는 데이터를 생성하는 것이 가능은 함

    • 그러므로 정렬 알고리즘 문제와 같이 시간 복잡도 O(NlogN)을 보장하는 정렬 코드를 작성해야 한다면 기본형(Primitive) 타입의 배열을 Arrays.sort()로 정렬하는 것은 무리무리

    • 시간 복잡도 면에서는 정렬 시 Arrays.sort()보다 collections.sort가 더 유리한 면이 많다. 이 문제에서는 괜찮았지만 정렬할 값이 많아지면 collections.sort를 쓰자.

    코드3의 시간복잡도는 1*n + n^2 = O(N^2)
    코드4의 시간복잡도는 1*n = O(n)



공간복잡도

내가 보려고 정리하는 개념

  • 약수: 어떤 수를 나누어 떨어지게 하는 수
  • Integer.MIN_VALUE : integer의 최솟값을 제공하는 상수
  • Integer.MAX_VALUE : integer의 최댓값을 제공하는 상수
  • Arrays.sort()는 static메서드이므로 인스턴스를 생성하지 않고 바로 사용할 수 있다.
    출처: https://codingnojam.tistory.com/38

더 알아보고 싶은 것

Rf

profile
suRan
개발 공부를 해라
다음 포스트

[백준] 9012 괄호 (JAVA)

0개의 댓글