[프로그래머스] 유한소수 판별하기(유클리드호제법, 소인수분해)

2023. 2. 27. 10:53·Algorithm
728x90
반응형

https://school.programmers.co.kr/learn/courses/30/lessons/120878

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr



문제 푼 코드

package programmers.pr2023.Lv0.February;

import java.util.HashSet;
import java.util.Iterator;

public class Lv0_유한소수판별하기_20230227 {
    class Solution {
        public int solution(int a, int b) {
            // 유한소수라면 1, 무한소수라면 2(유한소수 조건 : 분모의 소인수가 2와 5만 존재)
            // 정수도 유한소수로 판별
            int answer = 1;
            
            if(a == b) return 1; // 같다면 정수이므로 유한소수
            if(b == 1) return 1; // 분모가 1이라면 유한소수

            // 기약분수 나타내기(유클리드호제법)
            // a > b 일때, r = a%b, a = b, b = r; b가 0이 될 때의 a가 최대공약수
            if(a > b) {
                int r = 0;
                int x = a;
                int y = b;
                while(y != 0) {
                    r = x % y;
                    x = y;
                    y = r;
                }

                a = a / x;
                b = b / x;

                // 분모가 1이면 유한소수
                if(b == 1) return 1;
            }

            if(b > a) {
                int r = 0;
                int x = b;
                int y = a;
                while(y != 0) {
                    r = x % y;
                    x = y;
                    y = r;
                }

                a = a / x;
                b = b / x;

                // 분모가 1이면 유한소수
                if(b == 1) return 1;
            }
            
            // 방법1) 소인수분해
            HashSet<Integer> set = new HashSet<>();
            int k = 2;
            int n = b;
            while(k <= n) {
                if(n % k == 0) {
                    set.add(k);
                    n = n/k;
                } else {
                    k++;
                }
            }

            Iterator<Integer> iter = set.iterator();
            while(iter.hasNext()) {
                int temp = iter.next();
                if(!(temp == 2 || temp == 5)) {
                    return 2;
                }
            }

            return answer;
        }
    }
}

힌트를 보고 유클리드호제법을 사용해서 최대공약수를 구해 기약분수로 만들고 분모를 소인수분해하여 2,5외에 다른 값이 있으면 2를 리턴하도록 했었는데 테스트 케이스에서 계속 실패..

이유가 뭘까 반례를 찾다가 정수인 경우에도 유한소수로 판별하기 위해 분자와 분모가 같으면 1을 리턴, 분모가 1일 경우 정수이므로 1을 리턴하도록 수정했다.

그래도 테스트 케이스 일부분이 실패..

유클리드호제법을 사용할 때 a > b라는 조건이 있는데 꼭 분모가 크다라는 법은 없으니 반대의 경우도 유클리드호제법을 사용하도록 조건을 추가하였고 각 분기의 유클리드 호제법을 사용한 뒤 분모가 1인 경우에는 유한소수이기 때문에 1을 리턴하도록 하였다.

 

결과는 모든 테스트 케이스를 통과!!

 

레벨0 문제라면서.. 어려웠고.. 생각할 게 너무 많았다ㅠㅠ

728x90
반응형

'Algorithm' 카테고리의 다른 글

[프로그래머스] 평행 (직선의 평행 조건)  (0) 2023.03.15
[프로그래머스] 연속된 수의 합(등차수열의 합)  (0) 2023.03.07
[프로그래머스] 문자열 정렬하기(1)  (0) 2023.02.07
[프로그래머스] 분수의 덧셈 / 유클리드 호제법(최대공약수 구하기)  (0) 2023.01.30
[프로그래머스] 단어 변환 / DFS/BFS(그래프탐색)  (0) 2022.08.15
'Algorithm' 카테고리의 다른 글
  • [프로그래머스] 평행 (직선의 평행 조건)
  • [프로그래머스] 연속된 수의 합(등차수열의 합)
  • [프로그래머스] 문자열 정렬하기(1)
  • [프로그래머스] 분수의 덧셈 / 유클리드 호제법(최대공약수 구하기)
야리니
야리니
오늘보다 내일 더 성장하는 개발자가 되기 위한 야리니 블로그입니다 :)
    반응형
    250x250
  • 야리니
    야리니의 step by step
    야리니
  • 링크

    • GitHub
    • Linkedin
  • 전체
    오늘
    어제
    • 분류 전체보기 (478) N
      • TIL (379)
        • Java (97)
        • Kotlin (28)
        • JPA (16)
        • Spring (37)
        • Oracle (22)
        • JDBC (7)
        • Web(HTML, CSS, JS, jQuery) (90)
        • View Template (31)
        • AWS (7)
        • HTTP (7)
        • CS (5)
        • Linux, Unix (2)
        • Python (20)
      • Trouble Shooting(Error) (37)
      • Algorithm (15)
      • Git,GitHub (8)
      • Diary (24) N
      • 독서 (9)
      • Etc (6)
        • Mac (1)
        • 학원준비과정 (2)
  • 블로그 메뉴

    • 방명록
    • 태그
  • 공지사항

    • 안녕하세요 :)
  • 인기 글

  • 태그

    코틀린
    java기초
    백엔드 개발자
    쌍용교육센터
    java
    HTML
    국비지원학원
    oracle
    CSS
    Kotlin
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
야리니
[프로그래머스] 유한소수 판별하기(유클리드호제법, 소인수분해)
상단으로

티스토리툴바