기사단원의 무기, 비밀지도 - level1

- 기사단원의 무기 문제

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

프로그래머스

 

- 풀이

걸린 시간 : 40 ~ 45분

class Solution {
    public int solution(int number, int limit, int power) {      
        int answer = 0;
        for(int i = 1; i <= number; i++){
            int count = 0;
            for(int j = 1; j <= Math.sqrt(i); j++){
                if(i % j == 0){
                    count += 1;
                }
            }
            if(i % Math.sqrt(i) == 0){
                count = count * 2 - 1;
            } else {
                count = count * 2;
            }
            if(count > limit){
                answer += power;
            } else {
                answer += count;
            }
        }
        return answer;
    }
}

이 문제는 중첩 for문의 시간을 줄여야만 하는 문제였다.

처음에는 그냥 중첩 for문을 썼는데, 시간 초과가 걸려서

어떻게 줄이지 생각을 했다.

그러다 문득, 어딘가에서 들었던게 생각이 났다.

바로 약수를 찾을 땐, 해당 수의 제곱근 및에서 찾은 다음, 곱하기 2를 하면

약수의 개수가 나온다는 것을 깨달았다.

 

하지만 1, 4, 9와 같은 정확히 제곱근이 정수로 떨어지는 애들은 어떻게 해야하나

고민하다가,

제곱근으로 나누었을때 나머지가 0인 애들은 -1을 따로 해주면 되었다.

 

그렇게 문제 해결!

잘한 사람들 보니, 중첩 for문을 쓴것을 보고 이건 어쩔 수 없다고 생각했다.

 

- 비밀지도 문제

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

프로그래머스

 

- 풀이

걸린 시간 : 40~45분

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] binary = new String[n];
        for(int i = 0; i < n; i++){
            binary[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
            if(binary[i].length() != n){
                binary[i] = "0".repeat(n - binary[i].length()) + binary[i];
            }
            binary[i] = binary[i].replace("1", "#");
            binary[i] = binary[i].replace("0", " ");
        }
        return binary;
    }
}

카카오는 참 문제를 잘 내는것 같다.

기초적인 것을 잊지 말라는 느낌의 문제였다.

 

이문제를 고민하는데, int를 어떻게 String의 2진수로 바꾸나 했더니

toBinaryString이라는 것을 알게되었다.

하지만 여기서 또 문제가 발생했는데

어떻게 String 끼리 2진수를 비교해서 or 연산을 수행하지?

 

답은 기초에 있었다.

바로 "논리연산자"를 사용하면 된다.

논리 연산자 " | " 는 Int Int -> Int를 반환하는데,

주어진 배열의 값이 Int이니,

or 연산 먼저 계산 후 toBinaryString을 하면 아주 간단하게 답이 나온다.

 

toBinaryString은 앞이 0이면 그 값은 포함하지 않아서,

따로 0을 추가해주는 작업을 해야했다.

 

그후 replace를 수행하면 끝!

함수와 기초를 탄탄히 해야한다...

이 문제는 그리고 StringBuilder를 썼다면, GC 사용도를 줄일 수 있다고 생각한다.