Programmers
[프로그래머스 Level.3] 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) (Java)
Devtraces
2023. 4. 20. 17:05
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/118668
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2022 KAKAO TECH INTERNSHIP > 코딩 테스트 공부
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.
알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.
문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.
예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다.
- A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다.
- B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다.
풀 수 없는 문제를 해결하기 위해서는 알고력과 코딩력을 높여야 합니다. 알고력과 코딩력을 높이기 위한 다음과 같은 방법들이 있습니다.
- 알고력을 높이기 위해 알고리즘 공부를 합니다. 알고력 1을 높이기 위해서 1의 시간이 필요합니다.
- 코딩력을 높이기 위해 코딩 공부를 합니다. 코딩력 1을 높이기 위해서 1의 시간이 필요합니다.
- 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높입니다. 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있습니다.
- 문제를 하나 푸는 데는 문제가 요구하는 시간이 필요하며 같은 문제를 여러 번 푸는 것이 가능합니다.
당신은 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 구하려 합니다.
초기의 알고력과 코딩력을 담은 정수 alp와 cop, 문제의 정보를 담은 2차원 정수 배열 problems가 매개변수로 주어졌을 때, 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간을 return 하도록 solution 함수를 작성해주세요.
모든 문제들을 1번 이상씩 풀 필요는 없습니다. 입출력 예 설명을 참고해주세요.
제한사항
- 초기의 알고력을 나타내는 alp와 초기의 코딩력을 나타내는 cop가 입력으로 주어집니다.
- 0 ≤ alp,cop ≤ 150
- 1 ≤ problems의 길이 ≤ 100
- problems의 원소는 [alp_req, cop_req, alp_rwd, cop_rwd, cost]의 형태로 이루어져 있습니다.
- alp_req는 문제를 푸는데 필요한 알고력입니다.
- 0 ≤ alp_req ≤ 150
- cop_req는 문제를 푸는데 필요한 코딩력입니다.
- 0 ≤ cop_req ≤ 150
- alp_rwd는 문제를 풀었을 때 증가하는 알고력입니다.
- 0 ≤ alp_rwd ≤ 30
- cop_rwd는 문제를 풀었을 때 증가하는 코딩력입니다.
- 0 ≤ cop_rwd ≤ 30
- cost는 문제를 푸는데 드는 시간입니다.
- 1 ≤ cost ≤ 100
정확성 테스트 케이스 제한사항
- 0 ≤ alp,cop ≤ 20
- 1 ≤ problems의 길이 ≤ 6
- 0 ≤ alp_req,cop_req ≤ 20
- 0 ≤ alp_rwd,cop_rwd ≤ 5
- 1 ≤ cost ≤ 10
효율성 테스트 케이스 제한사항
- 주어진 조건 외 추가 제한사항 없습니다.
입출력 예
| alp | cop | problems | result |
| 10 | 10 | [[10,15,2,1,2],[20,20,3,3,4]] | 15 |
| 0 | 0 | [[0,0,2,1,2],[4,5,3,1,2],[4,11,4,0,2],[10,4,0,4,2]] | 13 |
입출력 예 설명
입출력 예 #1
- 코딩력 5를 늘립니다. 알고력 10, 코딩력 15가 되며 시간이 5만큼 소요됩니다.
- 1번 문제를 5번 풉니다. 알고력 20, 코딩력 20이 되며 시간이 10만큼 소요됩니다. 15의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.
입출력 예 #2
- 1번 문제를 2번 풉니다. 알고력 4, 코딩력 2가 되며 시간이 4만큼 소요됩니다.
- 코딩력 3을 늘립니다. 알고력 4, 코딩력 5가 되며 시간이 3만큼 소요됩니다.
- 2번 문제를 2번 풉니다. 알고력 10, 코딩력 7이 되며 시간이 4만큼 소요됩니다.
- 4번 문제를 1번 풉니다. 알고력 10, 코딩력 11이 되며 시간이 2만큼 소요됩니다. 13의 시간을 소요하여 모든 문제를 풀 수 있는 알고력과 코딩력을 가질 수 있습니다.
제한시간 안내
- 정확성 테스트 : 10초
- 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수
나의 코드
import java.util.*;
class Solution {
public int solution(int alp, int cop, int[][] problems) {
int answer = 0;
int alpResult = 0; // 알고목표치
int copResult = 0; // 코딩목표치
// 알고목표치와 코딩목표치 구하기
for(int i=0; i<problems.length; i++) {
alpResult = Math.max(alpResult, problems[i][0]);
copResult = Math.max(copResult, problems[i][1]);
}
// 이미 초기값으로 모든 문제 풀 수 있으므로 반환
if(alpResult <= alp && copResult <= cop) return answer;
if(alp > alpResult) alp = alpResult; // 알고능력이 알고목표치를 넘기면 알고목표치로 세팅
if(cop > copResult) cop = copResult; // 코딩능력이 코딩목표치를 넘기면 코딩목표치로 세팅
int[][] dp = new int[alpResult + 2][copResult + 2];
for(int i=alp; i<=alpResult; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[alp][cop] = 0;
for(int i=alp; i<=alpResult; i++) {
for(int j=cop; j<=copResult; j++) {
dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j] + 1);
dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j] + 1);
// 알고능력 or 코딩능력이 목표치를 넘겼을 경우 목표치로 세팅 (최종적으로 dp[알고목표치][코딩목표치]로 반환하기 위해서)
for(int[] prob : problems) {
// 문제를 풀 수 있을 때
if(i >= prob[0] && j >= prob[1]) {
// 알고능력, 코딩능력 둘 다 목표치 이하일 경우
if(i + prob[2] <= alpResult && j + prob[3] <= copResult) {
dp[i + prob[2]][j + prob[3]] = Math.min(dp[i + prob[2]][j + prob[3]], dp[i][j] + prob[4]);
}
// 알고능력은 목표치 초과, 코딩능력은 목표치 이하일 경우
else if(i + prob[2] > alpResult && j + prob[3] <= copResult) {
dp[alpResult][j + prob[3]] = Math.min(dp[alpResult][j + prob[3]], dp[i][j] + prob[4]);
}
// 알고능력은 목표치 이하, 코딩능력은 목표치 초과했을 경우
else if(i + prob[2] <= alpResult && j + prob[3] > copResult) {
dp[i + prob[2]][copResult] = Math.min(dp[i + prob[2]][copResult], dp[i][j] + prob[4]);
}
// 알고능력, 코딩능력 둘다 목표치 초과했을 경우
else if(i + prob[2] > alpResult && j + prob[3] > copResult) {
dp[alpResult][copResult] = Math.min(dp[alpResult][copResult], dp[i][j] + prob[4]);
}
}
}
}
}
answer = dp[alpResult][copResult];
return answer;
}
}
풀이
- 해당 문제는 dp를 이용하여 풀어야 효율성 검사에 통과 할 수 있다.
- 우선 알고목표치 alpResult와 코딩목표치 copResult를 선언하고 problems를 순회하면서 문제에서 요구하는 알고능력의 최대치를 alpResult에 저장하고 문제에서 요구하는 코딩능력의 최대치를 copResult에 저장한다. (모든 문제를 풀 수 있어야 하므로 각각의 알고목표치와 코딩목표치만큼 알고능력과 코딩능력을 길러야 한다)
- 처음에 주어진 알고능력 alp와 코딩능력 cop가 각각 알고목표치 alpResult와 코딩목표치 copResult보다 크다면 이미 모든 문제를 풀 수 있는 것이므로 0을 반환한다.
- 이제 dp를 이용하기 위해 이차원 배열 dp를 행을 alpResult+2 길이로 열을 copResult+2 길이로 생성하고 2차원 for문을 돌면서 행이 alp부터 alpResult까지 열이 cop부터 copResult까지 모두 dp의 값을 int형 최대값으로 초기화한다.
- 초기 알고능력, 코딩능력인 dp[alp][cop]부터 시작하여 최종적으로 알고목표치와 코딩목표치인 dp[alpResult][copResult]를 구할 것이다
- dp[alp][cop]는 처음 초기값이므로 0으로 초기화한다.
- 이제 이중 for문을 돌면서 첫번째 for문에서 alp부터 alpResult까지 두 번째 for문에서 cop부터 copResult까지 돌면서 dp를 업데이트 한다.
- 우선 이중 for문 안에서 알고능력을 1 높이는 dp[i+1][j]를 dp[i+1][j]의 값과 dp[i][j]에서 1의 시간을 추가한 dp[i][j] + 1과 비교하여 최솟값으로 저장하고 코딩능력을 1 높이는 dp[i][j+1]도 마찬가지로 dp[i][j+1]의 값과 dp[i][j]에서 1의 시간을 추가한 dp[i][j] + 1과 비교하여 최솟값으로 저장한다.
- 그리고 이제 문제를 풀수있는지 확인하기 위해서 이중 for문 안에서 for문을 하나 더 추가하여 삼중 for문을 만든다.
- 세 번째 for문에서는 problems를 순회하면서 i(알고능력)가 problems[k][0] 이상이고 j(코딩능력)가 problems[k][1] 이상이라면 문제를 풀 수 있는 것이므로 문제를 풀 수 있다면 해당 보상 알고능력과 보상 코딩능력을 증가시켜 주면 되는데 우리가 구할 것은 알고능력과 코딩능력의 딱 목표치를 구하는 것이므로 보상을 받은 능력치가 목표치를 초과하는 경우 해당 능력치를 목표치로 다시 세팅해주면 된다.
- 따라서 알고능력, 코딩능력 둘 다 목표치 이하일 경우와 알고능력은 목표치 초과, 코딩능력은 목표치 이하일 경우, 알고능력은 목표치 이하, 코딩능력은 목표치 초과했을 경우, 알고능력, 코딩능력 둘다 목표치 초과했을 경우 각 4가지 경우로 나누어 보상을 받아 목표치를 넘어간 능력을 목표치로 세팅하며 해당 dp에 문제를 푼 시간인 problems[k][4]를 더하면서 최솟값을 업데이트 해나가면 된다.
- 이렇게 최종적으로 dp를 업데이트 하여 최종적으로 알고목표치와 코딩목표치를 달성했을 때 최소 시간을 저장한 dp[alpResult][copResult]를 answer에 저장하고 반환한다.
참고 : https://taehoung0102.tistory.com/211