[백준/BOJ] 1193번 분수찾기(Node js/javascript)

1193번: 분수찾기 (acmicpc.net)

1193번: 분수찾기

 

문제해석

먼저 문제에 분수들이 담긴 무한한 배열을 규칙을 찾기 쉽도록 나열해보자.

1/1                                    
(1)

1/2 -> 2/1     -asc                         : 2
(2)      (3)    

3/1 -> 2/2 -> 1/3   -desc              : 3
(4)      (5)      (6)                           

1/4 -> 2/3 -> 3/2 -> 4/1   -asc      : 4
(7)      (8)      (9)     (10)
                 .
                 .
                 .

 

위와 같이 나열했을때 가장 먼저 눈에 보인 규칙은

 

1. 짝수일때 asc(오름차순), 홀수일때 desc(내림차순)이다.

 

2. 분수들이 위와 같이 [1/1] , [1/2 -> 2/1], [3/1-> 2/2 -> 1/3] ... 와 같이 나누어 그룹을 특정했을 때,

 그룹의 index가 곧 해당 그룹의 분모 혹은 분자에 들어갈 수 있는 최대값이자, 해당 그룹의 원소의 개수이다.

 Ex) 4번째 그룹의 원소의 개수는 4, 분모 혹은 분자의 최대값도 4

 

 

위와 같은 특징들로 함수의 매개변수들을 먼저 구상했다.

 

매개변수   : i(int) , : denominator(int), : numerator(int), : asc(boolean)

몇번째 분수인지를 세기 위한 인자 : i,

분자 : denominator

분모 : numerator

오름차순인지 판단 : asc

 

변수명은 최대한 직관적으로 지으려는 버릇을 들이고 있다.

이제 함수를 작성해보자,

const fountains = (i, numer, deno, asc) => {

  if (i >= N) {      //  i 가 N(i입력받은 값)과 같다면 answer에 출력값을 넣고 return;

    answer = numer + "/" + deno;

    return;

  } else {

    if (asc) {

      if (deno == 1) {

        fountains(i + 1, 1, numer + 1, !asc);

      } else {

        fountains(i + 1, numer + 1, deno - 1, asc);

      }

    } else {

      if (numer == 1) {

        fountains(i + 1, deno + 1, 1, !asc);

      } else {

        fountains(i + 1, numer - 1, deno + 1, asc);

      }

    }

  }

};

처음에는 위와 같이 작성하고,  매개변수에 각각 2, 1, 2, true 를 입력하여 아래의 1/2에서 함수가 시작하여 재귀호출 방식으로 분수를 만들고 동시에 해당 분수가 몇번째 분수인지 세도록 하였다.

 

그런데 위와 같이 실행하니 아래와 같이 StackSizeExceeded 런타임 에러가 발생했다.

 

처음에는 빠져나오는 구문을 놓친 부분이 있는줄 알고 찾아보고 여기저기 구석구석 return을 넣어보고 돌려도 봤는데 될 리가 없었다.

찾아보니 javascript는 JS(javascript)엔진이 함수를 call stack에 쌓아놓고 실행하는데 예제 입력의 최대값이 10,000,000이여서 이를 재귀함수로 호출하려니 call stack이 꽉차서 에러가 나버린 것 같았다. 이렇게 보니 java로 로직을 구현했어도 어차피 시간초과가 났을 것 같다.

 

그래서 생각해낸 해결방안은, 만약 입력받은 값이 9라고 가정한다면, 9번째 분수가 속해 있는 그룹의 index를 찾고, 해당 그룹의 1/index 혹은 index/1가 몇번째 분수인지만 찾으면 그 지점 부터 재귀 함수를 시작하는 것이다.

 

1/1   <<---여기가 아니라                             
(1) 

1/2 -> 2/1     -asc                         : 2
(2)      (3)    

3/1 -> 2/2 -> 1/3   -desc              : 3
(4)      (5)      (6)                           

1/4 -> 2/3 -> 3/2 -> 4/1   -asc      : 4  <<---여기부터
(7)      (8)      (9)     (10)
                 .
                 .
                 .

9번 분수의 그룹 index는 4, 1/4는 7번째 분수이므로 7번째 분수부터 재귀호출을 시작한다.

 

 

전체코드

const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim();

var N = Number(input);

var answer = 0;

var find_group_sum = 1;

var find_group_index = 1;

while(true){  //찾는 분수의 Group index와, 해당 그룹의 첫번째 분수의 번호를 찾는 로직

    if(find_group_sum > N){

        find_group_index--;

        find_group_sum -= find_group_index;

        break;

    }

    find_group_sum = find_group_sum + find_group_index ;

    find_group_index++;

}

const fountains = (i, numer, deno, asc) => {  //재귀 함수 부분

  if (i >= N) {

    answer = numer + "/" + deno;

    return;

  } else {

    if (asc) {

      if (deno == 1) {

        fountains(i + 1, 1, numer + 1, !asc);

      } else {

        fountains(i + 1, numer + 1, deno - 1, asc);

      }

    } else {

      if (numer == 1) {

        fountains(i + 1, deno + 1, 1, !asc);

      } else {

        fountains(i + 1, numer - 1, deno + 1, asc);

      }

    }

  }

};

if(find_group_index % 2 == 0){

    fountains(find_group_sum, 1, find_group_index, true);

}else{

    fountains(find_group_sum, find_group_index, 1, false);

}

if (N > 1) {

  console.log(answer);

} else {

  console.log("1/1");

}