안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.
이번 포스팅은 프로그래머스 - 양궁대회 자바 풀이를 작성하고자 합니다.
문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/92342
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
1. 풀이 소스
class Solution {
int[] lion; // 라이언 점수
int[] answer; // 정답을 복사할 배열
int max = -1; // 최대값
public int[] solution(int n, int[] info) {
lion = new int[11];
answer = new int[11];
dfs(0, n, info);
if (max == -1) return new int[]{-1}; // 경우의 수가 없는 경우 리턴
return answer;
}
private void dfs(int depth, int n, int[] apeach) {
if (depth == n) {
int score = calculate(apeach);
if (max <= score) { // 참고 #1
max = score; // 최대값 업데이트
answer = lion.clone(); // lion의 배열의 값을 복사, 참조로 할 경우 lion이 바뀌면서 값이 바뀜
}
return;
}
// lion[i] <= apeach[i] 조건 (apeach의 10점을 3번 맞췄다면, lion은 10점을 얻으려면 4번을 맞춰야함)
for (int i = 0; i < apeach.length && lion[i] <= apeach[i]; i++) {
lion[i] += 1; // 해당 인덱스에 1 증가 -> 다음 dfs에서도 1 증가할 수 있음 따라서 위의 조건까지 반복
dfs(depth + 1, n, apeach);
lion[i] -= 1; // 위에서 추가한 lion 배열에서 1을 감소하는 작업을 모든 dfs에서 수행하므로 원점 복구 가능
}
}
int calculate(int[] apeach) {
int apeachScore = 0;
int lionScore = 0;
for (int i = 0; i < lion.length; i++) {
if (apeach[i] == 0 && lion[i] == 0) continue;
if (apeach[i] >= lion[i]) apeachScore += (10 - i);
else lionScore += (10 - i);
}
if (apeachScore <= lionScore) return lionScore - apeachScore;
return -1;
}
/*
# 참고1
해당 로직에서 스코어가 같으면 가장 작은 점수를 더 많이 맞춘 배열을 체크하지 않고 업데이트 하는 이유
하단에 for문을 보면, i++로 상향식 반복문이 진행
따라서, 가장 최근에 업데이트 되는 score는 가장 적은 점수의 과녁을 더 많이 맞춘 배열
*/
}
2. 문제 풀이 과정
해당 문제는 dfs로 해결해야 하는 문제입니다. 처음 풀이하는 과정에, 더 큰 점수 차이를 기록한 배열들이 여러 개인 경우 어떻게 차이를 구분해야 하는가에 대한 고민을 하였습니다.
이 과정에서, 주석 처리한 참고1을 확인하면 해당 문제를 해결할 수 있습니다.
상향식으로 반복문을 돌다보면, i++로 인해 배열의 끝에 있는 i를 업데이트하게 됩니다.
만약 더 큰 점수차이가 여러 개이더라도 더 적은 과녁을 하나라도 더 맞힌 배열을 리턴하게 됩니다.
lion[i] += 1;
dfs()
lion[i] -= 1;
이 로직은, i 번째 과녁을 선택하지 않을 수 있습니다. 이 경우, 다음 인덱스로 넘겨주기 위해 재귀 성질을 이용하여 더한 만큼 다시 빼주면 원점으로 돌릴 수 있습니다.
자세한 풀이 과정은 마찬가지로 소스에 주석 처리하였습니다.
이상으로 프로그래머스 양궁대회 풀이를 마치겠습니다. 감사합니다.
'Algorithm' 카테고리의 다른 글
| [Algorithm] 프로그래머스 - 미로 탈출 명령어 자바 풀이 (0) | 2023.04.29 |
|---|---|
| [Algorithm] 프로그래머스 - 두 큐 합 같게 만들기 자바 풀이 (0) | 2023.04.29 |
| [Algorithm] 프로그래머스 - 파괴되지 않은 건물 자바 풀이 (0) | 2023.04.28 |
| [Algorithm] 프로그래머스 - 표 편집 자바 (0) | 2023.04.28 |
| [Algorithm] 프로그래머스 - 양과 늑대 자바 풀이 (0) | 2023.04.27 |
