구현 ( 백트래킹 )
프로그래머스 2022 KAKAO BLIND RECRUITMENT Level 2 문제 양궁대회를 Java를 이용해 풀어보았다.
백트래킹을 이용해야 한다는 건 알았는데 코드로 작성하는 게 막상 어려웠던 문제였다.
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/92342
백트래킹 이용해 모든 가능한 조합 찾기
11개 점수가 존재하는 과녁을 1<=n<=10 만큼의 화살을 이용해 맞출 수 있는 조합을 모두 찾아내야 한다. 주어진 n개의 화살을 모두 쏘고 나면 입력으로 주어진 배열과 비교해가며 어피치와 라이언의 점수를 계산해준 후에 최대의 점수차를 갱신해줘야 한다.
이를 위해 우선적으로 해야할 것은 라이언이 맞출 수 있는 모든 조합들을 찾아나가야 한다. 이는 다음과 같이 구현할 수 있다.
void backTracking(int cnt,int idx, int n, int[] ap, int[] ry){
if(cnt==n){ // 라이언이 화살 다 쐈으면 점수 계산해주자
...
return;
}
for(int i=idx; i<11; i++){
ry[i]++;
backTracking(cnt+1, i, n, ap, ry);
ry[i]--;
}
}현재까지 쏜 화살의 개수 cnt를 1씩 증가시키고, 방금 추가해준 점수에 해당하는 idx를 parameter 로 넘겨주며 재귀를 돌다가 n발을 다 쏘면 필요한 작업들을 해주고 return하면 된다.
점수 계산하기
그럼 가능한 하나의 조합을 완성하고 나면 첫 번째 라인인 if(cnt==n)이 돌아갈 차례다. 어피치와 라이언의 점수를 계산해줄 차례인 것이다. 이 안의 코드를 살펴보자.
static int max = Integer.MIN_VALUE;
static ArrayList<int[]> list = new ArrayList<>();
void backTracking(int cnt,int idx, int n, int[] ap, int[] ry){
if(cnt==n){ // 라이언이 화살 다 쐈으면 점수 계산해주자
getScore(ap, ry);
if(ryanScore>appeachScore){ // 라이언이 이길 경우
int diff = ryanScore - appeachScore;
if(diff>max){ // 더 큰 점수차를 발견하면
max = diff;
list.clear(); // 기존의 조합들 다 날려
list.add(ry.clone());
}
else if(diff==max) list.add(ry.clone()); // 최대 점수차가 동일하면 하나 더 추가
}
return;
}
for(int i=idx; i<11; i++){
ry[i]++;
backTracking(cnt+1, i, n, ap, ry);
ry[i]--;
}
}getScore(ap, ry) 메소드는 둘의 점수판 배열을 넘겨줘서 각자의 점수를 계산하는 메소드다. 간단하다. 코드로 살펴보자.
void getScore(int[] ap, int[] ry){ // 둘의 결과를 넘겨주면 각각의 점수 계산
appeachScore = 0; ryanScore = 0;
for(int i=0; i<11; i++){
int appeach = ap[i];
int ryan = ry[i];
if(appeach==0 && ryan==0) continue;
if(ryan>appeach) // 라이언이 점수를 얻는 경우
ryanScore += (10-i);
else // 어피치가 점수를 얻는 경우
appeachScore += (10-i);
}
}둘의 점수 계산까지 다 끝났다. 그럼 이제 결과를 반환해줄 시간이다.
정렬
만약 list가 비어있다면 라이언이 이길 가능한 조합이 없다는 뜻이므로 문제에서 주어진 대로 {-1}을 반환하면 된다.
if(list.size()==0) return new int[]{-1}; // 가능한 결과 없을 때그렇지 않을 경우에는 다시 가장 낮은 점수를 더 많이 맞춘 조합을 찾아내서 반환해야 한다.
이는 Comparator를 사용해서 정렬 가능하다. 가장 낮은 점수부터 비교해서 내림차순으로 정렬해주면 된다.
코드로 표현하면 다음과 같다.
Collections.sort(list, (o1,o2) -> {
for(int i=10; i>=0; i--)
if(o1[i]!=o2[i]) return o2[i]-o1[i]; // 더 큰 놈이 앞에 오도록
return 0;
});
return list.get(0);문제를 풀기 전에는 너무나도 머리가 하얘졌는데 전체를 다 돌아봐야 하는 이런 재귀 문제가 특히 취약한 것 같다. 어쩌면 단순 무식하기에 더 간단할 수도 있는데 전수 조사 자체를 내가 좀 두려워 하는 것 같다. 더 많이 풀어봐야지...
오늘 배운 것
Comparator사용법을 익혀봤다.(o1,o2) -> { return o2 - o1; }이면 내림차순! 반대로 하면 오름차순
