[Java] 백준 1193번: 분수찾기

hansung's·2024년 2월 24일

Java 알고리즘

문제 url:
분수찾기

문제:

🤔 문제 알아보기

나열된 분수들이 지그재그 순으로 나타나 X번째 분수를 구하는 문제
분수들이 1/1 -> 1/ 2 -> 2/1 -> 3/1 ....등으로 나타나며
분모가 1이고 분자보다 작다면 분자가 작아지면서 분모가 커지는 규칙
반대로 분자가 1이고 분모보다 작다면 분모가 작아지면서 분자가 커지는 규칙이 존재

즉 3/1 일때 분모가 1이며 분자가 크기 때문에, 분모가 커지면서 분자가 작아지는 그림으로 3/1 -> 2/2 -> 1/3이런식으로 진행된다.

또 1/4 일때는 분자가 1이고 분모가 크기 때문에, 1/4 -> 2/3 -> 3/2 -> 4/1 식으로, 문보가 작아지고 분자가 커지는 식으로 진행된다.

그 후 끝점 즉 3/1일 때는 1/3 또는 1/4일 때는 4/1로 갔을 때 분모 혹은 분자에 1을 더해서 새롭게 시작할 수 있도록 해야 한다.

적고있는 필자조차도 이걸 남이 이해할 수 없을거 같다는 생각이 드니깐 코드를 하나씩 분해하며 
설명하도록 하겠다.

🐱‍👤 실제 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbd = new StringBuilder();
        int x = Integer.parseInt(br.readLine());
        int up = 1;
        int down = 1;
        int count = 1;

        if(x == 1) {

        } else{
            while(count < x ) {
                if(up == 1 && up <= down) {
                    down++;
                    count++;

                    while(down !=1 && count < x) {
                        up++;
                        down--;
                        count++;

                    }

                } else if(down == 1 && down < up) {
                    up++;
                    count++;

                    while(up !=1 && count < x) {
                        up--;
                        down++;
                        count++;
                    }


                }
            }
        }
        System.out.println(sbd.append(up).append("/").append(down));

        //System.out.println(up + "/" + down);
    }
}

😎 코드 리뷰

변수 해석

int x = Integer.parseInt(br.readLine()); // X번째를 받기 위한 변수
int up = 1;   	// 분자를 의미
int down = 1; 	// 분모를 의미
int count = 1; 	// 추후 x와 비교해서 현재 위치를 파악하기 위한 count

첫 번째 if문

if(x == 1) {

 }

        System.out.println(sbd.append(up).append("/").append(down));

X가 1일 떄는 1/1을 출력하기 위해 if문안에는 아무것도 넣지 않고 바로 출력문으로 이동

else문

else{
            while(count < x ) {
                if(up == 1 && up <= down) {
                    down++;
                    count++;

                    while(down !=1 && count < x) {
                        up++;
                        down--;
                        count++;

                    }

                } else if(down == 1 && down < up) {
                    up++;
                    count++;

                    while(up !=1 && count < x) {
                        up--;
                        down++;
                        count++;
                    }


                }
            }
        }

while문 살펴보기

count는 현재 위치를 파악하기 위한 변수로 만약 x(원하는 위치)보다 크다면 해당 반복문이 끝나도록 설정

if(up == 1 && up <= down)

1/1을 포함하기 위해 up(분자) <= down(분모)를 한 것이며
이는 1/1 , 1/2, 1/3, 1/4 ...일 떄를 받기 위한 if문이다.
즉 현재 해당 위치면 끝점을 의미하기 때문에 분모에 1과 함께 움직였기 때문에 count에 1을 더함

while(down !=1 && count < x)

down(분모)가 1일 될때까지 down(분모)을 -1하고 up(분자)을 +1한다.
현재 움직인 위치가 원하는 위치와 같게되면 멈춰야 하니 count < x를 설정

그렇다면 반대로 else if문은 위와 정 반대라고 생각하고 구하면 된다.

🤢 회고

문제를 풀기위해 코드를 짯지만.. 이걸 누군가가 보신다면 조금은 창피한 코드라고 생각한다.
굉장히 러프하게 하드하게 코드를 짜게 되면서.. 규칙성을 찾았으나 약간 어거지로 맞추게 되어 이해하기 힘든 코드가 되었다.
규칙성을 보다 안정적으로 찾을 수 있도록 짜는 연습을 해보도록 하며
아래는 다른 블로그 글을 가져와 리팩트링하는 작업을 해보도록 하겠다.

😢 리팩토링

import java.io.*;

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;                        // 현재 대각선에 놓인 (칸)개수
        int prev_count_sum = 0;                     // 지금까지 대각선을 움직인 개수

        // 원하는 위치가 현재 대각선의 개수 + 현재까지 지나간 대각선 개수보다 작거나 같을 때까지 반복
        while(true) {

            if(X <= cross_count + prev_count_sum) {
                // 현재 대각선의 개수가 홀수일 경우
                // 즉 분자가 작아지고 분모가 커지는 그림을 떠올리면 된다.
                if(cross_count % 2 == 1) {
                    System.out.println((cross_count - (X - prev_count_sum - 1)) + "/" + (X-prev_count_sum));
                    break;

                } else {
                    System.out.println((X-prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
                    break;
                }
            } else {
                prev_count_sum += cross_count;
                cross_count++;
            }

        }
    }
}