[백준] 1037번 : 약수 - JAVA [자바]

 
www.acmicpc.net/problem/1037

1037번: 약수

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

이 문제는 그리 어렵지 않은 문제지만, 한가지 주의해야 할 점이 있다. "최소공배수로 구하면 틀린다." 이유는 문제에서 보면 이렇게 쓰여 있다.

 

"어떤 수 N의 진짜 약수가 모두 주어질 때"

 

이 부분 때문에 단순히 최소공배수로 구하면 오답이 된다.

 

예로 들어보자.

N = 30 이라고 가정하면 입력은 다음과 같이 들어올 것이다.

 

2, 3, 5, 6, 10, 15

 

그 외의 입력은 들어올 수가 없다.

 

예로들어 2, 3, 5라는 입력 자체가 들어올 수가 없다는 의미다. N에대한 약수가 모두 주어져야 하므로 최소공배수로 구하거나 모든 원소를 곱해버리면 틀릴 수 밖에 없다.

 

이를 생각하고 풀이한다면 문제 해결은 매우 쉽다. 그냥 입력으로 들어오는 값 중 최솟값과 최댓값을 서로 곱하면 끝이다.

 

while (T-- > 0) {
	int number = input()

	if(number > max) max = number
	if(number < min) min = number
}

print(max * min)

 

대강 이런식으로 짜면 끝난다.

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

서로 다른 입력방법(Scanner와 BufferedReader)을 사용하여 입력에 따른 성능차이를 볼 것이다.

 

1 . Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int T = in.nextInt();
		
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		
		while(T-- > 0) {
			int N = in.nextInt();
			max = N > max ? N : max;
			min = N < min ? N : min;
            
			/*
			 same this
			 if(N > max) max = N;
			 if(N < min) min = N;
			*/
		}
		System.out.println(max * min);
	}

}

 

 

워낙 쉬운 문제라.. 별달리 설명할 것이 없다.

 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
		while(T-- > 0) {
			int N = Integer.parseInt(st.nextToken());
			max = N > max ? N : max;
			min = N < min ? N : min;
		}
		System.out.println(max * min);
	}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

채점 번호 : 23256567  -  방법 2 : BufferedReader

채점 번호 : 23256561  -  방법 1 : Scanner 

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

언제나 그렇지만 항상 문제를 잘 봐야한다. 난이도상으로는 매우 쉬운 문제인데 제대로 해석하지 못하면 잘못된 접근을 할 수 있다. 아마도 그래서 정답비율이 절반에 못미치지 않았나 싶다.