[구름] 완전제곱수 (2레벨 , 3레벨)

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://level.goorm.io/exam/43152/%EC%99%84%EC%A0%84-%EC%A0%9C%EA%B3%B1%EC%88%98/quiz/1

구름LEVEL

https://level.goorm.io/exam/43116/%EC%99%84%EC%A0%84-%EC%A0%9C%EA%B3%B1%EC%88%98/quiz/1

구름LEVEL

---

Think🤔

1.

완전 제곱수란 이름을 가진 문제가 두 개였다.

하나는 2레벨 이였고, 다른 하나는 3레벨 이였다.

 

일단 위에 2레벨 문제는... Math.pow를 사용하면 제곱을 구할 수 있다. 또는 Math.sqrt를 이용하면 제곱수를 구할 수 있다.

그리고 입력 받은 값들의 제곱근이 있으면 완전 제곱수여서 count++ 하게 만들어 준다.

import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int input = Integer.parseInt(br.readLine());
		int[] arr = new int[input];
		
		int count = 0;
		for(int i=0; i<input; i++){
			arr[i] = Integer.parseInt(br.readLine());
			for(int j=1; j<arr[i]; j++){
				if(arr[i]/j == j && arr[i] % j == 0){
					System.out.println(arr[i]);
					count++;
				}
			}
		}
		
		System.out.print(count);
	}
}

코드 이론상 맞는데 현재 분서 결과 잘못된 부분을 예상해보자면,

if 문에서 arr[i]값이 1일때를 인식하지 못하는 것 같다.

2.

비슷한 방법인데 최솟값, 그리고 누적합을 구하는 부분이 있음

---

Solution✍

1.

import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int input = Integer.parseInt(br.readLine());
		int[] arr = new int[input];
		
		int count = 0;
		for(int i=0; i<input; i++){
			arr[i] = Integer.parseInt(br.readLine());
			int sqrt = (int)(Math.sqrt(arr[i]));
			if(sqrt * sqrt == arr[i]){
				count++;
			}
		}
		
		System.out.print(count);
	}
}

import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int input = Integer.parseInt(br.readLine());
		int[] arr = new int[input];
		
		int count = 0;
		for(int i=0; i<input; i++){
			arr[i] = Integer.parseInt(br.readLine());
			for(int j=1; j<=arr[i]; j++){
				if(arr[i]/j == j && arr[i] % j == 0){
					count++;
				}
			}
		}
		
		System.out.print(count);
	}
}

if문을 잘 보자면 arr[i]/j를 나눴을 때 j 값이랑 같고 그리고 7로 나눴을때 나누어 떨어지면 그 값은 제곱근이다.

2.

import java.io.*;
class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		
		int begin = Integer.parseInt(input[0]);
		int end = Integer.parseInt(input[1]);
		
		int hab = 0;
		int min = end;
		
		// 처음 값이 최솟값 그리고 end 값이 최대값
		for(int i=begin; i<=end; i++){
			int sqrt = (int)Math.sqrt(i);
			if(sqrt * sqrt == i){
				hab += i;
				min = Math.min(i, min);
			}
		}
		
		System.out.print(min + " " + hab);
	}
}

---

Review🤩

min을 처음에 0으로 해놔서 0이 계속해서 나왔고, sqrt도 i값으로 해뒀어야 했는데 begin으로 해둬서 답이 안나왔다.

sqrt * sqrt인 부분을 Math를 사용하지 않고도 풀어본다.

import java.io.*;
class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		
		int begin = Integer.parseInt(input[0]);
		int end = Integer.parseInt(input[1]);
		
		int hab = 0;
		int min = end;
		
		// 처음 값이 최솟값 그리고 end 값이 최대값
		for(int i=begin; i<=end; i++){
			for(int j=1; j<=i; j++){
				if(i % j == 0 && i / j == j){
					min = Math.min(i,min);
					hab += i;
				}
			}
		}
		
		System.out.print(min + " " + hab);
	}
}

구현을 해봤다.

근데 그럼 2중 for문이 돼서 bigO 표기법에 의해서 성능이 느려져서 Math.min을 사용하는게 더 나은거 같기도 하다.

---