[Lv.0] 순서쌍의 개수 *

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

프로그래머스

 

문제 설명

순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 

자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

 

제한사항

 

입출력 예

입출력 예 설명

 

아이디어

• n이 뭔질 모르는데 어떤 걸 곱했는지 내가 어떻게 알아?
• 곱했을 때 n이라고 했고, 순서쌍이라고 했으니까, 이게 n의 약수 중에 있나? 이렇게 접근하면,                                      엄청 복잡한 로직이 된다.
• 완전탐색으로 접근이 가능하다.
• 그런데 이 때 완전탐색으로 접근을 하는 게 뭐냐면, 일단 모든 순서쌍을 다 만들어 본 다음, 모두 곱해보고, 그 중에 n 인게 나오면 개수를 세는 방식으로 만들려고 접근하는 것이다.
• 남은 문제는,,, 모든 순서쌍을 어떻게 알 수 있는지?
• 두 수의 곱이 n이 되려면 a와 b의 범위는 어떻게 되어야 하는지를 생각해봐야.
• 여기서 의미있는 발견, a와 b는 일단 무조건 n보다는 작아야 한다.
• a와 b 관련해 모든 경우의 수를 다 보고싶다면, 반복문이 2개 필요해. 그래서 while문 쓰는 것은 적절치 않다.
• 반복문 2개는 순차적인 것이 아니라 중첩된 것.
• a와 b를 곱했을 때, n이라는 소리는, 하나의 순서쌍을 찾았다는 의미와 같다.
• 그럼 answer의 숫자를 하나 증가시켜줘야지.
• 곱셈은 0부터 시작하는 게 바람직하지 않다고 했으므로 이 부분은 고려해주어야 한다. 

 

나의 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int a = 0;
        int b = 0;
        
        for(a=1; a<=n; a++) {
            for(b=1; b<=n; b++) {
                if(n == a*b) {
                    answer++;
                }      
            }
        }
        return answer;
    }
}

• 여기서 코드를 실행해보면, 정답은 맞으나 실행시간 초과라고 해서 틀렸다고 결과가 나온다.
• 왜냐면 n이 최대 100만이기 때문.
• 완전탐색의 단점이, 하나하나 일일이 다 따지는 것이므로, 너무 무겁고 오래걸린다는 것이었다.
• 탐색 공간이 너무 오래걸린다.

 

개선

• 풀이는 a와 b 둘 다 모르니까 다 돌아본거다. 100만까지.
• 두 개의 수를 곱했을 때 n이 되는 수를 찾는 것이 문제.
• 조금 더 줄일 수 있는 아이디어를 생각해보자.
• => 적당히 작은 값을 넣어서 테스트해보면 된다.
• 먼저, 입출력 예를 보면서 생각해보면, 일단 곱해서 나오니까 인수분해 해서 약수끼리 쌍을 지어본다.
• 결국, 문제를 재정의해보면 "n의 약수 찾기"가 된다.
• 반복 횟수를 조금 줄여서 n의 약수를 찾을 수 없는지를 탐색해본다.
• => 굳이 a나 b로 나눌 필요가 없이 나머지 연산자를 사용해서 나머지가 0이면 약수라고 생각하면 되겠지.

 

개선된 답안

class Solution {
    public int solution(int n) {
        int answer = 0;

        for(int i=1; i<=n; i++) {
            if(n%i==0) {
                answer++;
            }
        }        
        return answer;
    }
}

• 0으로 나눌 수 없다는 에러 종종 발생하니 유의.