다음날 있을 NHN 코딩테스트를 위해 알고리즘 문제를 열심히 풀었다. 물론 몇일 집중한다고 잘보진 않겠지만, 끝까지 해보는게 안하는 것보다 낫다고 생각했다.
자바 다중 배열도 익숙치 않기 때문에 이번 코테가 지나면 기초부터 탄탄히 풀어나가야겠다.
11:20 ~ 13:00
[프로그래머스] 큰 수 만들기 (그리디)
https://school.programmers.co.kr/learn/courses/30/lessons/42883
조건은 다음과 같습니다. 주어진 number가 있습니다. 해당 숫자에 k개의 수는 무조건 제거해야합니다. 제거한 수의 최대 조합를 구하면됩니다.
k개를 제거할때, 이전 숫자와 비교하면서 삭제하면 됩니다.
앞에서부터 비교해서 큰수를 살립니다. 만약에 비교했는데, 앞에보다 뒤에가 크다? 그러면 앞 숫자를 제거하고, 뒤에 숫자를 살리게 됩니다. 그러나 앞에 숫자보다 작다면 살려둡니다. 그리고 k만큼 제거하는 쿠폰이 있다고 생각하면서 지우면 생각하기 쉽습니다.
‘924’를 예시로 들자면, 1과 9 중 9가 커서 k=2 중 1개를 사용하여 1을 제거하고 9가 남습니다. 그다음엔 2인데 9보다 작으므로 살려둡니다. 그다음 숫자는 4가 오게되고 2보다 크므로 제거 쿠폰 1개를 사용하여 2를 제거하고 4를 살립니다. 결과적으로 ‘94’가 답으로 산출되게 됩니다.
만약, k=3으로 제거 쿠폰이 1개 남았다면 맨뒤에서부터 제거하면 됩니다. 94에서 4를 제거한 ‘9’가 답이 됩니다.
import java.util.*;
class Solution {
public String solution(String number, int k) {
// 결과를 담을 객체를 생성합니다.
StringBuilder sb = new StringBuilder();
// 입력된 숫자를 하나씩 순회한다.
for(char num : number.toCharArray()) {
// sb에 문자가 비어있지 않고, 제거할 k가 0이 아니고, sb마지막 문자가 현재 문자보다 작으면
// if문 쓰면 1회만 실행되므로 해당 사항이 충족할때까지 실행하기 위해 while 사용
while(sb.length() > 0 && k > 0 && sb.charAt(sb.length() -1) < num) {
// sb의 마지막 문자 제거
sb.deleteCharAt(sb.length() -1);
// 제거횟수 1회 차감
k--;
}
// 현재 문자를 sb에 추가 (수택의 push와 동일)
sb.append(num);
}
// k 수가 남았다면 맨뒤에서부터 k만큼 제거
if (k > 0) {
sb.setLength(sb.length()-k);
}
// 완성된 sb를 String으로 변환하여 반환
return sb.toString();
}
}13:00 ~ 14:00
지금까지 급하게 고득점 키트에 나와있는걸 했는데, 다시 기초로 들어가서 빠르게 입문 문제를 풀어보려고 합니다.
[프로그래머스] 짝수는 싫어요 (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120813
2로 나누어서 나머지가 0이면 짝수이고, n까지의 배열 중 짝수만 빼서 출력하면 됩니다.
두가지의 방식으로 풀어보았습니다.
- for문과 if문을 통해 홀수만 배열에 담기
class Solution {
public int[] solution(int n) {
// 홀수의 개수를 계산
int count = (n + 1) / 2;
// 홀수 개수만큼의 크기를 가진 배열을 생성
int[] answer = new int[count];
// 1부터 n까지의 숫자 중 검사하여 홀수만 answer 배열에 담기
int index = 0;
for(int i = 1; i <= n; i++) {
if(i % 2 != 0) {
answer[index] = i;
index++;
}
}
return answer;
}
}- 스트림 사용하기
import java.util.*;
import java.util.stream.*;
class Solution {
public int[] solution(int n) {
int[] answer = IntStream.rangeClosed(1, n).filter(value -> value % 2 !=0).toArray();
return answer;
}
}14:00 ~ 14:20
자바의 스트림에 대해서 정리해보았다. 오늘 개념 정리한 내용이 좀 많은데, 따로 포스팅해두겠다.
14:20 ~ 14:25
[프로그래머스] 나이출력 (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120820
굉장히 간단한 문제인데, 나이에 따른 출생년도를 계산하면 된다.
태어났을때 부터 1살이므로 [2022 - age + 1]을 하면 결과가 출력된다.
class Solution {
public int solution(int age) {
int answer = 0;
answer = 2022 - age + 1;
return answer;
}
}14:25 ~ 14:42
[프로그래머스] 피자 나눠 먹기 (1) (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120814
피자가 7조각이므로 인원수에서 7로 나누어서 몫에다가 나머지 발생시 +1만 해주면 됩니다. 그럼 나머지 발생시랑 아닐시 두가지 케이스를 나누면 구할 수 있습니다.
class Solution {
public int solution(int n) {
int answer = 0;
// 나머지가 없으면 몫 사용, 있으면 몫 + 1
if (n % 7 == 0) {
answer = n / 7;
}
else {
answer = (n / 7) + 1;
}
return answer;
}
}14:42 ~ 15:15
[프로그래머스] 피자 나눠 먹기 (2) (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120815
모두 같은 수의 피자 조각을 먹어야하므로 나머지가 나오면 +1을 함. 그리고 또 나머지가 나오면 +1을 합니다.
이렇게 0으로 나누어 떨어질때까지 계산하면 되지 않을까해서 다음과 같이 while문을 사용하여 작성하였습니다.
class Solution {
public int solution(int n) {
int pizza = 1;
while((6 * pizza) % n != 0) {
pizza++;
}
return pizza;
}
}해당 문제는 최소공배수(LCM) 알고리즘을 적용하면 더 쉽게 구할 수 있습니다. Gemini를 사용하여 확인해보면 다음과 같습니다.
class Solution {
// 최대공약수(GCD)를 구하는 함수
public int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
public int solution(int n) {
// n과 6의 최소공배수는 총 필요한 피자 조각 수
int lcm = (n * 6) / gcd(n, 6);
// 총 조각 수를 6으로 나누면 피자 판 수가 나옴
return lcm / 6;
}
}카뱅 정보보호 서탈 (16:00 ~ 16:40)
카카오뱅크 정보보호플랫폼 개발자 메일이 왔는데 서류 탈락했다.
아무래도 나의 포트폴리오나 경험이 보안쪽하고 거리가 멀어서 어려웠던 것 같다.
[프로그래머스] 피자 나눠 먹기 (3) (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120816
피자 조각 수는 slice이고 피자를 먹는 수는 n명입니다.
n명의 사람들이 최소 한 조각 이상 피자를 먹으려면 몇판 시켜야하는지 출력하면 됩니다.
두 가지 케이스입니다. slice 만큼 나누고 나머지가 0일때와 아닐때가 있고, 아니면 +1해서 답을 구합니다.
class Solution {
public int solution(int slice, int n) {
int answer = n / slice;
if(n % slice != 0) {
answer++;
}
return answer;
}
}16:40 ~ 17:20
[프로그래머스] 배열의 평균값 (입문)
https://school.programmers.co.kr/learn/courses/30/lessons/120817
numbers의 평균값을 구하는 문자입니다. numbers 배열 합에 numbers.length 만큼 나누면 됩니다.
여기서 주의할 점은 결과가 실수형이므로 나눌때 분모나 분자에 double 실수처리 해줘야합니다.
class Solution {
public double solution(int[] numbers) {
double answer = 0;
double sum = 0;
// 배열 합(향상된 for문)
for(int number:numbers) {
sum += number;
}
// 평균 구하기 (소수점까지 나올라면 분모나 분자에 double 처리)
answer = sum / numbers.length;
return answer;
}
}17:20 ~ 18:15
웹캡이 와서 NHN 코딩테스트를 시험환경처럼 만들고 사전 테스트를 진행했습니다. 프로그래머스는 생각보다 준비할 것도 많고 빡세네요…
18:15 ~ 19:00
이제 DP 한문제만 풀어보고 완전탐색, 이진탐색, 그리디 문항에 대해 복습해보겠습니다.
[프로그래머스] N으로 표현 (DP)
해당문제는 이해를 아직못했습니다. DP의 기초적인 문제를 풀어보고 되돌아와서 풀어봐야겠습니다.
number를 N과 사칙연산으로만 표현해야합니다.
그렇게 표현한 식들 중에 숫자 N을 제일 적게 쓴 케이스의 사용횟수를 구하면 됩니다.
예를 들어 N이 5이면 55던 5던 이어서 새로운 숫자 만들기도 가능합니다.
N의 사용 횟수를 늘려가면서, 각 횟수마다 만들 수 있는 모든 숫자 계산합니다. 점화식 유도하면 됩니다.
import java.util.*;
class Solution {
public int solution(int N, int number) {
// N과 number가 같으면 N을 한번만 사용하면 되므로 1 반환
if(N == number) {
return 1;
}
// 1. DP 테이블 초기화: List<Set<Integer>> 사용
// dp.get(i)는 N을 i+1번 사용해서 만들 수 있는 숫자들의 집합
List<Set<Integer>> dp = new ArrayList<>();
for(int i = 0; i < 9; i++) {
dp.add(new HashSet<>());
}
// 2. 초기값 설정: N을 1번 사용하면 만들 수 있는 수는 N뿐
dp.get(0).add(N);
// 3. 메인 반복문: N을 2번부터 8번까지 사용하는 경우를 계산
for(int i = 1; i < 8; i++) {
// N을 i+1번 이어 붙여서 만든 수 추가 (예: 5, 55, 555...)
// Integer.parseInt(String.valueOf(N).repeat(i + 1)) 와 동일
String repeatedN = "";
for(int k = 0; k <= i; k++) {
repeatedN += String.valueOf(N);
}
dp.get(i).add(Integer.parseInt(repeatedN));
// 3-2. 사칙연산 조합
// 예: i=3 (N 4번 사용) -> j=0,1,2
// j=0: (N 1번 사용) 연산 (N 3번 사용)
// j=1: (N 2번 사용) 연산 (N 2번 사용)
for(int j = 0; j< i; j++) {
// dp.get(j) : N을 j+1번 사용한 결과 집합
// dp.get(i-j-1) : N을 i-j번 사용한 결과 집합
for(int op1 : dp.get(j)) {
for(int op2 : dp.get(i - j -1)) {
dp.get(i).add(op1 + op2);
dp.get(i).add(op1 - op2);
dp.get(i).add(op1 * op2);
if(op2 != 0) {
dp.get(i).add(op1 /op2);
}
}
}
}
// 4. 정답 확인
// 이번 단계(N을 i+1번 사용)에서 만든 숫자들 중에 number가 있는지 확인
if(dp.get(i).contains(number)) {
return i + 1; // 사용횟수는 i+1
}
}
// 8번까지도 사용해도 못 찾은 경우
return -1;
}
}19:00 ~ 20:00
복습을 위해 다시풀어본 문제들입니다.
[프로그래머스] 최소직사각형 (완전탐색)
지갑을 가로던 세로던 상관없이 주어진 모든 명함이 들어갈 수 있는 지갑의 크기를 구하면 됩니다.
명함 배열을 오름차순 순서로 정렬한 다음에 [i][0]의 제일 큰 수와 [i][1]의 제일 큰 수를 구하고, 나온 두 값을 곱하면 됩니다.
import java.util.*;
class Solution {
public int solution(int[][] sizes) {
int answer = 0;
// Arrays.sort(sizes); // 내부 명함 배열도 정렬되는지? -> 안됨
// GPT사용: for문 사용해서 내부 명함 배열 정렬을 해야함
for(int[] card : sizes) {
Arrays.sort(card);
}
int max_h = 0;
int current_h = 0;
int max_w = 0;
int current_w = 0;
// 맨첨엔 i <= sizes.length라고 했는데 이러면 ArrayIndexOutOfBoundsException 오류가 나옵니다. 배열 길이는 4인데, 실제 배열은 0부터 시작해 3이 끝이기 때문입니다. 다음과 같이 작성해야합니다.
for(int i = 0; i < sizes.length; i++) {
current_h = sizes[i][0];
current_w = sizes[i][1];
// 현재 높이가 최대 높이보다 크면 갱신
if(current_h >= max_h) {
max_h = current_h;
}
// 현재 너비가 최대 너비보다 크면 갱신
if(current_w >= max_w) {
max_w = current_w;
}
}
return answer = max_h * max_w;
}
}21:00 ~ 22:11
[프로그래머스] 소수 찾기 (완전탐색)
먼저, 주어진 numbers로 만들 수 있는 모든 경우의 수를 구하면 됩니다.
여기서 루트값이 소수라면 소수입니다.
for문으로 17을 따로 나눕니다.
주어진 숫자에 대해 모든 조합을 구해봅니다.
0을 제외하고 모든 배열의 숫자를 왼쪽 첫번째부터 넣어봅니다.
별개의 경우로 본인 혼자인 경우도 고려해야합니다.
소수는 1과 자기자신밖에 나눠지지 않습니다.
위의 생각 흐름으로 전개했는데, 풀지를 못했다. 아직 List, Set에 대해 잘 사용하지 못해서 그런 것 같다.
import java.util.*;
class Solution {
public int solution(String numbers) {
// 만들 수 있는 모든 숫자 조합 찾기
Set<Integer> allNumbers = new HashSet<>();
generate("", numbers, allNumbers);
// 소수인 숫자의 개수 세기
int primeCount = 0;
for(int num : allNumbers) {
// 각 숫자가 소수인지 판별
if (isPrime(num)) {
primeCount++;
}
}
return primeCount;
}
// prefix: 현재까지 조합된 숫자 문자열
// remaining: 아직 사용하지 않은 숫자 문자열
// set: 만들어진 모든 숫자들을 중복 없이 저장할 set
void generate(String prefix, String remaining, Set<Integer> set) {
// 현재까지 조합된 prefix가 비어있지 않다면, 숫자로 바꿔서 set 추가
if (!prefix.isEmpty()) {
set.add(Integer.parseInt(prefix));
}
// 남아있는 숫자들을 하나씩 가져와서 prefix에 붙인다.
for(int i = 0; i < remaining.length(); i++) {
char currentChar = remaining.charAt(i);
// 다음 재귀 함수 호출
// - prefix에는 현재 문자를 붙여서 넘겨주고
// - remaining에서는 현재 문자를 제외하고 넘겨줌
generate(prefix + currentChar, remaining.substring(0, i) + remaining.substring(i + 1), set);
}
}
boolean isPrime(int num) {
if(num < 2) {
return false;
}
for(int i = 2; i <= (int)Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}
}21:11 ~ 23:50
[프로그래머스] 타겟 넘버 (DFS/BFS)
https://school.programmers.co.kr/learn/courses/30/lessons/43165
numbers에 더하고 빼서 target 숫자를 만드는 방법의 수를 리턴하면 됩니다.
dfs를 통해 첫번째 인덱스부터 더하거나 빼면서 모든 케이스를 생각합니다.
생각외로 1단계인데, 어렵습니다. dfs 함수자체가 익숙치 않아서 그런 것 같습니다. 나중에 다시 복습해야겠습니다.
class Solution {
int answer = 0;
int[] numbers;
int target;
public int solution(int[] numbers, int target) {
this.numbers = numbers;
this.target = target;
// DFS 시작
dfs(0, 0);
return answer;
}
public void dfs(int currentSum, int index) {
// 탈출 조건: 모든 숫자 사용시 (그전까지 재귀)
// 결국 모든 숫자가 사용된 시점에서부터 target과 수가 같으면 +1이 된다.
if(index == numbers.length) {
if(currentSum == target) {
answer++; // 타겟 넘버와 같으면 정답 개수 증가
}
return; // 함수 종료
}
// 재귀 호출: 다음 숫자를 더하거나 빼는 두 가지 경우를 모두 호출
// 현재 숫자를 더하는 경우
dfs(currentSum + numbers[index], index + 1);
// 현재 숫자를 빼는 경우
dfs(currentSum - numbers[index], index + 1);
}
}23:50 ~ 00:40
잠시동안 일부 개념에 대해서 정리했다. println 찍어서 디버깅하기, 자바의 List, Set 사용 등이 있는데 따로 포스팅하겠다.
00:40 ~ 02:00
[프로그래머스] K 번째 수 (정렬)
https://school.programmers.co.kr/learn/courses/30/lessons/42748
아이디어는 쉬운데, 코드 작성은 결코 간단하지 않습니다… 자력으로 풀다가 배열 자르기에 문제가 있었습니다.
commands에서 주어진 수만큼 자르고, 그 배열에서 특정 순서를 출력하면됩니다. 여기서 주의해야되는건 command의 배열이 1부터 시작한다는 가정이므로 인덱스 기반으로 바꾸기 위해 -1을 해줘야합니다.
import java.util.*;
class Solution {
public int[] solution(int[] array, int[][] commands) {
// 1. 최종 결과를 담을 배열 (commands의 개수만큼 결과가 나옴)
int[] answer = new int[commands.length];
// 2. commands 배열을 순회
for(int i = 0; i < commands.length; i++) {
int[] command = commands[i]; // 현재 명령어 [2, 5, 3]
// 4. 배열 자르기 (문제는 1기반, 배열은 0기반 인덱스이므로 조정)
int[] slicedArray = Arrays.copyOfRange(array, command[0] - 1, command[1]);
// 5. 자른 배열 정렬하기(오름차순으로 해야 정상적으로 출력)
Arrays.sort(slicedArray);
// 6. k번째 수 찾아서 정답 배열에 넣기
answer[i] = slicedArray[command[2] - 1];
}
return answer;
}
}내일을 위해 빨리 잠드는 것으로…
코딩은 머리가 맑아야 잘되는 것 같다.
