🧩 양궁대회 - 문제 정보
- 문제: https://school.programmers.co.kr/learn/courses/30/lessons/92342
- 난이도: LV 2
- 유형: 완전 탐색, 구현
NewCodes의 풀이
- 스스로 풀었는가: O
- 다시 풀어볼 문제인가: O
- 풀이 시간: 65분
- 제출 횟수: 3회
- 선택 언어: Java
- 풀이 환경: 프로그래머스 내 IDE
📝 풀이 정보
요구 사항 정리
- 라이언은 어피치보다 k 점수에 더 많은 화살을 맞혀야 k 점수를 가져갈 수 있다.
- 라이언이 어피치를 이기기 위해서는 어피치보다 최종 점수가 더 커야만 한다.
- 가장 큰 점수차로 이길 수 있는 것 리턴한다.
- 라이언 우승 방법 여러 개라면, 가장 낮은 점수를 더 많이 맞힌 경우 리턴한다.
- 가장 낮은 점수에서 개수 같다면 그 다음 걸로 판단한다.
풀이 설계
: 설계에 21분을 소모했습니다.
가장 먼저, 정답을 찾기 위해서 라이언이 어떻게 화살을 쏴야 하는지 그 규칙을 발견했습니다. 만약 어피치가 1개라도 쏜 영역에서 라이언이 화살을 쏜다면, '해당 개수 + 1'만큼 쏴야 합니다.
즉, 라이언은 각 영역에 0개를 쏘거나 혹은 '어피치 화살 개수 + 1'만큼 쏴야 합니다.
따라서 dfs를 통해 위 규칙대로 할당하다가 최적의 해 후보가 나옴을 체크하면 된다고 생각했습니다. 가장 최적의 해를 구별하는 건 정확히 설계하진 못했습니다. 좋은 방법이 떠오르지 않았고, 우선 구현해 보기로 했습니다.
통과한 풀이 (실전 풀이)
: 시간 상 네이밍, 메서드 분리 등 클린하게 작성하기보다는 실전 상황에 맞게 풀이한 코드입니다. 해당 코드는 스킵하고 스크롤 내리셔서 바로 리팩토링한 코드를 보셔도 무방합니다.
import java.util.*;
class Solution {
private int maxScoreGap = 1;
private int[] maxLionInfo = {-1};
private int n;
private int[] info;
public int[] solution(int n, int[] info) {
this.n = n;
this.info = info;
int scoreGap = 0;
for (int i = 0; i < 11; i++) {
if (info[i] != 0) {
scoreGap -= 10 - i;
}
}
dfs(0, scoreGap, 10, new int[11]);
return maxLionInfo;
}
private void dfs(int usedArrows, int scoreGap, int k, int[] lion) {
if (usedArrows > n) {
return;
}
if (scoreGap >= maxScoreGap) {
int[] temp = lion.clone();
temp[10] += n - usedArrows;
if (scoreGap != maxScoreGap || maxLionInfo.length == 1) {
maxScoreGap = scoreGap;
maxLionInfo = temp;
}
for (int i = 10; i >= 0; i--) {
if (temp[i] > maxLionInfo[i]) {
maxLionInfo = temp;
break;
} else if (temp[i] < maxLionInfo[i]) {
break;
}
}
}
for (int i = k; i >= 0; i--) {
usedArrows += info[10 - i] + 1;
lion[10 - i] += info[10 - i] + 1;
// 어피치가 해당 점수에서 0개일 때는 i 한 번만 더해야 함을 유의하자!
if (info[10 - i] == 0) {
scoreGap += i;
} else {
scoreGap += i * 2;
}
dfs(usedArrows, scoreGap, i - 1, lion);
usedArrows -= info[10 - i] + 1;
lion[10 - i] -= info[10 - i] + 1;
if (info[10 - i] == 0) {
scoreGap -= i;
} else {
scoreGap -= i * 2;
}
}
}
}
해당 풀이에서 시행착오가 있었습니다. dfs 함수 내에서 dfs를 재귀적으로 호출할 때, i - 1이 아닌 k - 1을 대입해 버렸습니다. dfs 혹은 백트랙킹 유형을 풀 때 변수 헷갈리지 않도록 유의해야겠습니다.
리팩토링한 코드 (정돈된 풀이)
import java.util.*;
class Solution {
private int n;
private int[] apeachInfo;
private int maxScoreGap = 1;
private int[] optLionInfo = {-1};
public int[] solution(int n, int[] info) {
this.n = n;
this.apeachInfo = info;
int targetScore = 10;
int usedArrows = 0;
int[] lionInfo = new int[11];
int scoreGap = 0;
for (int i = 0; i < 11; i++) {
if (apeachInfo[i] != 0) {
scoreGap -= 10 - i;
}
}
dfs(targetScore, usedArrows, scoreGap, lionInfo);
return optLionInfo;
}
private void dfs(int targetScore, int usedArrows, int scoreGap, int[] lionInfo) {
checkOptimalSolution(scoreGap, usedArrows, lionInfo);
for (int i = targetScore; i >= 0; i--) {
if (usedArrows + apeachInfo[10 - i] + 1 > n) continue;
usedArrows += apeachInfo[10 - i] + 1;
lionInfo[10 - i] += apeachInfo[10 - i] + 1;
if (apeachInfo[10 - i] == 0) {
scoreGap += i;
} else {
scoreGap += i * 2;
}
dfs(i - 1, usedArrows, scoreGap, lionInfo);
usedArrows -= apeachInfo[10 - i] + 1;
lionInfo[10 - i] -= apeachInfo[10 - i] + 1;
if (apeachInfo[10 - i] == 0) {
scoreGap -= i;
} else {
scoreGap -= i * 2;
}
}
}
private void checkOptimalSolution(int scoreGap, int usedArrows, int[] lionInfo) {
if (scoreGap < maxScoreGap) return;
int[] temp = lionInfo.clone();
temp[10] += n - usedArrows;
if (isAbsoultelyOptimal(scoreGap, optLionInfo)) {
maxScoreGap = scoreGap;
optLionInfo = temp;
return;
}
for (int i = 10; i >= 0; i--) {
if (temp[i] > optLionInfo[i]) {
optLionInfo = temp;
break;
} else if (temp[i] < optLionInfo[i]) {
break;
}
}
}
private boolean isAbsoultelyOptimal(int scoreGap, int[] optLionInfo) {
if (scoreGap > maxScoreGap) {
return true;
}
if (optLionInfo.length == 1) {
return true;
}
return false;
}
}
: 리팩토링하는 데 21분 정도 걸렸네요. 주로 네이밍과 메서드 분리에 신경 썼습니다. 리팩토링하는 시간을 단축시키는 건 더 연습을 해봐야겠네요!
풀이 시행 착오
: 다 구현하고 나서 최종 제출을 했는데, 2개의 테스트 케이스가 틀렸습니다. 엣지 테스트 케이스가 있을 것임을 직감했고, 코드를 처음부터 다시 천천히 읽어보며 가장 취약할 것 같은 부분을 찾았습니다. 그 부분은 바로 '최적의 해를 판단'하는 부분이었습니다.
if (scoreGap >= maxScoreGap) {
maxLionInfo = lion.clone();
maxLionInfo[10] += n - usedArrows;
maxScoreGap = scoreGap;
}
백트랙킹 내에 if 문을 삽입하여 점수차가 가장 크면서도 백트랙킹에서 가장 마지막에 찾아진 해로 최적해를 구했습니다. 하지만, 이는 예외가 있습니다.
예를 들어, 라이언이 10점에 9개, 0점에 1개 쏴서 점수차가 10점으로 최적의 해로 저장되었다고 가정해 봅시다. 이후 5점에서 5개, 4점에서 4개, 0점에서 0개를 쏘게 된다면, 같은 10점 점수차이기에 maxLionInfo가 갱신됩니다. 하지만, 이는 문제 요구 사항에 의해 갱신되기 이전의 배열이 더 우선순위가 높기에 갱신했으면 안 됩니다.
그래서 최적해인지 판단하는 부분을 조금 더 꼼꼼하게 처리했습니다. 이는 checkOptimalSolution() 메서드를 참고하시면 되겠습니다.
풀이 의도 설명
: 위 풀이에서 포인트는 크게 두 가지입니다.
1. dfs 알고리즘을 사용하여 완전 탐색
: dfs 알고리즘을 사용하여 라이언이 각 영역에 화살을 쏠 수 있는 경우를 모두 탐색합니다. 각 영역에는 0개 혹은 '어피치 화살 개수 +1' 만큼 화살을 쏠 수 있으므로 각 영역에서의 경우의 수는 2가지입니다. 영역은 총 11개이므로 라이언이 화살을 쏠 수 있는 총경우의 수는 2^11(=2048)입니다. 따라서, 문제에서 주어진 시간 복잡도 10초 안에 충분히 실행될 수 있습니다.
2. 최적의 해 판단하는 로직
: checkOptimalSolution() 메서드를 통해 최적의 해를 판단합니다. 가장 우선적으로 고려해야 하는 건 '(라이언 총점수 - 어피치 총점수)가 이전보다 더 큰가?'입니다.
- 이전보다 더 크다면 바로 배열을 답의 후보로 할당해도 됩니다.
- 이전과 같다면 가장 낮은 점수 영역부터 순회하며 어떤 경우가 더 낮은 점수에 많은 화살을 맞혔는지 확인해야 합니다.
- 이전보다 작다면 답의 후보로 고려할 필요가 없습니다.
🎯 풀이 피드백
- 백트랙킹: 반복문 내에서 k가 아니라 i로 연산하기!! 변수 헷갈리지 말기!
- 테케 실패 시 태도: 복잡해질 때쯤 실전에서는 다른 문제로 넘어가자. 네부캠에서는 CS 문제로 넘어가도 되겠다!
- 배열 깊은 복사: 자바에서는 Arrays.copyOf(), clone()를 통해 배열을 깊은 복사할 수 있다.
- vscode단축키 익혀두자! 리팩토링 할 때 유용할 것!
'Computer Science > Algorithm' 카테고리의 다른 글
| 프로그래머스 이모티콘 할인행사 - 자세한 풀이(Java) (1) | 2024.06.07 |
|---|---|
| 프로그래머스 프렌즈4블록 - 자세한 풀이 (Java) (4) | 2024.05.30 |
| 프로그래머스 멀쩡한 사각형 - 자세한 풀이 (Java) (4) | 2024.05.29 |
| 백준 5430번 AC - 자세한 풀이(Java) (3) | 2024.05.24 |
| 백준 3190번 뱀 - 자세한 풀이 (Java) (6) | 2024.05.23 |
