(Java) 프로그래머스 - 멀쩡한 사각형

2022. 7. 14. 00:54·코딩 테스트

알고리즘 문제보다 수학 문제 같았다.

문제 풀이 방법에는 두 가지가 있다.

첫 번째는 규칙을 찾아 푸는 방법이고

두 번째는 기울기를 이용해서 푸는 방법이다.

나는 규칙을 찾아가면서 풀었지만 기울기를 이용한 방법이 더 간편해 보인다.

 

입력값이 int로 주어지고 w와 h값이 각각 1억 이하의 자연수이기 때문에

사용할 수 없는 사각형 계산을 하면서 인티저 오버플로가 발생할 수 있다.

따라서 입력값을 전부 long으로 형 변환 후 계산했다.

또한 최대 공약수가 1억을 넘을수는 없기 때문에 int로 선언했다.

 

최대 공약수를 구하는 방법도 세 가지가 있는데

첫 번째는 w와 h를 BigInteger로 변환하고 BigInteger에 내장된 gcd를 사용하는 방법

두 번째는 재귀를 이용한 유클리드 호제법

세 번째는 반복문을 이용한 유클리드 호제법이다.

나는 세번째 방법만 알았는데 이번 문제를 통해서 첫 번째와 두 번째 방법도 사용할 수 있다는 걸 배웠다.

세 가지 방법 모두 같은 방식으로 값이 도출되는데 그중 가장 코드가 짧은 첫 번째 방법을 사용했다.

 

최종 코드

import java.math.BigInteger;
class Solution {
    public long solution(int w, int h) {
        
        // 입력값 long으로 변환
        long lw = Long.valueOf(w);
        long lh = Long.valueOf(h);

        // 최대공약수
        int gcd = BigInteger.valueOf(lw).gcd(BigInteger.valueOf(lh)).intValue();

        // 전체 사각형
        long quadrangle = lw * lh;

        // 반복되는 사각형에서 사용할수 없는 사각형의 개수
        long reQuadrangle = ((lw / gcd) + (lh / gcd) - 1) * gcd;

        // 답
        long answer = quadrangle - reQuadrangle;
        return answer;
    }
}

'코딩 테스트' 카테고리의 다른 글

(Java) 프로그래머스 - 순위 검색  (0) 2022.07.16
(Java) 백준 15686 - 치킨 배달  (0) 2022.07.15
(Java) 프로그래머스 - 게임 맵 최단거리  (0) 2022.07.12
(Java) 백준 12865 - 평범한 배낭  (0) 2022.07.12
(Java) 백준 1932 - 정수 삼각형  (0) 2022.07.11
'코딩 테스트' 카테고리의 다른 글
  • (Java) 프로그래머스 - 순위 검색
  • (Java) 백준 15686 - 치킨 배달
  • (Java) 프로그래머스 - 게임 맵 최단거리
  • (Java) 백준 12865 - 평범한 배낭
로승리
로승리
  • 로승리
    Roy's Blog
    로승리
  • 전체
    오늘
    어제
    • 분류 전체보기
      • Issuefy
      • Language
      • Spring
      • Database
      • Network
      • Kubernetes
      • AWS
      • 코드스쿼드
      • 코딩 테스트
      • 생각정리
      • 국비지원
      • 회고
      • 컨퍼런스, 세미나
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
로승리
(Java) 프로그래머스 - 멀쩡한 사각형
상단으로

티스토리툴바