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

 
www.acmicpc.net/problem/3036

3036번: 링

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

음.. 달리 설명 할 필요가 없는 문제다.

 

위 예제를 보면 첫 번째 링의 반지름이 12이고, 이 링이 한 바퀴 돌 때 나머지 링이 몇 바퀴가 도는지를 '기약 분수'로 출력하는 문제다.

 

 

어? 그러면 둘레를 구해야 하나? 라고 생각해서 둘레로 구하는 경우도 봤는데, 모든 도형이 모두 원이기 때문에 둘레를 구할 필요가 없다. 왜 그런지 감이 안온다면 위 예제를 갖고 한 번 적용해보자.

 

첫 번째 링의 둘레 : R₁ = 2πr₁ 

두 번째 링의 둘레 : R₂ = 2πr₂

세 번째 링의 둘레 : R₃ = 2πr₃

네 번째 링의 둘레 : R₄ = 2πr₄

 

 

여기서 첫 번째 링을 기준으로 몇 바퀴가 굴러갔는지 확인하려면 R1에서 다른 링을 나눠보면 되지 않겠는가?

 

R₁ / R₂ → 2πr₁ / 2πr₂

→ 2πr₁ / 2πr₂ = r₁ / r₂

 

이러면 결국에 2π는 모두 공통적으로 갖고 있기 때문에 지워진다, 즉, 위 문제 풀이 과정에서 굳이 둘레를 구할 필요가 없고, 반지름만 갖고서도 풀 수 있다는 것이다.

 

그럼 이제 마지막으로 해결 할 문제는 '기약 분수'로 나타내기다.

 

이건 모두가 알듯이 기약분수로 나타내고 싶다면 분모와 분자의 최대공약수로 나눠주면 끝나는 문제다. 바로 알고리즘으로 보자.

 

// 첫 번째 링
int firstRing = input();
 
for (int i = 1; i < N; i++) {
 
	int otherRing = input()
 
	// 기약분수로 만들기 위한 최대공약수 찾기
	int gcd = gcd(firstRing, otherRing);
 
	// 분모와 분자를 최대공약수로 나눠주기 
	print((first / gcd) + "/" + (otherRing / gcd));
}
 
// 최대공약수 메소드
int gcd(int a, int b) {
	int r;
 
	while (b != 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

 

 

매우 쉽죠??

 

 

 

 

 

 

 

 

 

 

---

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

 

이 번 풀이에서는 Scanner와 BufferedReader을 사용해 각기 다른 입력에 따른 성능의 차이를 비교해볼 것이다. 또한 BufferedReader에서는 각각 출력하는 방법과, 하나의 문자열로 묶어서 한 번에 출력하는 방법을 사용하여 출력에 따른 차이도 확인해보고자 한다.

 

알고리즘은 위에서 설명한 것을 토대로 사용할 것이다.

 

1 . Scanner

2. BufferedReader 

3. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		// 첫 번째 링
		int firstRing = in.nextInt();
 
		for (int i = 1; i < N; i++) {
			
			int otherRing = in.nextInt();
			
			// 기약분수로 만들기 위한 최대공약수 찾기
			int gcd = gcd(firstRing, otherRing);
 
			// 분모와 분자를 최대공약수로 나눠주기 
			System.out.println((firstRing / gcd) + "/" + (otherRing / gcd));
		}
	}
 
	// 최대공약수 메소드
	static int gcd(int a, int b) {
		int r;
 
		while (b != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
 
}

 

 

가장 기본적인 방법이다.

 

 

 

---

- 방법 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 N = Integer.parseInt(br.readLine());
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		// 첫 번째 링
		int firstRing = Integer.parseInt(st.nextToken());
 
		for (int i = 1; i < N; i++) {
			
			int otherRing = Integer.parseInt(st.nextToken());
			
			// 기약분수로 만들기 위한 최대공약수 찾기
			int gcd = gcd(firstRing, otherRing);
 
			// 분모와 분자를 최대공약수로 나눠주기 
			System.out.println((firstRing / gcd) + "/" + (otherRing / gcd));
		}
 
	}
 
	// 최대공약수 메소드
	static int gcd(int a, int b) {
		int r;
 
		while (b != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
 
}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

 

---

- 방법 3 : [BufferedReader + StringBuilder]

 

 

 

 

출력 방법을 매 번 출력하는 것이 아닌 StringBuilder로 묶어서 한 번에 출력하는 방법이다.

 

 

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));
		StringBuilder sb = new StringBuilder();
 
		int N = Integer.parseInt(br.readLine());
 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
		// 첫 번째 링
		int firstRing = Integer.parseInt(st.nextToken());
 
		for (int i = 1; i < N; i++) {
			
			int otherRing = Integer.parseInt(st.nextToken());
			
			// 기약분수로 만들기 위한 최대공약수 찾기
			int gcd = gcd(firstRing, otherRing);
 
			// 분모와 분자를 최대공약수로 나눠주기 
			sb.append(firstRing / gcd).append('/').append(otherRing / gcd).append('\n');
		}
		
		System.out.println(sb);
 
	}
 
	// 최대공약수 메소드
	static int gcd(int a, int b) {
		int r;
 
		while (b != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
 
}

 

 

 

워낙 쉽게 풀 수 있는 문제라 어렵지 않았으리라 본다.

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 23427571  -  방법 3 : BufferedReader + StringBuilder

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

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

 

 

출력에서는 그렇게 큰 차이가 없는듯하다.. 입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

직전 문제는 정답률이 워낙 낮았는데 그래서 그런지 매우 쉬운 문제였다. 아마 질문이 없을 것이라 예상하지만... 혹시나 잘 모르겠거나 어려운 부분이 있다면 댓글 남겨주시는대로 빠르게 답변드리도록 하겠다.