Java - 모의고사, 소수 만들기, 덧칠하기

Java

모의고사

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/42840
• 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하는 함수를 완성
• 학생의 문제의 답을 찍는 순서는 아래와 같음 
  • 학생1 - 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 ...
  • 학생2 - 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5 ...
  • 학생3 - 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 ...

제한조건

• 시험은 최대 10,000문제로 구성되어있으며 문제의 정답은 1, 2, 3, 4, 5 중 하나임
• 가장 높은 점수를 받은 사람이 여럿일 경우 return 하는 값을 오름차순 정렬

입출력 예시

나의 풀이

중복이 없고 자동 정렬해주는 TreeSet 이용

import java.util.Set;
import java.util.TreeSet;

class Solution {
    public Set<Integer> solution(int[] answers) {
      
        int[] pattern1 = {1,2,3,4,5};
        int[] pattern2 = {2,1,2,3,2,4,2,5};
        int[] pattern3 = {3,3,1,1,2,2,4,4,5,5};

        int score1 = 0;
        int score2 = 0;
        int score3 = 0;

        int j = 0;
        int k = 0;
        int l = 0;

        for (int i = 0; i < answers.length; i++) {

            if (j == pattern1.length) {
                j = 0;
            }
            if (k == pattern2.length) {
                k = 0;
            }
            if (l == pattern3.length) {
                l = 0;
            }

            if (answers[i] == pattern1[j++]) {
                score1++;
            }

            if (answers[i] == pattern2[k++]) {
                score2++;

            }
            if (answers[i] == pattern3[l++]) {
                score3++;

            }
        }
        Set<Integer> answer = new TreeSet<>();

        if (score1 >= score2) {
            if (score3 > score1) {
                answer.add(3);
            } else {
                answer.add(1);
            }
             
            if (score1 == score2) {
                answer.add(2);
            }

            if (score1 == score3) {
                answer.add(3);
            }

        } else {

            if (score2 > score3) {
                answer.add(2);

            } else {
                if (score2 == score3) {
                    answer.add(2);
                    answer.add(3);
                } else {
                    answer.add(3);
                }
            }
        }

        return answer;
    }
}

• 좋은 알고리즘으로 푸는 연습이 아직은 바로 떠오르지 않아서 원초적으로 문제를 접근하고 하나하나 해결하는 방식으로 밖에는 문제를 풀지 못하고 있다.
• 문저 문제를 찍는 학생 3명의 패턴을 각각 int 배열로 선언해주고, 정답인 answers 배열에서 값을 하나씩 꺼내기 위해 반복문을 사용했다.
• 그다음 각 학생 3명의 패턴이 정답을 맞춘 갯수를 저장하기 위한 변수 3개와 각 패턴에서 값을 꺼내기 위한 변수 3개를 선언해주고 answers의 값을 꺼낼때 마다 각 패턴에서 요소를 꺼내서 비교한 후 같다면 점수를 증가시킨다.
• 이때 각 패턴의 길이가 다르기 때문에, 패턴의 인덱스를 뜻하는 j, k, l의 변수가 각 패턴의 길이와 같아지면 index의 범위를 벗어나버리기 때문에 다시 0으로 초기화 해주어 0번 인덱스부터 다시 비교하도록 구성했다.
• 반복문이 끝나면 각 score1, score2, score3 변수에는 각 패턴이 얼마나 정답을 맞췄는지에 대한 값이 들어있는데 이제 이 값의 모든 경우의 수를 직접 비교했다.
• 먼저 정답을 담는 자료구조를 중복이 없고 오름차순으로 자동으로 정렬해주는 TreeSet으로 선언해주고 반환값을 Set으로 반환하도록 설정해주었다.
• 그다음 score1이 score2보다 크거나 같다면, socre3 > score1을 비교하여 가장 큰 값을 찾도록 했고 가장 큰 값이 찾아지면 score1과 score2가 같은지, score1과 score3이 같은지를 비교하여 동점인 경우에 정답에 값을 추가해주었다.
• 만약 score2가 score1보다 크다면 score2 > score3을 비교하여 score2가 크면 2를 추가해주고, 아닐 경우 score2 == socre3을 비교하여 같다면 2, 3을 추가해주고 여기서도 아니라면 3만 추가해주도록 하여 모든 경우의 수를 비교했다.
• 매우 원초적으로 풀었기 때문에 성능 자체는 좋을 수 있긴하지만 너무 코드가 길어지는 단점이 있어 이미 잘 작성된 메서드를 사용하면 가독성과 성능을 둘다 지킬 수 있을 것 같다

최적화

import java.util.Set;
import java.util.TreeSet;

class Solution {
    public Set<Integer> solution(int[] answers) {

        int[] pattern1 = {1, 2, 3, 4, 5};
        int[] pattern2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] pattern3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

        int score1 = 0, score2 = 0, score3 = 0;

        for (int i = 0; i < answers.length; i++) {

            if (answers[i] == pattern1[i % pattern1.length]) score1++;
            if (answers[i] == pattern2[i % pattern2.length]) score2++;
            if (answers[i] == pattern3[i % pattern3.length]) score3++;
        }
        int max = Math.max(score1, Math.max(score2, score3));
        Set<Integer> answer = new TreeSet<>();

        if (score1 == max) answer.add(1);
        if (score2 == max) answer.add(2);
        if (score3 == max) answer.add(3);

        return answer;
    }
}

• 각 패턴의 배열의 인덱스를 나타내는 j, k, l 변수를 제거하고 반복문 변수 i를 각 패턴의 길이로 나눈 나머지(i % 패턴의 길이)를 인덱스로 사용하면 불필요한 변수 선업 없이 더 간결한 코드로 구현할 수 있다.
• 성능만 고려한다면 인덱스 변수를 개별로 관리하는 방식이 조금 더 효율적일 수 있지만 가독성과 유지보수 성을 고려하면 지금처럼 % 연산을 활용하는 것이 더 적합할 것 같다.
• 심지어 요즘 컴퓨터는 속도가 매우 빨라서 이정도 속도차이는 큰 의미도 없을 것 같다.
• 추가적으로 이미 최적화가 잘 되어있는 Math.max메서드를 사용하면 내가 직접 모든 경우의 수를 if문으로 비교한것을 매우 간단하게 최대값을 찾을 수 있다.
• 해당 문제에서는 가장 정답을 많이 맞춘 패턴만 제공하면 되기 때문에 각 max함수를 통해 최대값을 알아내고, 각 변수가 최대값이면 1, 2, 3을 각각 추가하도록 하여 가독성도 좋고 성능도 챙길 수 있는 코드로 최적화를 할 수 있다.

다른 풀이

List 자료구조 활용 - 일반화된 구조, 수포자 수 증가 대응

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[patterns.length];
        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;
    }
}

• 우선 패턴을 2차원 배열로 선언하고, 각 패턴과 정답을 비교하여 정답을 맞춘 개수를 담는 배열 hit의 길이를 2차원 배열의 행의 길이로 선언하여 패턴이 증가되어도 자동으로 대응되도록 구성한다.
• 그 다음 2차원 배열을 통해서 각 패턴의 요소와 정답의 요소를 비교하여 정답의 개수를 hit의 각 요소에 저장한다.
• 이때 첫 번째 반복문 변수 i를 patterns의 행, hit의 인덱스로 사용하면서 각 패턴과 패턴의 점수가 서로 같은 인덱스를 사용할 수 있게 된다.
  • 즉 patterns[i]로 꺼낸 패턴으로 정답을 비교하여 hit[i]에 저장하기 때문에 patterns[0] 의 패턴의 정답은 hit[0]에 담기게 된다.
• 2중 반복이 끝내면 Math.max를 통해서 hit 배열의 요소를 모두 비교하여 최대 값을 찾아낸 후 hit의 각 요소와 비교하면서 최대값이라면 list.add(i + 1)를 통해서 각 패턴을 나타내는 값을 저장한다.
  • 여기서 하드코딩이 들어가 있는데 stream을 사용하면 배열 전체를 순회하여 최대값을 동적으로 구할 수 있다.
  • Arrays.stream(hit).max().getAsInt()
• 이후의 로직은 list을 int[]로 반환하기 위한 로직이다.

---

소수 만들기

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/12977
• 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때 nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하는 함수를 완성

제한조건

• nums에 들어있는 순자의 개수는 3개 이상 50개 이하임
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며 중복된 숫자는 들어있지 않음

입출력 예시

나의 풀이

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    boolean flag = true;

                    int sum = nums[i] + nums[j] + nums[k];
                    
                    for (int l = 2; l * l <= sum; l++) {
                        if (sum % l == 0) flag = false;
                    }
                    
                    if (flag) answer++;
                }
            }
        }
        return answer;
    }
}

• 먼저 배열에서 각각 다른 수를 3개씩 뽑아서 더해야 하기 때문에 3중 반복문을 사용했다.
• 처음 반복문 변수의 값은 배열의 첫 번째 인덱스부터 꺼내기 위해 0으로, 그 다음 반복문 변수의 값은 i + 1, 그 다음 반복문 변수의 값은 j + 1로 각각의 반복문 변수가 증가 되더라도 배열에서 서로 다른 조합이 되도록 이전 반복문 변수에 + 1을 해주었다.
• 그리고 각 반복문의 반복횟수를 정해주는 것이 중요한데, 증가된 값 만큼 nums의 길이에서 뺄셈 연산을 해주지 않으면 배열의 끝에서 인덱스 초과가 발생할 수 있다.
• 마지막 반복문에서 nums[i] + nums[j] + nums[k]로 배열의 각 요소를 꺼내 더한 후 이 값이 소수인지 판별하는 로직을 통해 소수이면 answer의 값을 1 증가시켜 문제를 해결했다.
• 소수를 판별할 때는 2부터 판별할 대상의 제곱근 까지 나눠 보면서 나누어 떨어지는지 확인해보고 나누어 떨어지는 수가 없다면 그 수는 소수라고 판단할 수 있다.
• 여기서 소수를 구하는 공식을 메서드화 하여 제공하면 조금더 가독성이 증가할 수 있으며 제곱근을 구할 때 Math.sqrt()를 사용해도 되지만 지금처럼 소수를 구하는 값을 제곱하는 것이 성능면에서는 더 좋다고 한다.

소수 구하는 공식을 메서드화

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {

                    int sum = nums[i] + nums[j] + nums[k];

                    if (validPrimeNumber(sum)) answer++;
                }
            }
        }
        return answer;
    }
    
    private boolean validPrimeNumber(int num) {
        if (num < 2) return false;
        
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

---

덧칠하기

문제

• 프로그래머스 - https://school.programmers.co.kr/learn/courses/30/lessons/161989
• 페인트가 칠해진 길이 n, 벽에 페인트를 칠하는 롤러의 길이 m, 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 주어질 때 롤러로 페인트칠 해야 하는 최소 횟수를 구하는 함수를 완성
  • 벽을 1미터 길이의 구역 n개로 나누고 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙여서 페인트를 다시 칠해야할 구역을 정함
  • 페인트는 롤러가 벽에서 벗어나면 안되며 구역의 일부분만 포함되도록 칠하면 안됨
  • 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며 이를 벽을 한번 칠했다고 정의함
  • 한 구역에 페인트를 여러번 칠해도 되고 다시 칠해야할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정하 ㄴ구역은 적어도 한 번 페인트칠을 해야 함

제한조건

• 1 <= m <= n <= 100,000
• 1 <= section의 길이 <= n
  • 1 <= section의 원소 <= n
  • section의 원소는 페인트를 다시 칠해야 하는 구역의 번호임
  • section에서 같은 원소가 두 번 이상 나타나지 않으며 원소는 오름차순으로 정렬 되어 있음

입출력 예시

 

다시 칠해야할 영역: 2, 3, 6

롤러의 길이: 4

벽의 길이: 8

페인트칠 2번만하면 벗겨진 벽이 모두 칠해짐

 

다시 칠해야할 영역: 1, 3

롤러의 길이: 4

벽의 길이: 5

페인트칠 1번만하면 벗겨진 벽이 모두 칠해짐

나의 풀이

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int painting = 0;
        for (int i = 0; i < section.length; i++) {
            
            int target = section[i];
            if (target < painting) {
                continue;
            }
            painting = target + m;
            answer++;       
        }   
        return answer;
    }
}

• 덧칠해야할 구역이 적혀있는 section배열에서 요소를 하나씩 꺼내야 하므로 반복문을 사용하여 꺼낸 요소를 덧칠해야할 시작 지점이라고하여 target 변수라고 지정했다.
• 다시 칠해야할 시작 지점인 painting 변수를 0으로 초기화 해두고 반복문을 거듭할 수록  target과 롤러의 길이를 더하여 다음 덧칠해야할 시작 지점을 누적 저장하고 덧칠한 횟수를 1 증가시킨다
• 이때 반복문에서 꺼낸 덧칠해야할 구역이 painting 변수의 값보다 작으면 이미 한번의 덧칠로 해당 지점을 지난 것이므로 continue를 사용하여 반복을 건너뛰고 다음 요소를 꺼낸다.
• 반복이 모두 끝난 후 덧칠한 횟수인 answer를 반환하여 문제를 해결했다
• 여기서 다시 칠해야할 시작 지점을 뜻하는 변수명을 painting보다 nextPaintingIndex, 시작 지점을 target보다 start라고하면 좀 더 명확할 것 같다

다른 풀이

class Solution {
    public int solution(int n, int m, int[] section) {
        int roller = section[0];
        int cnt = 1;
        for(int i = 1; i < section.length; i++) {
            if(roller + m - 1 < section[i]) {
                cnt++;
                roller = section[i];
            }
        }
        return cnt;
    }
}

• 아이디어는 내가 풀이한 방식과 비슷하지만 문제 해결 방식이 조금 다른것 같아서 가져왔다.
• 먼저 section[0]으로 칠할 시작점을 가져오고, 처음 롤러를 한번 칠한다.
• 그다음 벽에 덧칠한 구역이 남았다면 section의 다음 요소를 꺼내서 칠하도록 반복을 하는데, 이때 조건문을 통해 section에서 꺼낸 값보다 덧칠할 시작점(roller) + 롤러의 길이(m) - 1 의 값이 작아야 덧칠을 수행하여 횟수를 증가시키고 다음 덧칠할 시작점을 변경한다.
  • -1을 한 이유는 만약 덧칠해야할 시작 지점이 2이고 롤러의 길이가 4라면 2부터 4만큼 덧칠했으므로 2, 3, 4, 5 까지 덧칠하여 5까지 덧칠해졌으므로 덧칠한 구역을 뜻하기 위해선 -1을 해야한다.
  • -1을 하지 않으면 2 + 4 = 6이되어 덧칠한 구역이 아니라 덧칠해야할 시작지점이 되어 변수명을 헷갈리지 않게 해야한다.