이 영역을 누르면 첫 페이지로 이동
Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

페이지 맨 위로 올라가기

Stranger's LAB

프로그래밍과 관련하여 다양한 알고리즘 문제를 풀어보고, 프로그래밍 언어를 이해해 볼 수 있도록 돕고자 만든 블로그 입니다.

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

  • 2020.10.15 14:49
  • JAVA - 백준 [BAEK JOON]/정수론 및 조합론
글 작성자: ST_
728x90





 
www.acmicpc.net/problem/1037

 

1037번: 약수

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

www.acmicpc.net

 









  • 문제



 

 

 

 

 

 

 

 

 

 

 

 

 





  • 알고리즘 [접근 방법]

 



 

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

 

"어떤 수 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 가 빠른 걸 볼 수 있다.








  • 정리

 



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

 

 



 

저작자표시 비영리 변경금지 (새창열림)

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

[백준] 11050번 : 이항 계수 1 - JAVA [자바]  (18) 2020.10.27
[백준] 3036번 : 링 - JAVA [자바]  (0) 2020.10.23
[백준] 2981번 : 검문 - JAVA [자바]  (10) 2020.10.22
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]  (14) 2020.10.20
[백준] 5086번 : 배수와 약수 - JAVA [자바]  (0) 2020.10.14

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 3036번 : 링 - JAVA [자바]

    [백준] 3036번 : 링 - JAVA [자바]

    2020.10.23
  • [백준] 2981번 : 검문 - JAVA [자바]

    [백준] 2981번 : 검문 - JAVA [자바]

    2020.10.22
  • [백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

    [백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

    2020.10.20
  • [백준] 5086번 : 배수와 약수 - JAVA [자바]

    [백준] 5086번 : 배수와 약수 - JAVA [자바]

    2020.10.14
다른 글 더 둘러보기

정보

Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

  • Stranger's LAB의 첫 페이지로 이동

검색

나의 외부 링크

  • st-github

공지사항

  • 공지 - 블로그 사용 설명서

메뉴

  • 홈
  • 방명록

카테고리

  • 전체 카테고리 (267)
    • Java (5)
    • JAVA - 백준 [BAEK JOON] (177)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (10)
      • 기본 수학 1 (8)
      • 기본 수학 2 (6)
      • 2차원 배열 (0)
      • 정렬 (10)
      • 재귀 (4)
      • 브루트 포스 (5)
      • 집합과 맵 (0)
      • 기하 1 (5)
      • 정수론 및 조합론 (12)
      • 백트래킹 (8)
      • 동적 계획법 1 (15)
      • 누적 합 (0)
      • 그리디 알고리즘 (5)
      • 스택 (5)
      • 큐, 덱 (7)
      • 분할 정복 (9)
      • 이분 탐색 (7)
      • 기타 문제 (17)
      • 별 찍기 문제 모음 (2)
    • C++ - 백준 [BAEK JOON] (46)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (0)
      • 기타 문제 (4)
    • 자료구조 (18)
      • Java (18)
    • 알고리즘 (11)
      • Java (11)
    • 프로그래밍 기초 (6)
    • 이모저모 (2)
    • 일상의 글 (2)

최근 글

정보

ST_의 Stranger's LAB

Stranger's LAB

ST_

블로그 구독하기

  • 구독하기
  • 네이버 이웃 맺기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © ST_.

티스토리툴바