항해99 11/9(화) 알고리즘

약수의 개수와 덧셈

 

코딩테스트 연습 - 약수의 개수와 덧셈

class Solution {
    public int solution(int left, int right) {
        int answer = 0;

        for (int i = left; i <= right; i++) {
            int divCnt = 0;
            for(int k = 1; k <= i; k++){
                if(i % k == 0){
                    divCnt++;
                }
            }

            if(divCnt % 2 == 0){
                answer += i;
            }else{
                answer -= i;
            }
        }

        return answer;
    }
}

딱히 할 말이 없다. 쉬운 문제였다. 문제 이해가 더 어려웠다.

 

 

K번째수

코딩테스트 연습 - K번째수

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        List<Integer> resList = new ArrayList<>();

        for (int i = 0; i < commands.length; i++) {
            List<Integer> list = new ArrayList<>();
            // commands[i][0] : array의 자르기 시작점
            // commands[i][1] : array의 자르기 끝점
            // commands[i][2] : 잘리고 난 뒤 찾을 인덱스
            for (int k = commands[i][0] - 1; k < commands[i][1]; k++) {
                list.add(array[k]);
            }
            Collections.sort(list);
            int data = commands[i][2] - 1;
            resList.add(list.get(data));
        }

        int[] answer = resList.stream().mapToInt(i -> i).toArray();
        return answer;
    }
}

배열의 값을 for문에 잘 응용하는것이 중요한 문제였다. 프로그래머스가 가끔씩 지문에서 2번째와 2번 인덱스를 혼용하여 표현하는 경우가 있는데, 이 부분에서 IndexOutofBoundException이 발생 할 수 있으니 조심하자.

 

 

체육복

코딩테스트 연습 - 체육복

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        // 여벌의 체육복은 바로 앞뒤 사람에게밖에 빌려줄 수 없음
        Arrays.sort(lost);

        Set<Integer> lostSet = new HashSet<>();
        Set<Integer> reserveSet = new HashSet<>();
        for (int i = 0; i < lost.length; i++) {
            lostSet.add(lost[i]);
        }
        for (int i = 0; i < reserve.length; i++) {
            reserveSet.add(reserve[i]);
        }

        for (int i = 0; i < lost.length; i++) {
            if (reserveSet.contains(lost[i])) {
                // 여벌의 체육복을 가진 학생이 잃어버렸을 경우
                reserveSet.remove(lost[i]);
                lostSet.remove((lost[i]));
            }
        }
        for (int i = 0; i < lost.length; i++) {
            if (reserveSet.contains(lost[i] - 1)) {
                // 앞번호 친구한테 빌려오기
                reserveSet.remove(lost[i] - 1);
                lostSet.remove(lost[i]);
            } else if (reserveSet.contains(lost[i] + 1)) {
                // 뒷번호 친구한테 빌려오기
                reserveSet.remove(lost[i] + 1);
                lostSet.remove(lost[i]);
            }
        }

        int answer = n - lostSet.size();
        return answer;
    }
}

빠르게 풀어보려는 목적으로 속도나 효율성은 고려하지 않고 그냥 손 가는대로 풀어본 문제다. 문제의 의도상 HashSet을 사용하는게 바람직할 것 같아서 사용했더니 푸는데 오래 걸리지는 않았다. 문제는 효율성도 고려하지 않았고 코드도 너무 반복된다.

아래는 내가 사용한 HashSet을 단 한 번만 사용해서 활용한 사례이다. 보다 간소하고 나은 것 같다.

 

import java.util.HashSet;
class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer=n-lost.length;
        HashSet<Integer> ko = new HashSet<Integer>();
        for(int k : reserve) {
            ko.add(k);
        }
        for(int i =0;i<lost.length;i++) {
            if(ko.contains(lost[i])) {
                //System.out.println("내껀내가입지");
                answer++;
                ko.remove(lost[i]);
                lost[i]=-1;
            }
        }


        for(int i =0;i<lost.length;i++) {
            //System.out.println(i);

            if(ko.contains(lost[i]-1)) {
                //System.out.println("있다");
                answer++;
                ko.remove(lost[i]-1);
            }else if(ko.contains(lost[i]+1)) {
                //System.out.println("있다");
                answer++;
                ko.remove(lost[i]+1);
            }
            //System.out.println("없다");
        }


        return answer;
    }
}

주석 열심히 달아놓은걸 보니 이 사람도 나처럼 에러 많이 났나보다. 

 

 

다트 게임

코딩테스트 연습 - [1차] 다트 게임

public int solution(String dartResult) {
        // 다트게임은 총 3회
        // 얻을 수 있는 점수는 0 ~ 10
        // S, D, T 영역이 존재하고 각 1제곱, 2제곱, 3제곱 점수 획득
        // 스타상* : 당첨시 지금 얻은 점수와 바로전에 얻은 점수를 두 배로
        // 아차상# : 당첨시 지금 얻은 점수가 마이너스
        // 스타상이 처음 나올 경우 지금 얻은 점수만 두 배로
        // 스타상 다음 스타상이 다시 나오면 4배로 획득
        // 아차상 바로 다음에 스타상이 나오면 점수를 두 배로 마이너스
        // 점수마다 SDT는 각 하나씩만 존재가능. 무조건 있음.
        // 점수마다 *#는 각 하나씩만 존재가능. 없을수도 있음

        int recent_score = 0;
        int current_score = 0;
        int total_score = 0;

        char[] result = dartResult.toCharArray();

        System.out.println("    R  C  T");
        for (int i = 0; i < result.length; i++) {
            // 0 ~ 10 사이의 정수일 경우
            if (result[i] >= '0' && result[i] <= '9') {
                // current_score 교체
                current_score = result[i] - '0';

                // 1이면 10인지 한 번 검사
                if (result[i] == '1') {
                    if (result[i + 1] == '0') {
                        current_score = 10;
                        i++;
                    }
                }
            }

            // S, D, T중 하나일 경우
            // S일경우 X, D일경우 current_score*2, T일경우 current_score*3

            switch (result[i]) {
                case 'D':
                    current_score = (int)Math.pow(current_score, 2);
                    break;
                case 'T':
                    current_score = (int)Math.pow(current_score, 3);
                    break;
            }

            // 만약 배열의 끝이거나 뒤에 *이나 # 없을시 total_score에 반영
            // 및 current_score를 recent_score로 이동시키고 current_score를 0으로
            if(result[i] == 'S' || result[i] == 'D' || result[i] == 'T'){
                if((i != result.length-1 &&
                        (result[i+1] != '*' && result[i+1] != '#')) ||
                        i == result.length-1){
                    total_score += current_score;
                    recent_score = current_score;
                    current_score = 0;
                }
            }

            // *이나 #일 경우
            // *일 경우 current_score 및 recent_score의 값 만큼을 total_score에 반영
            // #일 경우 current_score * -1
            switch(result[i]){
                case '*':
                    current_score *= 2;
                    total_score += current_score + recent_score;
                    recent_score = current_score;
                    break;
                case '#':
                    current_score *= -1;
                    total_score += current_score;
                    recent_score = current_score;
                    break;
            }
            System.out.print(result[i] + " : " + recent_score + ", " + current_score + ", ");
            System.out.println(total_score);
        }

        return total_score;
    }

푸는데 30분? 1시간 정도 걸린 것 같다. 문제를 잘 읽어가면서 하니 생각보다 잘 풀렸다. 풀고보니 코드도 나름 효율적으로 잘 나온 것 같다. 이번 코드는 꽤 만족스럽다. 반복을 줄이고 싶지만 이 정도는 참아줄 수 있을 것 같다.

문제의 조건이 다소 복잡해서 어렵게 느껴졌었는데, 문제 조건을 하나하나 따져보며 주석으로 먼저 큰 틀을 만든 뒤 조건에 따른 변수들을 하나씩 만들어가며 푸니 풀고보니 어렵지 않았다. 신기하다.