내일은 알고리즘

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

배열 두개의 원소를 하나씩 뽑아 곱해 합을 가장 작게 만드는 문제입니다.

풀이 아이디어부터 말하자면, 두 배열을 정렬해 큰수 - 작은수를 순서대로 짝을 맞춰주면 됩니다. 증명이 떠오르지 않더라도 이렇게 하지 않으면 안된다는 사실은 쉽게 떠올릴 수 있습니다.

예를 들어 작은 수 a, 큰 수 A가 있고 작은 수 b, 큰 수 B가 있다고 해봅시다.

a보다 큰 수 A는 두 수의 차이를 n이라고 하면 a + n으로 생각할 수 있습니다. 마찬가지로 B는 b + m으로 생각할 수 있습니다.

작은수 - 큰수 쌍으로 곱한다면, ab + am + ab + bn이 됩니다. 만약 이 순서를 지키지 않고 곱한다면 ab + ab + am + bn + mn이 됩니다. 즉 A와 B가 a와 b보다 큰 mn 만큼 합이 커지게 됩니다. 따라서 작은수가 큰 수와 짝을 이루게 곱해야 더 작은 합이 됩니다.

(제가 수학 전공이 아니기 때문에 수학적 증명은 틀릴 수도 있습니다.)

두 배열을 오름차순 / 내림차순으로 정렬을 해 곱해도 되고, 길이가 같기 때문에 둘 다 오름차순으로 정렬해 앞과 뒤에서부터 곱해주어도 됩니다.

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;

        Arrays.sort(A);
        Arrays.sort(B);
        
        for(int i = 0; i < A.length; i++){
            answer += A[i] * B[B.length - i - 1];
        }

        return answer;
    }
}

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

스택 연습문제로 되어있지만 사실 스택 없이도 풀 수 있는 문제입니다.

잘 생각해 보면 올바른 괄호는 '여는 괄호와 닫는 괄호의 수가 같고' 여는 괄호보다 닫는 괄호가 많이 나오지 않는 형태입니다. 닫는 괄호가 많아진다면 반드시 잘못된 형태지만 여는 괄호가 많은 경우는 이후에 나오는 닫는 괄호와 짝을 이루어 올바른 형태가 될 수 있기 때문이죠.

따라서 입력을 한 번 순회하면서 여는 괄호보다 닫는 괄호가 많아지는지, 입력을 다 순회하고 나서 열고 닫는 괄호 짝이 전부 만들어졌는지를 체크하면 됩니다. 

두 경우 모두 만족하지 못하는 순간 False를 return 하면 됩니다.

	class Solution {
	    boolean solution(String s) {
	        boolean answer = true;
	        
	        char[] cArr = s.toCharArray();
	        int count = 0;
	        
	        
	        for(int i = 0; i < cArr.length; i++){
	            if(cArr[i] == '(') {
	            	count += 1;
	            }else {
	            	count -= 1;
	            }
	            
	            if(count < 0) {
	            	answer = false;
	            	break;
	            }
	        }
	        
	        if(count != 0) {
	        	answer = false;
	        }

	        return answer;
	    }
	}

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

문자열의 단어 시작을 관리하고 첫 스펠링만 대문자로, 나머지는 소문자로 만드는 문제입니다. 

공백문자가 여러번 나올 수 있기 때문에 boolean으로 공백문자를 만날때 마다 새로운 단어로 판단하도록 체크했습니다.

대문자와 소문자 변환은 ascii 값을 이용했는데, 언어에서 제공하는 내부 메소드를 사용해도 간편하게 풀 수 있습니다.

class Solution {
    public String solution(String s) {
        char[] cArr = s.toCharArray();
        boolean flag = false;
        for(int i = 0; i < cArr.length; i++) {
            if(!flag && 97 <= (int)cArr[i] && (int)cArr[i] <= 122) {
                cArr[i] = (char)((int)cArr[i] - 32);
            }else if(flag && 65 <= (int)cArr[i] && (int)cArr[i] <= 90) {
                cArr[i] = (char)((int)cArr[i] + 32);
            }

            if(cArr[i] == ' ') {
                flag = false;
            }else {
                flag = true;
            }
        }

        return new String(cArr);
    }
}

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

문자열을 쪼개고 최댓값, 최솟값 관련 메소드를 알면 쉽게 풀 수 있는 문제입니다. 

예전 문제라 Lv2이고 요즘 코딩 테스트 난이도로는 Lv1이 맞을것 같네요.

import java.util.StringTokenizer;

class Solution {
    public String solution(String s) {
        StringTokenizer st = new StringTokenizer(s);
        String answer = "";
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        while(st.hasMoreElements()) {
            int n = Integer.parseInt(st.nextToken());
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
        return Integer.toString(min) + " " + Integer.toString(max);
    }
}

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

분명히 프로그래머스 Lv1 문제를 전부 다 풀었었단 말이죠... 

카카오 서버가 불타고 티스토리도 덩달아 뻗어서 반 강제적으로 알고리즘 공부를 못한 일주일 사이에 Lv1문제가 리필되었습니다. 제논의 역설도 아니고... ㅋㅋ

아무튼 유명한 콜라문제의 속임수 없는 버전입니다. 마지막에 콜라를 한 병 더 살수있다는 꼼수가 막혔음을 유의하세요!

	class Solution {
	    public int solution(int a, int b, int n) {
	        int answer = 0;
	        
	        while(n >= a){
	            int bottle = (n / a) * b;
	            n = (n % a) + bottle;
	            answer += bottle;
	        }
	        
	        return answer;
	    }
	}

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

기본적인 반복문 중첩으로 풀이할 수 있는 완전탐색 문제입니다.

선택한 번호가 겹치지 않도록 반복문의 시작 범위를 잘 잡아주고 모든 경우에 대해 세 번호의 합이 0이 되는 경우를 세어주면 됩니다.

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        
        for(int i = 0; i < number.length; i++){
            for(int j = i + 1; j < number.length; j++){
                for(int k = j + 1; k < number.length; k++){
                    if(number[i] + number[j] + number[k] == 0){
                        answer += 1;
                    }
                }
            }
        }
        
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=java 

Python으로 푼 문제를 Java로 다시 작성한 문제입니다.
풀이방법과 주의사항, Python 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/185

기본적인 구현은 비슷하지만 정답 체크를 달리했습니다.

Python과 달리 Java는 배열에 값을 추가하기가 곤란하기 때문에 ArrayList LinkedList 같은 자료구조를 추가로 써야하는데, 귀찮기 때문에... 

answer1과 answer2로 정답 후보 두개를 관리해줬습니다.

새로운 값이 answer1보다 크거나 같다면 answer1을 answer2로, 새로운 값을 answer1로 넣어주면 됩니다.

(두 값이 같아도 갱신해줘야 합니다! 예를 들어 기존 후보가 4와 3이고 새로운 값이 4일때도 answer1을 2로 밀어줘야 4와 4로 16이라는 올바른 값을 return할 수 있습니다.) 

answer1보단 작지만 answer2보다 크다면 새로운 값을 answer2로 넣어주면 됩니다.

초기값을 -1로 넣어줬으므로, answer1 * answer2가 0보다 작다면 둘 중 하나가 -1이라는 소리고 사이클이 하나뿐이라는 얘기니 0을 return합니다. 아니라면 후보가 두개 이상이었다는 소리니 answer1 * answer2fmf return하면 됩니다.

class Solution {
    public int solution(int[] cards) {
        int answer1 = -1;
        int answer2 = -1;
        
        for(int i = 0; i < cards.length; i++){
            if(cards[i] == 0)
                continue;
            
            int box = cards[i] - 1;
            int nbox = -1;
            int count = 1;
            cards[i] = 0;
            
            while(true){
                if(cards[box] == 0){
                    if(count >= answer1){
                        answer2 = answer1;
                        answer1 = count;
                    }else if(count > answer2){
                        answer2 = count;
                    }
                    break;
                }
                
                nbox = cards[box] - 1;
                count ++;
                cards[box] = 0;
                box = nbox;
            }
            
        }
        
        if(answer1 * answer2 < 0){
            return 0;
        }
        
        return answer1 * answer2;
    }
}

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

입력 사이즈가 작아서 대충 돌려도 되지만... 약수의 특징을 사용하면 조금 더 효율적인 코드를 짤 수 있습니다.

N의 제곱근을 기준으로 작은 약수와 큰 약수로 나누어 두개를 동시에 찾으면 됩니다.

예를 들어 100의 약수를 찾을때, 100의 제곱근은 10입니다.

10보다 작은 100의 약수 1, 2, 4, 5는 각각 100, 50, 25, 20과 대응됩니다.

또 100의 제곱근인 10이 정수이므로 10도 포함할 수 있습니다. 이렇게 약수를 찾는 경우 N이 클 때는 어마어마한 시간차이가 나게 됩니다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int div = 1;
        while(div < Math.sqrt(n)){{
            if(n % div == 0){
                answer += div;
                answer += (n/div);
            }
            div += 1;
        }}
        if(div == Math.sqrt(n)){
            answer += div;
        }
        return answer;
    }
}