CodingTest # 18 Java 1193 (분수 찾기) 문제 풀이
목요일부터 시작해 오늘까지 풀 공부를 달리는 중이다..
뿌듯한 마음도 들지만, 아직까지도 내가 부족하다 느낀다.
오늘은 어제 마지막까지 풀었지만, 수학 능력이 부족하다고 판단하여..
계차수열을 좀 더 공부하고, 풀어본 1193 분수 찾기 문제이다.
오랜 시간이 걸려서 마침내 결과를 정답으로 바꾸었다.
아쉬운 점은 메모리를 많이 먹었다는 점..
아무래도 코드를 간결하게 짜지 못했을뿐더러..
대책없는 천만 단위까지 for문 돌리기,
List에 사용으로 인한 것 같다.
그래도 서툰 정답과 구글을 통해 다른 사람의 정답과 비교해보았다..
무려 100ms 시간 차이가 났다..
보고 배울게 많은 것 같다.
우선 나의 코드이다.
1193
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Test1193 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int X = Integer.parseInt(br.readLine());
//몇번째 항인가
int count = 0;
//분자
int mole = 1;
//분모
int deno;
//범위중 시작 ex) 11 ~ 15 -> 11
int first = 0;
//범위중 끝 ex) 11 ~ 15 -> 15
int last = 0;
//초항(고정값)
int hang = 1;
for (int i = 0; i < 10000001; i++) {
//계차함수처럼 1 2 3 4씩 값을 더해준다.
hang += i;
// X보다 크면 break
// 동시에 해당 항에 범위를 넣어준다.
if (X < hang) {
//이 다음 첫번째 항 숫자 - 전 항 카운트 = 현재 첫번째 숫자
first = hang - count;
//이 다음 첫번째 항 숫자 - 1 = 현재 마지막 숫자
last = hang - 1;
break;
}
//아니면 다음 항으로 가기 때문에 1을 올려준다.
count++;
}
//분모 업데이트 (현재 항이 분모값과 동일)
deno = count;
// 범위 안에 숫자 갯수 (마지막 숫자 - 첫번째 숫자 + 1 = 숫자 범위 길이)
int length = (last - first) + 1;
// 범위 안에 숫자들을 담을 배열
String[] arr = new String[length];
//분자는 증가를, 분모는 증감을 해주며 배열에 넣어준다.
for (int i = 0; i < length; i++) {
arr[i] = mole++ + "/" + deno--;
}
//현재 항이 짝수 일때
//순서가 바뀌어서 나와 순서를 바꾸어준다.
if(count % 2 > 0) {
arr = changeReverse(arr);
}
//배열안에 원하는 값 인덱스 (받은 값 - 현재 항에 첫 숫자 = 받은 값에 인덱스)
int index = X - first;
System.out.print(arr[index]);
}
//배열에 순서를 바꾸어준다.
private static String[] changeReverse(String[] arr) {
List<String> list = Arrays.asList(arr);
Collections.reverse(list);
return list.toArray(arr);
}
}분자와 분모에 값을 서로 증가, 증감을 해주는데 애를 먹기보다는
1항, 2항, 3항...
1항에 1/1
2항에 1/2, 2/1...
식으로 항을 나누어서 문제를 푸니
계차수열을 이루었다.
천만 단위로 포문을 돌리고, 해당 조건이 맞으면 break으로 포문을 나왔다.
나오는 동시에 해당 항에 첫 번째와 마지막 숫자를 구하여,
그 사이에 있는 숫자들을 계산하여 배열에 담아주었다.
X로 받은 숫자가 배열에 어디 위치하는지 인덱스 값을 구해주었고,
답을 도출해낼 수 있었다.
예외적인 부분은 항이 짝수이면 배열 안에 값들의 순서를 반대로 바꾸어주어야 올바른
답이 나온다는 것을 확인할 수 있었다.
이제 구글에서 찾은 더 나은 답을 보자.
[백준] 1193번 : 분수찾기 - JAVA [자바]
https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제 분수를 찾는 것 자체는 그렇게 어려운 문제는 아니다. 다만 순서에 유의하여야 한..
st-lab.tistory.com
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int X = Integer.parseInt(br.readLine());
int cross_count = 1, prev_count_sum = 0;
while (true) {
// 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
if (X <= prev_count_sum + cross_count) {
if (cross_count % 2 == 1) { // 대각선의 개수가 홀수라면
// 분모가 큰 수부터 시작
// 분모는 대각선 개수 - (X 번째 - 직전 대각선까지의 누적합 - 1)
// 분자는 X 번째 - 직전 대각선까지의 누적합
System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
break;
}
else { // 대각선의 개수가 짝수라면
// 홀수일 때의 출력을 반대로
System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
break;
}
} else {
prev_count_sum += cross_count;
cross_count++;
}
}
}
}Stranger님의 답을 참고했다.
훨씬 보기 좋고 간결한 코드이다.
Arrays를 사용하지 않고, 짝수와 홀수를 판별해서 값을 뒤바꾸는 작업과,
for문을 한번 거치고, 따로 작업을 이어갔던 나와는 반대로
while문 안에서 한 번에 모든 걸 해결하고 break 한다는 점에서
좀 더 효율적이고, 간결하고, 보기 좋은 코드를 짜야한다는 점을 배웠다.
오늘은 이 한 문제로 마무리하려고 한다..
점점 어려워지지만 수학을 동시에 공부하면 두려울 건 없다고 생각이 든다.
