프로그래머스LV2_2

공부 방법 개선

1. 문제만 풀고 블로그에 리뷰하는 방식이 아니라 LV2부터는 일주일 중 6일은 문제 풀고 1일은 그 주의 문제 중 어렵거나 헷갈렸던 문제를 다시 처음부터 풀어보는 방식으로 진행
2. 매일 1문제 이상씩 풀기(1문제가 안된다면 문제를 보고 생각해보기라도 해보는 식으로 진행)

최솟값 만들기

접근 과정

1. 길이가 같은 배열인 것을 인지
2. 최솟값을 만들려면 큰 수와 작은 수를 곱하는 것을 생각함
3. 따라서 배열을 정렬하여 큰 수와 작은 수를 곱하여 누적하면 해결

시행착오

• 시행착오 없이 해결
  

해결 코드

• 접근 과정대로 순서대로 구현하여 해결
  

import java.util.*;
    
class Solution
{
	public int solution(int []A, int []B)
    {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        int l = A.length;
        for(int i = 0; i < l; i++){
            answer += A[i] * B[l - 1 - i];
        }
        return answer;
        }
    }

시간복잡도

이진 변환 반복하기

접근 과정

1. 문제의 조건대로 문자열의 0을 제거
2. 문자열 길이를 2진법 문자열로 변환
3. 길이가 1이 될 때까지 반복
4. 반복하면서 횟수와 빠진 0의 개수를 더하여 반환

시행착오

• String.replace()를 하여 문자열에 담아야 하는데 이를 하지 않아 무한 루프를 돌아 잘 안됐었다.
  

해결 코드

• 시행착오에서 겪은 문제를 해결하기 위해 문자열을 담으니 해결
  

import java.util.*;
    
class Solution {
	public int[] solution(String s) {
		int[] answer = new int[2];
        while(!s.equals("1")){
          int l = s.length();
          s = s.replace("0", "");
          int c = s.length();
          answer[0]++;
          answer[1] += (l - c);
          s = Integer.toBinaryString(c);
        }
        return answer;
    }
}

시간복잡도

숫자의 표현

접근 과정

1. 2중 반복문으로 i부터 n까지 더해 n이 되는지를 체크
2. n이 넘어가면 break(이게 없으면 시간 초과)

시행착오

• 2중 반복문에 하지 않으려고 수학 규칙을 찾으려고 했는데 못찾았는데 다른 사람 풀이에서 찾긴 했는데 정확한 규칙을 AI한테 물어봤는데 조금 복잡했다.
  

해결 코드

• 2중 반복문으로 접근 과정대로 해결
  

class Solution {
	public int solution(int n) {
    	int answer = 0;
    	for(int i = 1; i <= n; i++){
    		int sum = 0;
    		for(int j = i; j <= n; j++){
    			sum+= j;
    			if(sum == n){
    				answer++;
    				break;
    			}
    			if(sum > n) break;
    		}
    	}
    	return answer;
    }
}
    
// 다른 사람 풀이
class Solution {
	public int solution(int n) {
		int answer = 0;
		for (int i = 1; i <= n; i += 2) 
			if (n % i == 0) answer++;
		return answer;
	}
}

시간복잡도