[Java] 카잉달력

1. 문제 설명

두 자연수 m, n이 주어진다.
카잉제국은 달력을 <k:y>의 형식으로 표현
k = 1, m 사이, y = 1, n 사이를 순환하며 증가한다
ex) m = 10, n = 12
첫해 : <1, 1> / 11번째 해 : <1:11> / 13번째 해 : <3 : 1>/ 60번째 해 : <10 : 12>
단, 중복은 없고 정답이 없다면 -1

네 개의 정수 M, N, x 와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는 지를 구하는 프로그램을 작성하라.

입력 형식

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력 형식

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

2. 알고리즘 접근

정수의 특징을 사용하면 굉장히 쉽다
k 번째 x = 1 + (k - 1) % m
k 번째 y = 1 + (k - 1) % n
위와 같이 x, y를 구하는 것은 간단하다
허나 우리는 x, y가 몇번 째 해인지를 알아야한다
반복문을 통해 x,y가 일치하는지 탐색할 수 있지만 이는 계산량이 너무 많다
규칙성을 통해 최적화하자
x와 값이 다를때 우리가 굳이 탐색을 이어나갈 필요가 있는가? -> 전혀 없다
즉 x의 값이 일치할 때만 y값을 탐색해서 최적화(소스코드 구현 참고)

3. 소스코드

import java.util.Scanner;

public class Q4H {
   static final Scanner sc = new Scanner(System.in);
   private static void testCase(int caseIndex) {

       int m = sc.nextInt(); // 자연수 m  // 10, 12
       int n = sc.nextInt(); // 자연수 n

       int x = sc.nextInt(); // 자연수 k
       int y = sc.nextInt(); // 자연수 y 입력받은 x y가 몇번째 해인지 구해보쟈

       // 카잉 달력 생성
       KaingCalender calender = new KaingCalender(m, n);

       // 이 달력에서 <x, y>가 몇 번째 연도인지 계산
       int answer = calender.getIndex(x, y);

       System.out.println(answer);
   }

   public static void main(String[] args) {

       int caseSize = sc.nextInt();

       for(int caseIndex = 1; caseIndex <= caseSize; caseIndex++){
           testCase(caseIndex);
       }

   }
}
class KaingCalender{
   final int M; // 왼쪽 번호 최대 값
   final int N; // 오르쪽 번호 최대 값
   KaingCalender(int M, int N){
       this.M = M;
       this.N = N;
   }
   public int getXbyIndex(int index){
       return 1 + (index - 1) % M;
       // index % M = 나머지 0인 경우가 있기에 1을 뺏다가 결과값에 1을 더한다
   }
   public int getYbyIndex(int index){
       return 1 + (index - 1) % N;
   }

   // 이 달력에 <x, y>라는 연도가 최초로 등장하는 순번 (등장하지않으면 -1)
   public int getIndex(int x, int y){
       for(int index = x; index <= M * N; index+=M){ // x가 일치할 때만 탐색
           if(getYbyIndex(index) == y){ // x에 해당하는 index를 탐색하여 y와 일치한다면
               return index; // 해당 인덱스를 리턴한다.
           }
       }
       return -1;
   }

}