항해99 11/8(월) 알고리즘 - 고성범님 담당 분량

6. 없는 숫자 더하기

코딩테스트 연습 - 없는 숫자 더하기

class Solution {
    public int solution(int[] numbers) {
    	// 0~9중 없는 숫자를 더하기
        // 0~9까지의 합(45)에서 빼면 됨
        int answer = 45;
        for(int i = 0; i < numbers.length; i++)
            answer -= numbers[i];
        return answer;
    }
}

 

 

10.행렬의 덧셈

코딩테스트 연습 - 행렬의 덧셈

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
    	// 행렬에서 대응되는 자리의 수를 더하기
        // [2,3] + [3,4] -> [5, 7]
        int[][] answer = new int[arr1.length][arr1[0].length];
        for(int r = 0; r < answer.length; r++) {
            for(int c = 0; c < answer[0].length; c++)
                answer[r][c] = arr1[r][c] + arr2[r][c];
        }
        return answer;
    }
}

 

 

14. 나누어 떨어지는 숫자 배열

코딩테스트 연습 - 나누어 떨어지는 숫자 배열

import java.util.*;
class Solution {
    public int[] solution(int[] arr, int divisor) {
        int[] answer = {-1};
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] % divisor == 0) {
                pq.add(arr[i]);
            }
        }
        if(pq.size() == 0) {
            return answer;
        } else {
            answer = new int[pq.size()];
            int i = 0;
            while(!pq.isEmpty()) {
                answer[i] = pq.poll();
                i++;
            }
        }
        return answer;
    }
}

Arrays.sort 사용 후 return하면 끝나지만 시간복잡도를 고려해서 우선순위큐(순서가 존재하는 큐)를 사용하셨다고 한다.

arr를 스캔하여 나뉘는 값을 찾아서 정렬할 경우의 시간 복잡도
arr 스캔: O(n) 추출한 리스트를 array로 변환: O(n) 리턴값 정렬: O(nlogn)
시간 복잡도 결과: 2(O(n)) + O(nlogn)
우선순위큐를 이용할 경우의 시간 복잡도
arr 스캔하면서 우선순위큐에 삽입: O(nlogn) 추출한 값 array에 삽입: O(nlogn)
시간 복잡도 결과: 2(O(nlogn))
퀵정렬의 평균이 nlogn인걸 감안했을때 차이가 없는듯 하다.....

라고 하신다.

 

 

18. 서울에서 김서방 찾기

코딩테스트 연습 - 서울에서 김서방 찾기

class Solution {
    public String solution(String[] seoul) {
        String answer = "";
        for(int i = 0; i < seoul.length; i++) {
            if(seoul[i].equals("Kim"))
                return "김서방은 " + i + "에 있다";
        }
        return answer;
    }
}

Kim이 반드시 포함된 배열 속에서 Kim을 찾으면 된다고 한다. 심플하다.

 

 

22. 자릿수 더하기

코딩테스트 연습 - 자릿수 더하기

import java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        int divider = 10;
        int curVal = 0;
        if (n == 100000000)
            return 1;
        while(divider < 1000000000) {
            curVal = (n % divider);
            if(divider < 100)
                answer += curVal;
            else {
                int temp = curVal / (divider / 10);
                answer += temp;
            }
            divider *= 10;
        }
        return answer;
    }
}

 

 

26. 제일 작은 수 제거하기

코딩테스트 연습 - 제일 작은 수 제거하기

import java.util.*;
class Solution {
    public int[] solution(int[] arr) {
        if(arr.length == 1){
            arr[0] = -1;
            return arr;
        } else {
            int[] copy = Arrays.copyOf(arr, arr.length);
            Arrays.sort(copy);
            int min = copy[0];
            ArrayList<Integer> l = new ArrayList<Integer>();
            for(int i = 0; i < arr.length; i++) {
                if(arr[i] != min)
                    l.add(arr[i]);
            }
            int [] answer = new int[arr.length - 1];
            for(int j = 0; j < l.size(); j++) {
                answer[j] = l.get(j);
            }
            return answer;
        }
    }
}

배열에서 제일 작은수를 뺀 나머지를 반환해주면 되는 메소드이다. 만약 length가 1이면 -1을 반환해주도록 되어있다.

 

 

30. 최소 직사각형

코딩테스트 연습 - 최소직사각형

class Solution {
    public int solution(int[][] sizes) {
        int col = -1;
        int max = -1;
        
        for(int i = 0; i < sizes.length; i++) {
            for(int j = 0; j < sizes[0].length; j++) {
                if (sizes[i][j] > max) {
                    col = j;
                    max = sizes[i][j];
                }
            }
        }
        
        int otherCol = col == 0 ? 1 : 0;
        int otherMax = -1;
        
        for(int i = 0; i < sizes.length; i++) {
            if(sizes[i][col] < sizes[i][otherCol]) {
                int temp = sizes[i][col];
                sizes[i][col] = sizes[i][otherCol];
                sizes[i][otherCol] = temp;
            }
            if(sizes[i][otherCol] > otherMax)
                otherMax = sizes[i][otherCol];
        }
        
        return max * otherMax;
    }
}

모든 사각형이 들어갈 수 있는 가장 적합한 넓이의 사각형을 만드는 문제이다.

80, 10

20, 30

두 개의 사각형이 있으면, 아래의 사각형을 회전시켜서

80, 10

30, 20

의 꼴을 만들고 80*20의 사각형을 만들어 처리하면 된다.

문제가 심플하지만 생각할 필요가 있는 것 같다.

 

 

34. 모의고사

코딩테스트 연습 - 모의고사

import java.util.*;
class Solution {
    public int[] solution(int[] answers) {
        int[] answerss = {1,2,3};
        int[] numOfCor = {0,0,0};
        int i = 0;
        int num1Index = 0;
        int num2Index = 0;
        int num3Index = 0;
        int [] num1 = {1,2,3,4,5};
        int [] num2 = {2,1,2,3,2,4,2,5};
        int [] num3 = {3,3,1,1,2,2,4,4,5,5};
        while(i < answers.length) {
            int temp1 = i % num1.length;
            int temp2 = i % num2.length;
            int temp3 = i % num3.length;
            if(temp1 != 0) {
                if(answers[i] == num1[num1Index])
                    numOfCor[0]++;
            } else {
                num1Index = 0;
                if(answers[i] == num1[num1Index])
                    numOfCor[0]++;
            }
            if(temp2 != 0) {
                if(answers[i] == num2[num2Index])
                    numOfCor[1]++;
            } else {
                num2Index = 0;
                if(answers[i] == num2[num2Index])
                    numOfCor[1]++;
            }
            if(temp3 != 0) {
                if(answers[i] == num3[num3Index])
                    numOfCor[2]++;
            } else {
                num3Index = 0;
                if(answers[i] == num3[num3Index])
                    numOfCor[2]++;
            }
            i++;
            num1Index++;
            num2Index++;
            num3Index++;
        }
        int max = numOfCor[0];
        if (max > numOfCor[1] && max > numOfCor[2]) {int[] answer = {1};return answer;}           
        else if (max > numOfCor[1] && max == numOfCor[2]){int[] answer = {1, 3};return answer;}         
        else if (max == numOfCor[1] && max > numOfCor[2]){int[] answer = {1, 2};return answer;}         
        else if (max < numOfCor[1] && numOfCor[1] > numOfCor[2]){int[] answer = {2};return answer;}     
        else if (max < numOfCor[1] && numOfCor[1] == numOfCor[2]){int[] answer = {2, 3};return answer;}
        else if (numOfCor[2] > numOfCor[1] && max < numOfCor[2]){int[] answer = {3};return answer;}    
        else if (max == numOfCor[1] && max == numOfCor[2]){int[] answer = {1,2,3};return answer;}
        return answerss;
    }
}

수포자 주제에 찍어서 맞췄을때 등수가 높길 바라는 파렴치한 함수이다. 모든 경우의수를 구해서 계산해줬다.

 

import java.util.*;

class Solution {
    public static int[] solution(int[] answers) {
        int[][] patterns = {
                {1, 2, 3, 4, 5},
                {2, 1, 2, 3, 2, 4, 2, 5},
                {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}
        };

        int[] hit = new int[3];
        for(int i = 0; i < hit.length; i++) {
            for(int j = 0; j < answers.length; j++) {
                if(patterns[i][j % patterns[i].length] == answers[j]) hit[i]++;
            }
        }

        int max = Math.max(hit[0], Math.max(hit[1], hit[2]));
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < hit.length; i++)
            if(max == hit[i]) list.add(i + 1);

        int[] answer = new int[list.size()];
        int cnt = 0;
        for(int num : list)
            answer[cnt++] = num;
        return answer;
    }
}

이 코드는 간결하게 만든 코드라고 한다. 이런 코드를 짜는 사람이 되자.

 

 

38. 숫자문자열과 영단어

코딩테스트 연습 - 숫자 문자열과 영단어

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        int len = s.length();
        String[] digits = {"0","1","2","3","4","5","6","7","8","9"};
        String[] alphabets = {"zero","one","two","three","four","five","six","seven","eight","nine"};

        for(int i=0; i<10; i++){
            s = s.replaceAll(alphabets[i],digits[i]);
        }

        return Integer.parseInt(s);
    }
}

one2three4five6seven8nine0 형식으로 나오는 문자를

1234567890으로 바꿔주면 되는 문제이다.

replaceAll 기능을 알고 있다면 순식간에 풀 수 있지만, 모른다면 꽤 많은 고민을 거쳐야 할 것이다.

 

import java.util.*;

class Solution {
    public int solution(String s) {
        
        StringBuilder answer = new StringBuilder();
        HashSet<String> nums = new HashSet<String>();
        
        for(int i = 0; i < 10; i++)
            nums.add(String.valueOf(i));
        
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < s.length(); j++) {
            sb.append(s.charAt(j));
            if(sb.toString().length() == 1) {
                if(nums.contains(sb.toString())) {
                    answer.append(sb.toString());
                    sb.delete(0, 1);      
                }
            } else if (sb.toString().length() == 3) {
                if(sb.toString().equals("two")){
                    answer.append(2);
                    sb.delete(0, 3);
                } else if(sb.toString().equals("six")) {
                    answer.append(6);
                    sb.delete(0, 3);
                } else if(sb.toString().equals("one")) {
                    answer.append(1);
                    sb.delete(0, 3);
                }
            } else if (sb.toString().length() == 4) {
                if(sb.toString().equals("four")) {
                    answer.append(4);
                    sb.delete(0, 4);
                } else if(sb.toString().equals("nine")) {
                    answer.append(9);
                    sb.delete(0, 4);
                } else if(sb.toString().equals("zero")) {
                    answer.append(0);
                    sb.delete(0, 4);
                } else if(sb.toString().equals("five")) {
                    answer.append(5);
                    sb.delete(0, 4);
                }
            }  else if (sb.toString().length() == 5) {
                if(sb.toString().equals("three")){
                    answer.append(3);
                    sb.delete(0, 5);
                } else if(sb.toString().equals("eight")) {
                    answer.append(8);
                    sb.delete(0, 5);
                } else if(sb.toString().equals("seven")) {
                    answer.append(7);
                    sb.delete(0, 5);
                }
            }
        }
        return Integer.parseInt(answer.toString());
    }
}

이렇게 말이다.