[프로그래머스] Summer/Winter Coding(2019) -> 멀쩡한 사각형 - 자바스크립트

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

• W, H : 1억 이하의 자연수

입출력 예

WHresult

8

12

80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

---

<내 코드>

아이디어 :  전체 사각형에서 세로의 한줄씩 사용할 수 있는 것만 계산 -> 못쓰는 건 해당 세로줄에서 대각선이 가지는 최고값의 소수점 올림 정수값에서 대각선이 가지는 최소값의 소수점 첫째자리 내림값.

예시) 아래 이미지 기준으로 오른쪽 아래가 시작이라고 하면 

1번째 줄 : 세로줄 12개 - 2( 1.5의 올림 정수값) + 0 ( 0의 내림 정수값) = 10개 사용 가능
2번째 줄 : 세로줄 12개 - 3( 3의 올림 정수값) + 1 ( 1.5의 내림 정수값) = 10개 사용 가능

...

8번째 줄 : 세로줄 12개 - 12( 12의 올림 정수값) + 10 ( 10.5의 내림 정수값) = 10개 사용 가능

--> 총 80개 사용 가능

 

 previosSpare : 오염된 블록 아래 사용 가능한 블록의 갯수를 담고 있음. 

오른쪽 하단을 기준으로 시작하면 맨 처음에는 previosSpare 가 0 이다. 왜냐면 시작점이기 때문.
Math.ceil , floor 함수를 이용해 계산

//1차 시도
function solution(w, h) {
    let answer = 0;
    let previosSpare = 0;
    for(let i =1; i <= w; i++){
        let test = h*i/w
        answer += h - Math.ceil(test) + Math.floor(previosSpare)
        previosSpare = test;
    }
    return answer;
}

테스트12 실패 : 시간이 많이걸리나 싶어서 시간이 오래걸리나 싶어 로직 변경

---

//2차 시도
function solution(w, h) {
    let answer = 0;
    let previosSpare = 0;
    for(let i =1; i <= w; i++){
        let test = h*i/w
        answer += h - Math.ceil(test) + previosSpare // <- 변경
        previosSpare = Math.floor(test); // <- 변경
    }
    return answer;
}

테스트 12 실패 : 여전히 같은 코드에서 실패, 여기서 멘탈 붕괴 시작. Math 함수가 시간이 오래 걸리나 ? 아니면 부동수소점 연산이 문제인가 의심

---

//3차 시도
function solution(w, h) {
    let answer = w * h;
    let previosSpare = 0;
    let disable = 0;
    for(let i =1; i <= w; i++){
        let test = h*i/w;
        disable +=  Math.ceil(test) - previosSpare;
        previosSpare = Math.floor(test);
    }
    return answer - disable;
}

answer 를 구하는 과정에서 리소스를 잡아먹을수 있겠다는 생각이 불현듯 들어, 로직을 변경해봤음.

기존의 코드는 answer를 0 으로 초기화하고 함수가 돌때마다 값을 더해주는 구조였는데, 연산이 1억번까지 가버리면 합치는 로직에서 리소르를 어마무시하게 잡아먹을 것이라고 생각하고 로직 변경. 

아래 두 로직의 느낌. 지금은 문자열이라 확 느낌이 안오는데 우리 코드 상에선 add 부분이 크기가 급격하게 늘어나지 않지만 test 부분은 총합이라 급격하게 늘어나서 된거같음.

let test = "";

for(let i = 0; i < 5; i++){
	test += i
}

//test : 0
//test : 01
//test : 012
//test : 0123
//test : 01234

VS

let test = "";
let add = "";
for(let i = 0; i < 5; i++){
	add += i
}
test += add;

//test : ""
//test : "01234"

---

<다른 분 코드>

function solution(w,h){
    const gcd = (a, b) => {
        return b === 0 ? a : gcd(b, a % b);
    };

    return w * h - (w + h - gcd(w, h));
}

?? 공약수를 가지고 찾는 로직.. 이해못함 ㅅㄱ.