[백준] 카잉 달력 : 6064 : Java - 브루트 포스 (S1)

1.  💎 문제

6064번: 카잉 달력

 

 

---

 

 

2.  🤔 어떻게 풀까

 문제를 잘 읽어보면 달력에 표현되는 수는 x는 M으로 나눈 나머지, y는 N으로 나눈 나머지 값이다. 

그러므로 입력으로 주어진 x,y가 몇 번째 해를 아는지 알기 위해서는 결국 아래 두 조건을 만족시키는 최소 공배수가 필요하다.

• M으로 나누었을 때 나머지가 x이다.
• N으로 나누었을 때 나머지가 y이다.

최소 공배수를 구하기 위해, x,y를 시작으로 각 M, N을 더해가면서 기존에 나왔던 수인지 비교한다. 비교하기 위해 `HashSet`을 이용하였다. 방법은 아래와 같지만 시간초과가 났다.

 public static int getYear(int M, int N, int x, int y){
        int nextX = x%M;
        int nextY =y%N;

        HashSet<Integer> xNums = new HashSet<>();
        HashSet<Integer> yNums = new HashSet<>();
        while(nextX <= M*N || nextY <= M*N){
            xNums.add(nextX);
            yNums.add(nextY);
            if(nextX == 0 && nextY == 0){
                nextX += M;
                nextY += N;
                continue;
            }


            if(yNums.contains(nextX) && xNums.contains(nextY))
                return Math.min(nextX, nextY);
            if(yNums.contains(nextX))
                return nextX;
            if(xNums.contains(nextY))
                return nextY;

            nextX += M;
            nextY += N;
        }
        return -1;
    }

 

더 간단한 로직이 필요하다! 단순한 최소공배수를 구하는 것이 아닌 나머지 또한 고려해야되기 때문에 어려웠다.

결국 알아낸 로직은 y값만을 N씩 증가시키고 바로 그때 M으로 나눴을 때 x값이 되는지 확인하는 것이다.

그리고 또 조심해야할 것은 y가 0이 아닐 때를 체크해야한다. y가 0이면 바로 while문을 빠져나가 잘못된 결과가 리턴된다.

나누기 연산할 때는 0일 때를 잘 생각할 것!

public static int getYear(int M, int N, int x, int y){
        int nextY =y%N;
        
        while(nextY <= M*N){
            if((nextY-x)%M == 0 && nextY!= 0)
                return nextY;
            nextY += N;
        }
        return -1;
    }

 

 

3.  📄  전체 코드

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++){
            String [] input = br.readLine().split(" ");
            int M = Integer.parseInt(input[0]);
            int N = Integer.parseInt(input[1]);
            int x = Integer.parseInt(input[2]);
            int y = Integer.parseInt(input[3]);

            int year = getYear(M,N,x,y);
            if(year == 0)
                year = -1;
            bw.write(year +"\n");
        }
        bw.flush();

        bw.close();
        br.close();
    }

    public static int getYear(int M, int N, int x, int y){
        int nextY =y%N;

        while(nextY <= M*N){
            if((nextY-x)%M == 0 && nextY!= 0)
                return nextY;
            nextY += N;
        }
        return -1;
    }
}