[Programmers Lv3, Java] 카운트 다운
프로그래머스 다트 협회에서는 매년마다 새로운 특수 룰으로 다트 대회를 개최합니다. 이번 대회의 룰은 "카운트 다운"으로 "제로원" 룰의 변형 룰입니다.
"카운트 다운"은 게임이 시작되면 무작위로 점수가 정해지고, 다트를 던지면서 점수를 깎아서 정확히 0점으로 만드는 게임입니다. 단, 남은 점수보다 큰 점수로 득점하면 버스트가 되며 실격 합니다.
다음 그림은 다트 과녁입니다.
다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있습니다. "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"과 "아우터 불"이 있는데 "카운트 다운" 게임에서는 구분 없이 50점을 얻습니다.
대회는 토너먼트로 진행되며 한 게임에는 두 선수가 참가하게 됩니다. 게임은 두 선수가 교대로 한 번씩 던지는 라운드 방식으로 진행됩니다. 가장 먼저 0점을 만든 선수가 승리하는데 만약 두 선수가 같은 라운드에 0점을 만들면 두 선수 중 "싱글" 또는 "불"을 더 많이 던진 선수가 승리하며 그마저도 같다면 선공인 선수가 승리합니다.
다트 실력에 자신 있던 종호는 이 대회에 출전하기로 하였습니다. 최소한의 다트로 0점을 만드는 게 가장 중요하고, 그러한 방법이 여러가지가 있다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 합니다.
목표 점수 target이 매개변수로 주어졌을 때 최선의 경우 던질 다트 수와 그 때의 "싱글" 또는 "불"을 맞춘 횟수(합)를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
https://school.programmers.co.kr/learn/courses/30/lessons/131129
내가 접근한 방법은
1. <점수, 배율> 테이블을 만든다. 이 때 3배율부터 테이블을 만들어서, 같은 점수를 낮은 배율로 만들 수 있다면 배율을 덮어쓰게 한다.
2. 불을 맞춘 횟수에 따라서 경우의수를 계산하여, 가장 적은 횟수, 가장 적은 불 싱글을 맞춘 회차를 선택한다.
예외사항 : 점수가 40이하이고, 점수 테이블에 포함되지 않은 점수인 경우 [2,2]를 반환한다.
이유 : Greedy한 위의 로직을 따를 경우, 20~40구간은 무조건 2배수+1배수 형태로 나오게 된다. 그러나, 20~40구간은 1배수+1배수 로도 표현이 가능한데 로직에 포함시키기 어려우므로 예외처리한다.
public int[] solution(int target) {
// 초기화
int[] scoreMultiply = new int[3]; // 1배, 2배, 3배
// 1. 점수 배열
HashMap<Integer, Integer> scoreMap = new HashMap<>(); // { score, multiply }
for(int multiply = 3 ; multiply > 0 ; multiply--) {
for(int score = 1 ; score <= 20 ; score++) {
scoreMap.put(score*multiply, multiply);
}
}
scoreMap.put(50, 1);
List<Integer> scores = new ArrayList<>(scoreMap.keySet());
scores.sort(Comparator.reverseOrder());
Integer[] scoresArray = scores.toArray(new Integer[0]);
// 목표 점수가 40이하이고, 한 번의 점수로 나타낼 수 없을 때, 1배수 점수 2개로 만드는 것이 제일 좋다.
if(target < 40 && !scores.contains(target)) return new int[]{2, 2};
// 목표 점수가 41 이상일 경우 일반적인 계산을 통해 구한다.
List<Integer> bestLog = new ArrayList<>();
int bullSingle = 0;
for(int bull = 0 ; bull <= target/50 ; bull++) { // 점수가 50보다 클 때, 불을 맞춘 경우와 맞추지 않은 경우를 비교
int remainScore = target - (bull * 50);
List<Integer> scoreLog = new ArrayList<>();
for(int logBullAdd = 0 ; logBullAdd < bull ; logBullAdd++) scoreLog.add(50);
int testBullSingle = bull;
while (remainScore > 0) {
for (int i = 0; i < scores.size(); ) {
int hitScore = scoresArray[i];
if (remainScore >= hitScore) { // 해당 점수를 맞춰도 오버되지 않는 경우
scoreLog.add(hitScore);
scoreMultiply[scoreMap.get(hitScore)-1] += 1;
remainScore -= hitScore;
if(scoreMap.get(hitScore) == 1) testBullSingle++;
} else i++;
}
}
if(bestLog.size() == 0 || bestLog.size() > scoreLog.size()){ // best가 지정되지 않았거나, best가 더 많은 다트를 사용했다면, 이번 회차를 선택
bestLog = scoreLog;
bullSingle = testBullSingle;
} else if (bestLog.size() == scoreLog.size() && testBullSingle >= bullSingle) { // 맞춘 다트수가 같으면, 불 싱글을 많이 맞춘 쪽 선택
bestLog = scoreLog;
bullSingle = testBullSingle;
}
}
return new int[]{bestLog.size(), bullSingle};
}
근데 너무 리스트랑 해시맵 같은 자료구조를 너무 덕지덕지 처바른것 같아서
리팩토링을 해봤다.
public int[] solution(int target) {
// 초기화
int[] multiplyMap = new int[60];
// 1. 점수 배열
List<Integer> scores = new ArrayList<>();
for (int multiply = 3; multiply > 0; multiply--) {
for (int score = 1; score <= 20; score++) {
multiplyMap[score * multiply - 1] = multiply;
scores.add(score*multiply);
}
}
multiplyMap[49] = 1;
// 목표 점수가 40이하이고, 한 번의 점수로 나타낼 수 없을 때, 1배수 점수 2개로 만드는 것이 제일 좋다.
if(target < 40 && !scores.contains(target)) return new int[]{2, 2}; // 다트는 21~39 구간에서 짝수가 아닌수가 해당된다.
scores.sort(Comparator.reverseOrder());
Integer[] scoresArray = scores.toArray(new Integer[0]);
int bestlog = Integer.MAX_VALUE;
int bestBullAndSingles = 0;
for(int b = 0 ; b <= target/50 ; b++) {
int remains = target - (b*50);
int log = b;
int bullAndSingles = b;
for(int score : scoresArray) {
if(remains >= score) {
log += remains/score;
if(multiplyMap[score-1] == 1) bullAndSingles += remains/score;
remains %= score;
}
}
if(bestlog > log || (bestlog == log && bullAndSingles > bestBullAndSingles)) {
bestlog = log;
bestBullAndSingles = bullAndSingles;
}
}
return new int[]{bestlog, bestBullAndSingles};
}대충 while로 일일히 비교했던걸 점수별로 나누기, 나머지 이용해서 진행하고,
배율에 대한것도 HashMap대신 점수가 60점이 최대라고 딱 정해져있으니 60크기의 array를 만들어서 약간 HashTable처럼 지정해줬다.
한 번에 이렇게 코드를 짤 수 있게 되고싶다.
2022/11/04 17:39 추가
랜덤으로 문제뽑아서 풀다가 이 문제가 다시나와서 아예 좀 새롭게 로직을 짜봤다.
public int[] solution(int target) {
int[] bestMulTried = new int[3];
int bestDarted = Integer.MAX_VALUE;
int bullCount = 0;
// 21~40구간의 소수는 1~20구간 2개의 합으로 나타낼 수 있으므로 무조건 [2, 2]가 반환되어야한다.
// 아래 로직에서는 높은 점수부터 차례로 비교하므로 위에서 예외처리한다.
if(20 < target && target <= 40 && target % 2 > 0 && target % 3 > 0) return new int[]{2, 2};
do{
int remainScore = target - (50*bullCount);
int[] mulTried = new int[3];
int darted = bullCount;
mulTried[0] = bullCount;
for(int score = 60 ; score > 0 ; score--) {
int mulInfo = (score <= 20) ? 1
: (score <= 40 && score % 2 == 0) ? 2
: (score % 3 == 0) ? 3 : 0;
if(mulInfo == 0) continue; // mulInfo가 0인경우 유효하지 않은 점수이므로 스킵
if(remainScore == 0) break; // 남은 점수가 0인경우 더 확인할 필요 없으므로 스킵
if(remainScore == 1){ // 1점이 남은 경우 1로 가속
mulInfo = 1;
score = 1;
}
if(remainScore >= score) {
int hited = remainScore / score;
remainScore %= score;
darted += hited;
mulTried[mulInfo-1] += hited;
}
}
if(bestDarted > darted || (bestDarted == darted && mulTried[0] > bestMulTried[0])) {
bestMulTried = mulTried;
bestDarted = darted;
}
}while(target / (50 * (++bullCount)) > 0);
return new int[]{bestDarted, bestMulTried[0]};
}