코딩테스트를 대비하여 이번엔 프로그래머스에서 여러가지 문제를 풀어보았습니다.
12:30 ~ 13:45
[프로그래머스] 최소직사각형 (완전탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/86491
어제의 카페 문제와 비슷합니다. 명함의 가로, 세로 길이가 있고 회전할 수 있으며 주어진 모든 명함이 들어갈 수 있는 명함상자의 넓이를 구하면 됩니다.
각 카드의 max와 min 값을 구하고 각각의 max 값을 구하면 회전을 고려한 가로, 세로 길이를 구할 수 있습니다. 그렇게 나온 최대 가로, 세로를 곱하면 정답입니다.
import java.util.*;
class Solution {
public int solution(int[][] sizes) {
int max_w = 0;
int max_h = 0;
for (int[] card : sizes) {
int w = Math.max(card[0], card[1]);
int h = Math.min(card[0], card[1]);
max_w = Math.max(max_w, w);
max_h = Math.max(max_h, h);
}
return max_w * max_h;
}
}완전탐색에 맞게 풀면 다음과 같이 나타낼 수 있습니다.
class Solution {
int answer = Integer.MAX_VALUE;
public int solution(int[][] sizes) {
dfs(sizes, 0, 0, 0);
return answer;
}
private void dfs(int[][] sizes, int idx, int maxW, int maxH) {
if (idx == sizes.length) {
answer = Math.min(answer, maxW * maxH);
return;
}
int w = sizes[idx][0];
int h = sizes[idx][1];
// 1. 그대로 두는 경우
dfs(sizes, idx + 1, Math.max(maxW, w), Math.max(maxH, h));
// 2. 회전시키는 경우
dfs(sizes, idx + 1, Math.max(maxW, h), Math.max(maxH, w));
}
}13:45 ~ 14:40
42dot 과 스마일게이트의 이력서 내용을 작성하였습다. 미리 포폴과 이력서를 올려두었고, 42dot은 좀잇다가 지원동기를 작성해야겠습니다.
그리고 어제의 벨로그 내용을 올렸습니다.
14:40 ~ 16:10
실제 시험같이 맥북에서 플어보기로 했습니다.
[프로그래머스] 모의고사 (완전탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=java
3명의 인원이 주어진 패턴으로 계속해서 문제를 찍을 때, 정답 배열에 따라 최고 정답자를 구하면 됩니다. 여러명이 될 수도 있습니다.
인원에 대한 배열과 점수를 저장할 배열을 정하고, 각 인원에 대해 답과 비교하여 정답이면 +1을 해줍니다. 배열의 순환이 계속 반복되어야하므로 각 인원수의 원소 수만큼 i를 나눈 나머지의 원소와 비교해야합니다. 즉, p1의 인원의 i가 6이라면 원소 갯수 5를 나눈 나머지인 1이 나오고 p1[1]인 2와 비교를 하게 됩니다. 그래서 다음과 같은 answers[i] == p1[i % p1.length] 식이 나오게 됐습니다.
구해진 정답 갯수 중 Math.max를 통해 최대 점수를 구합니다. 그러나 자바에서는 2개의 값만 비교되어 중첩 호출로 최대 점수를 구합니다. 새 리스트를 만들어 scores[i] == maxScores 를 통해 최대 점수 받은 사람만 리스트에 +1 하여 입력합니다. (리스트값이 0부터 시작하므로)
리스트를 배열로 변환하여 정답을 출력합니다.
return result.stream().mapToInt(Integer::intValue).toArray();
변환하는 코드가 제일 어려운 것 같습니다.
import java.util.*;
class Solution {
public int[] solution(int[] answers) {
int[] p1 = {1, 2, 3, 4, 5};
int[] p2 = {2, 1, 2, 3, 2, 4, 2, 5};
int[] p3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
// 점수 저장할 배열
int[] scores = new int[3];
// 문제에 대한 답 비교
for (int i = 0; i < answers.length; i++) {
if (answers[i] == p1[i % p1.length]) scores[0]++;
if (answers[i] == p2[i % p2.length]) scores[1]++;
if (answers[i] == p3[i % p3.length]) scores[2]++;
}
// 중첩 호출로 최대 점수 구하기 (2개의 값씩만 비교)
int maxScore = Math.max(scores[0], Math.max(scores[1], scores[2]));
// 최대 점수 받은 사람만 결과 리스트에 추가(여러명일 수 있어 리스트 사용)
List<Integer> result = new ArrayList<>(); // <정수>를 담는 리스트
for (int i = 0; i < 3; i++) {
if(scores[i] == maxScore) {
result.add(i + 1); // 배열은 0 시작이어서 +1로 수포자 1로 바꿈
}
}
// 리스트를 배열로 변환
return result.stream().mapToInt(Integer::intValue).toArray();
}
}16:10 ~ 17:00
[프로그래머스] 소수 찾기 (완전탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/42839
이 문제는 많이 어렵습니다. 옛날에 에라토스테네스의 체라는 걸 사용해야합니다. 더군다나 파이썬으로 풀었던 걸 자바로 풀려니 난이도가 있습니다.
해당 문제는 입력된 숫자들의 조합들 중 소수의 갯수를 구하면 됩니다. 예를 들어 17이라면 7, 17, 71로 3입니다.
먼저, 모든 경웅의 수를 생성합니다. allcase라는 함수를 만들어서 순열로 모든 경우의 수를 재귀로 생성합니다. 앞자리가 0, 1, 7일 때의 두번째 자리를 모두 대입하며 구해지고 중복이 된다면 HashSet인 set에 의해서 제거됩니다.
만들어진 모든 케이스는 isPrime이라는 함수에 의해 0, 1을 제외하고 2부터 √n까지 나누어 떨어지면 소수가 아니고, 나누어 떨어지지 않는다면 소수입니다. 이는 에라토스테네스의 체인 원래 값의 루트를 씌운 값까지 나누어 떨어지지 않으면, 원래 값도 소수다 라는 이론을 적용한 결과입니다.
import java.util.*;
class Solution {
HashSet<Integer> set = new HashSet<>(); // 중복 제거
public int solution(String numbers) {
// 모든 경우의 수 생성
allcase("", numbers);
// 소수 개수 세기
int count = 0;
for(int num : set) {
if (isPrime(num)) count++;
}
return count;
}
// 순열로 모든 경우의 수 만들기
private void allcase(String prefix, String str) {
if(!prefix.isEmpty()) {
set.add(Integer.parseInt(prefix));
}
// i번째 문자를 선택하고 나머지로 재귀
for (int i = 0; i <str.length(); i++) {
allcase(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1));
}
}
// 소수 판별 함수
private boolean isPrime(int n) {
if(n == 0 || n == 1)
return false;
// 2부터 √n까지 나누어 떨어지면 소수가 아님 (여기선 제곱해서 구현)
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) return false;
}
return true;
}
}중간엔 식사와 운동, 휴식을 가졌습니다.
22:00 ~ 23:00
[프로그래머스] 카펫(완전탐색)
https://school.programmers.co.kr/learn/courses/30/lessons/42842
문제만 보면 처음엔 어떻게 풀어야하는지 몰랐습니다. 찾아보니 다음과 같습니다.
우선 중앙에 들어가는 카펫의 가로 세로 길이를 알아야합니다. 이는 주어진 노랑색 카펫의 약수와 같습니다. 예를 들어 6 같은 경우, (1, 6), (2,3), (3,2), (6, 1) 이 있습니다. 하지만, 중복이 되는 경우를 제외하여야 하므로 i <= Math.sqrt(yellow) 으로 중앙값까지 제한을 둡니다. for 반복문을 통해 노랑색 수를 나눌 수 있는 i가 구해지고, 높이가 되며 노랑색 수에 i를 나눈값은 너비가 됩니다.
이후에 카펫에 전체 가로, 세로 길이는 노랑의 가로 세로 길이에 각각 +2를 한 것과 같습니다. 왜냐하면 갈색이 노랑 주변을 감싸기 때문입니다. 이렇게 나온 카펫의 넓이는 갈색과 노랑 카펫의 총계랑 같아야합니다. carpetW * carpetH == brown + yellow 으로 같다면 그 너비와 높이가 답이 되므로 답 배열에 저장합니다.
import java.util.*;
class Solution {
public int[] solution(int brown, int yellow) {
int[] answer = new int[2]; // 가로, 세로값 정답이 들어갈 배열
// yellow의 가로, 세로 길이를 찾기 위한 반목문
for (int i = 1; i <= Math.sqrt(yellow); i++) {
if(yellow % i == 0) {
int yellowW = yellow / i;
int yellowH = i;
// 카펫 전체 가로, 세로 길이 계산
int carpetW = yellowW + 2;
int carpetH = yellowH + 2;
// 전체 넓이가 갈색과 노랑 카펫 수랑 같은지 확인
if (carpetW * carpetH == brown + yellow) {
answer[0] = carpetW; // 같으면 값 저장
answer[1] = carpetH;
break;
}
}
}
return answer;
}
}AM12:00 은 밤 00시다. (23:00 ~ 02:30)
42dot의 지원 동기를 작성하고 있었는데, 멍청한 행동을 해버렸습니다.
8월 21일 AM 12:00이라서 낮 12시인줄 알았는데, 알고보니 밤 00:00 였습니다. 다시금 생각해보니 20일까지인건데 왜 이제서야 생각이났는지...
아쉽지만, 다음 기회를 노리는걸로 하겠습니다.
