프로그래머스 Java - Lv. 1 [31~40]

6720·2023년 2월 21일
코딩테스트프로그래머스

CodingTest(프로그래머스)

목록 보기
26/28
post-thumbnail

👨‍🏫 이번 목표

프로그래머스 코딩테스트 Lv. 1 Java로 31부터 40까지 풀기 (최신순 정렬 기준)

📒 문제 풀이

깃허브 링크

31 직사각형 별찍기

문제 설명

이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다.별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요.

제한 조건

  • n과 m은 각각 1000 이하인 자연수입니다.

예시

입력

5 3

출력

*****
*****
*****

문제 접근

반복문으로 세로만큼 출력하게 하고, n만큼 repeat 시키면 될 듯.

코드

import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        for (int i = 0; i < b; i++) {
            System.out.println("*".repeat(a));
        }
    }
}

한줄평

다른 사람 코드에서는 sb가 호평을 받았는데 이거도 배워둬야 겠음.

import java.util.Scanner;
import java.util.stream.IntStream;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        StringBuilder sb = new StringBuilder();
        IntStream.range(0, a).forEach(s -> sb.append("*"));
        IntStream.range(0, b).forEach(s -> System.out.println(sb.toString()));
    }
}

32 소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

  • nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
  • nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

numsresult
[1,2,3,4]1
[1,2,7,6,4]4

문제 접근

에라토스테네스로 소수인지 아닌지 판별한 다음에 삼중 중첩 반복문으로 배열에서 3개를 더하면 될 듯.

코드

import java.util.*;

class Solution {
    public boolean[] primeArr;
    public int solution(int[] nums) {
        int answer = 0, sum;
        Arrays.sort(nums);
        primeArr = new boolean[nums[nums.length-1]+nums[nums.length-2]+nums[nums.length-3]+1];

        is_prime(primeArr.length);
        
        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++) {
                    sum = nums[i] + nums[j] + nums[k];
                    if (!primeArr[sum]) answer++;
                }
            }
        }

        return answer;
    }
    
    public void is_prime(int num) {
        if (num < 1) return;
        primeArr[0] = primeArr[1] = true;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (primeArr[i] == true) continue;
            for (int j = i * i; j < primeArr.length; j += i) {
                primeArr[j] = true;
            }
        }
    }
}

한줄평

삼중 이상의 중첩은 좋지 않은 코드라곤 하는데 이 경우에는 아예 피할 수는 없는 듯함.

33 예산

문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

  • d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
  • d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
  • budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

입출력 예

dbudgetresult
[1,3,2,5,4]93
[2,2,3,3]104

문제 접근

부서가 신청한 금액만큼을 모두 지원해 줘야 하며, 최대한 많은 부서에 지원이 가능해야 하므로, d를 오름차순 정렬한 뒤, 차감되는 만큼 result 카운팅과 budget 차감하면 될듯.

코드

import java.util.*;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        Arrays.sort(d);
        
        for (int i = 0; i < d.length; i++) {
            if (d[i] <= budget) {
                budget -= d[i];
                answer++;
            } else break;
        }
        return answer;
    }
}

한줄평

굿. 근데 내일부터 난이도가 높아지는 것 같다. 좀 무섭다.

34 [1차] 비밀지도

문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

  1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
  2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
  3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
  4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

http://t1.kakaocdn.net/welcome2018/secret8.png

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

  • 1 ≦ n ≦ 16
  • arr1, arr2는 길이 n인 정수 배열로 주어진다.
  • 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2 - 1을 만족한다. n

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

매개변수값
n5
arr1[9, 20, 28, 18, 11]
arr2[30, 1, 21, 17, 28]
출력["#####","# # #", "### #", "# ##", "#####"]
매개변수값
n6
arr1[46, 33, 33 ,22, 31, 50]
arr2[27 ,56, 19, 14, 14, 10]
출력["######", "### #", "## ##", " #### ", " #####", "### # "]

문제 접근

10진수 값을 2진수로 바꾼다음에 만약 하나라도 1인 값이 있다면 그 자리는 #로, 아니면 공백으로 놓으면 될듯.

코드

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        String arr1Binary, arr2Binary, result;
        
        for (int i = 0; i < n; i++) {
            result = "";
            arr1Binary = String.format("%0" + n + "d", Long.parseLong(Long.toBinaryString(arr1[i])));
            arr2Binary = String.format("%0" + n + "d", Long.parseLong(Long.toBinaryString(arr2[i])));
            for (int j = 0; j < n; j++) {
                if (arr1Binary.charAt(j) == '1' || arr2Binary.charAt(j) == '1') result = result.concat("#");
                else result = result.concat(" ");
            }
            answer[i] = result;
        }
        return answer;
    }
}

속도는 굉장히 느림.

한줄평

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
      String[] answer = new String[n];
      String temp;

      for(int i = 0 ; i < n ; i++){
          temp = String.format("%16s", Integer.toBinaryString(arr1[i] | arr2[i]));
          temp = temp.substring(temp.length() - n);
          temp = temp.replaceAll("1", "#");
          temp = temp.replaceAll("0", " ");
          answer[i] = temp;
      }

      return answer;
  }
}

이 코드가 제일 괜찮은 거 같음.

처음에 16자리로 포맷한 다음에 앞쪽에 남는 자릿수는 잘라내기 → 0과 1은 비교 대신 바로 replaceAll로 바꿔치기

35 [1차] 다트 게임

문제 설명

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

  1. 다트 게임은 총 3번의 기회로 구성된다.
  2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
  3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수¹ , 점수² , 점수³)으로 계산된다.
  4. 옵션으로 스타상(*), 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
  5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
  6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
  7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
  8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
  9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

"점수|보너스|[옵션]"으로 이루어진 문자열 3세트.예) 1S2D*3T

  • 점수는 0에서 10 사이의 정수이다.
  • 보너스는 S, D, T 중 하나이다.
  • 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.

예) 37

입출력 예제

예제dartResultanswer설명
11S2D*3T371¹  2 + 2²  2 + 3³
21D2S#10S91² + 2¹ * (-1) + 10¹
31D2S0T31² + 2¹ + 0³
41S*2T*3S231¹  2 2 + 2³ * 2 + 3¹
51D#2S*3S51²  (-1) 2 + 2¹ * 2 + 3¹
61T2D3D#-41³ + 2² + 3² * (-1)
71D2S3T*591² + 2¹  2 + 3³  2

문제 접근

문자열이니 split으로 한글자씩 나눠서 그 글자가 SDT인지, *#인지, 숫자인지를 검사한 후에 그에 대응하는 식을 넣어주면 될듯.

코드

import java.util.*;
class Solution {
    public int solution(String dartResult) {
				// scoreArrIdx = 결과 저장할 배열 인덱스
				// lengthMinusOne = 위 인덱스에서 하나 뺀거
				// lengthMinusTwo = 위 인덱스에서 두개 뺀거
        int scoreArrIdx = 0, lengthMinusOne, lengthMinusTwo, answer = 0;
				// scoreArr = 결과 저장할 배열
        int[] scoreArr = new int[3];
				// dartResultArr = dartResult split한 배열
        String[] dartResultArr = dartResult.split("");
				// str = 반복문에서 dartResultArr[i]를 담당해줄 애
        String str = "";
        
        for (int i = 0; i < dartResultArr.length; i++) {
						// 변수 정리
            str = dartResultArr[i];
            lengthMinusOne = scoreArrIdx - 1;
            lengthMinusTwo = scoreArrIdx - 2;
            
						// 숫자가 나오면 scoreArr 배열에 바로 넣어주기
            if (str.matches("[0-9]")) {
                scoreArr[scoreArrIdx] = scoreArr[scoreArrIdx] * 10 + Integer.parseInt(str);
                continue;
            }

						// *나 #가 나오면 그에 따른 값 변화 적용하기
            if (str.equals("*")) {
                scoreArr[lengthMinusOne] = scoreArr[lengthMinusOne] * 2;
                if (scoreArrIdx == 1) continue;
                scoreArr[lengthMinusTwo] = scoreArr[lengthMinusTwo] * 2;
                continue;
            }
            else if (str.equals("#")) {
                scoreArr[lengthMinusOne] = scoreArr[lengthMinusOne] * -1;
                continue;
            }
            
						// S의 경우 1제곱이므로 패스
						// D나 T가 나오면 각각 2제곱, 3제곱
            if (str.equals("D")) scoreArr[scoreArrIdx] = (int)Math.pow(scoreArr[scoreArrIdx], 2);
            else if (str.equals("T")) scoreArr[scoreArrIdx] = (int)Math.pow(scoreArr[scoreArrIdx], 3);
            
						// 숫자나 *, #가 나오면 continue로 인해 접근할 수 없으므로
						// SDT가 나오면 이 부분을 거치도록 함. => SDT가 나오는 부분에 인덱스 이동
            scoreArrIdx++;
        }
        
				// 결과 합산
        for (int score : scoreArr) {
            answer += score;
        }
        
        return answer;
    }
}

한줄평

원래 반환값을 stream으로 처리하려고 했는데 거기서 너무 시간을 많이 잡아먹어서 그냥 반복문으로 해결함.

36 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participantcompletionreturn
["leo", "kiki", "eden"]["eden", "kiki"]"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]["josipa", "filipa", "marina", "nikola"]"vinko"
["mislav", "stanko", "mislav", "ana"]["stanko", "ana", "mislav"]"mislav"

문제 접근

두 배열을 정렬해서 순서마다 비교해주고 안 맞는 구간이 있으면 출력되도록 하면 될듯.

코드

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for (int i = 0; i < completion.length; i++) {
            if (!participant[i].equals(completion[i])) return participant[i];
        }
        return participant[participant.length-1];
    }
}

한줄평

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

동명이인으로 인해 getOrDefault를 사용함.

hm이 Arrays.sort보다 빠르므로 시간 복잡도를 고려하면 밑 방법으로 사용하면 됨.

37 K번째 수

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

  1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
  2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
  3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

  • array의 길이는 1 이상 100 이하입니다.
  • array의 각 원소는 1 이상 100 이하입니다.
  • commands의 길이는 1 이상 50 이하입니다.
  • commands의 각 원소는 길이가 3입니다.

입출력 예

arraycommandsreturn
[1, 5, 2, 6, 3, 7, 4][[2, 5, 3], [4, 4, 1], [1, 7, 3]][5, 6, 3]

문제 접근

문제에서 시키는대로 배열 자르고 정렬하고 k 값에 따라서 값 뽑아오면 될 듯.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for (int i = 0; i < commands.length; i++) {
            int[] subArr = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(subArr);
            answer[i] = subArr[commands[i][2]-1];
        }
        
        return answer;
    }
}

한줄평

이렇게 푸는게 맞나봐용

38 모의고사

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

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, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

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

입출력 예

answersreturn
[1,2,3,4,5][1]
[1,3,2,4,2][1,2,3]

문제 접근

학생들이 찍는 방식은 정해져 있으면서 문제 수에 따라 그만큼 반복할 것임.

이제 배열을 하나 만들어서 학생이 답을 맞출때마다 +1해서 가장 높은 점수를 가진 사람을 출력하도록 하면 됨.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] student1 = {1, 2, 3, 4, 5};
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int count1 = 0, count2 = 0, count3 = 0, ansInt, arrMax;
        int[] correct = new int[3];
        
        for (int i = 0; i < answers.length; i++) {
            if (count1 >= student1.length) count1 = 0;
            if (count2 >= student2.length) count2 = 0;
            if (count3 >= student3.length) count3 = 0;
            ansInt = answers[i];
            
            if (ansInt == student1[count1]) correct[0]++;
            if (ansInt == student2[count2]) correct[1]++;
            if (ansInt == student3[count3]) correct[2]++;
            
            count1++;
            count2++;
            count3++;
        }
        
        arrMax = Arrays.stream(correct).max().getAsInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (arrMax == correct[i]) list.add(i+1);
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

한줄평

stream()에서 시간을 다 잡아먹는다고 함

그리고 코드를 간추릴 수 있을 것 같아서 간추려봄.

import java.util.*;

class Solution {
    public int[] solution(int[] answers) {
        int[] student1 = {1, 2, 3, 4, 5};
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
        int ansInt, arrMax;
        int[] correct = new int[3];
        
        for (int i = 0; i < answers.length; i++) {
            ansInt = answers[i];
            if (ansInt == student1[i%student1.length]) correct[0]++;
            if (ansInt == student2[i%student2.length]) correct[1]++;
            if (ansInt == student3[i%student3.length]) correct[2]++;
        }
        
        arrMax = Math.max(correct[0], Math.max(correct[1], correct[2]));
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (arrMax == correct[i]) list.add(i+1);
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

1) 채점하는 반복문에서 length를 통해 배열 인덱스를 조정할 수 있으므로 count1, count2, count3과 관련된 코드 제거함

2) 최대값을 구하는 부분에서 stream() 사용을 제거하고 Math.max를 사용하도록 함. 학생이 3명밖에 없어서 가능한 일.

3) 리스트를 만든다음, 그 크기와 같은 배열을 만들어 값을 옮김. 여기서도 stream()은 제외시킴.

메모리 부분은 솔직히 장담 못하지만 속도 부부은 2~4배가량 빨라졌음.

39 체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

  • 전체 학생의 수는 2명 이상 30명 이하입니다.
  • 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
  • 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
  • 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

nlostreservereturn
5[2, 4][1, 3, 5]5
5[2, 4][3]4
3[3][1]2

문제 접근

우선 명심할 것은 여벌 체육복을 가지고 있는 학생도 도둑 맞았을 수 있다는 점.

그래서 처음에 배열 하나를 만들어서 체육복 수를 저장해둬야 할 듯.

그리고 앞 뒤로 조사해서 체육복이 있으면 빌려주도록 하면 될 듯.

1번 학생부터 가져오지 못했을 수 있으니 체육복을 빌려주는 원칙은 바로 위 번호가 아래 번호에게 빌려주는 것을 우선 구하고 다음에 아래 번호가 빌려주는 걸 계산하면 될 듯.

코드

class Solution {
    public int[] student;
    public int solution(int n, int[] lost, int[] reserve) {
        student = new int[n];
    
        for (int i = 0; i < lost.length; i++) { student[lost[i]-1]--; }
        for (int i = 0; i < reserve.length; i++) { student[reserve[i]-1]++; }
        
        for (int i = 0; i < n; i++) {
						student[i]++;
            if (student[i] != 0) continue;
            
            if (i != 0) borrowBottom(i);
            if (i != n - 1) borrowTop(i);
        }
        
        int answer = 0;
        for (int i = 0; i < n; i++) {
            if (student[i] != 0) answer++;
        }
        
        return answer;
    }
    
    public void borrowBottom(int idx) {
        if (student[idx-1] == 2 && student[idx] == 0) {
            student[idx]++;
            student[idx-1]--;
        }
        return;
    }
    
    public void borrowTop(int idx) {
        if (student[idx+1] == 2 && student[idx] == 0) {
            student[idx]++;
            student[idx+1]--;
        }
        return;
    }
}

중간에 에러 뜬게 있었는데 만약에 체육복 보유 상황이 2 0 2라고 할 때 2번 학생이 1번 학생에게 체육복을 빌렸다면 3번학생에게는 빌리지 못하도록 검사하는 구간이 필요했음.

그래서 borrowBottom과 borrowTop에 자신의 체육복이 0인 상태에서만 빌리도록 함.

한줄평

함수 나누는게 중독 됐나 싶다. 그래도 보기는 좋아보임.

40 실패율

문제 설명

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

  • 실패율은 다음과 같이 정의한다.
    • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

  • 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
  • stages의 길이는 1 이상 200,000 이하이다.
  • stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
    • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
    • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
  • 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
  • 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

Nstagesresult
5[2, 1, 2, 6, 2, 4, 3, 3][3,4,2,1,5]
4[4,4,4,4,4][4,1,2,3]

문제 접근

스테이지 인덱스와 함께 실패율을 담을 해시맵을 만들어서 정렬해주면 될듯.

코드

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        HashMap<Integer, Double> failureRate = new HashMap<>();
        int challengePlayer = 0, failurePlayer = 0, max = 0;

        for (int i = 0; i < N; i++) {
            challengePlayer = 0;
            failurePlayer = 0;
            for (int j = 0; j < stages.length; j++) {
                if (stages[j] < i + 1) continue;
                challengePlayer++;
                if (stages[j] == i + 1) failurePlayer++;
            }
            if (challengePlayer == 0) {
                failureRate.put(i+1, 0.0);
                continue;
            }
            failureRate.put(i+1, (double)failurePlayer/challengePlayer);
        }
        List<Integer> list = new ArrayList<>(failureRate.keySet());
        Collections.sort(list, (o1, o2) -> Double.compare( failureRate.get(o2), failureRate.get(o1) ) );
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

KeySet(): key 값만 반환함.

한줄평

대신 저걸로 하면 시간이 너무 느리게 나옴.

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        double[] failureRate = new double[N];
        int challengePlayer = 0, failurePlayer = 0, max = 0;

        for (int i = 0; i < N; i++) {
            challengePlayer = 0;
            failurePlayer = 0;
            for (int j = 0; j < stages.length; j++) {
                if (stages[j] < i + 1) continue;
                challengePlayer++;
                if (stages[j] == i + 1) failurePlayer++;
            }
            if (challengePlayer == 0) {
                failureRate[i] = 0.0;
                continue;
            }
            failureRate[i] = (double)failurePlayer/challengePlayer;
        }
                
        for (int i = 0; i < N; i++) {
            answer[i] = i+1;
        }

        int temp = 0;
        double tempDouble = 0.0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (failureRate[i] < failureRate[j] || (failureRate[i] == failureRate[j] && answer[i] > answer[j])) {
                    tempDouble = failureRate[i];
                    failureRate[i] = failureRate[j];
                    failureRate[j] = tempDouble;
                    
                    temp = answer[i];
                    answer[i] = answer[j];
                    answer[j] = temp;
                }
            }
        }
        return answer;
    }
}

그래서 속도가 그나마 줄어들도록 해봄.

굳이 해시맵 사용했다가 stream 사용하지 않도록 해시맵도 배열로 변경함.

✨ 후기

1) 이제 슬슬 어려워진다.

profile
6720
뭐라도 하자
이전 포스트

프로그래머스 SQL 고득점 Kit - SELECT

다음 포스트

프로그래머스 SQL 고득점 Kit - SUM, MAX, MIN

0개의 댓글