[프로그래머스-JS] level 2 멀쩡한 사각형 (*)
https://school.programmers.co.kr/learn/courses/30/lessons/62048
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
나의 코드
1) 실패한 코드
function solution(w, h) {
const sum = h*w;
if(w === 1 || h === 1) return 0;
if(w > h){
const divide = w / h;
return sum - Math.ceil(divide) * h;
}else if(h > w){
const divideW = h / w;
return sum - Math.ceil(divideW) * w;
}else{
return sum - w;
}
}
정확히 반절만 맞았다.
풀고풀고 하다가 1시간이 넘어서 질문하기에서 힌트를 찾았다.
그리고 다시 생각해보았다.
이 선은 직사각형이든 정사각형이든 양 끝점을 가로지른다.
이는 택시 기하학을 활용해서 풀 수있다는 뜻이다.
최단거리 구하기를 활용하면 된다.
문제 예제에서는 가로가 8cm 세로가 12cm이기에
8 + 12 = 20 이고 사용할 수 없는 정사각형은 16개이다.
즉 4개의 오차가 발생한다. 왜그럴까?
자세히 보면 대각선이 꼭지점을 지날때는 네모칸이 끊어져있다.
그런곳이 총 3곳이고 - 3 을해주면 17이된다. 그리고 여기서 - 1 만 더 해주면 16개가 된다.
그런데 가만보면 꼭지점 3개 + 1 = 4 이 4는 가로 8 세로 12의 최대 공약수이다.
그렇다면 사용할 수 없는 정사각형의 개수는 ?
12 + 8 - 4 = 16
다른 경우도 같은까?
이 경우에도 10, 8의 최대 공약수는 2이다.
즉 꼭지점 1 + 1
따라서 사용할 수 없는 정사각형은
10 + 8 - 2 = 16
그렇다면 최대공약수가 없다면 ???
대각선이 만나는 꼭지점이 없다.
10 , 3의 최대 공약수는 0
따라서 사용할 수 없는 정사각형은
10 + 3 - 0 = 13
이걸 식으로 나타내면
문제에서는 사용가능한 정사각형의 개수를 구하라고 했으니까
전체 정사각형의 개수 - 사용할수 없는 정사각형의 개수
= 가로 x 세로 - ( 택시 기하학 - (w, h)의 최대 공약수)
= w x h - ( w + h - gcd )
이것을 코드로 나타낸다면 아래와 같다.
2) 성공한 코드
function solution(w, h) {
const gcd = (a,b) =>{
const remainder = a%b;
if(!remainder) return b;
return gcd(b, remainder)
}
return w*h - (w+h - gcd(w,h))
}