[프로그래머스 LV2] 양궁대회

 

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

 

문제요점

k점에 더 많은 화살을 맞힌사람이 k점을 가져감
맞힌 갯수가 같을 경우 어피치가 가져감
둘다 k점에 못 맞힌경우 아무도 가져가지 않는다
최종점수가 더 높은 선수가 우승자, 단 같을 경우 어피치가 우승자
라이언이 어피치를 가장 큰 점수 차이로 이기기 위해 n발을 어떤 과녁에 맞혀야하는지를 구하시오
라이언이 지거나 비기는 경우는 -1리턴

작은 차로 어피치를 이겨야함
어피치의 화살갯수가 작은 점수이고 점수가 높은 것 부터
최대 점수만 된다 그리디

 

 

주의점

array.push() 는 수정된 array의 길이를 반환한다

dfs에 넣기전에 new를 만들어준뒤 넣어주기

각 점수당 0개 ~ 10개가 꽃힐 수 있다.

0개를 선택했을때도 0넣어줘야함

 

로직

 

첫번째 풀이

function getSmallestIndex(arr) {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] !== 0) {
      return {
        index: i,
        count: arr[i],
      };
    }
  }
}

function solution(n, info) {
  var answer = [];

  function dfs(remainedCount, selected) {
    // console.log("--------", remainedCount, selected);
    // [탈출조건] 11개 점수의 화살 갯수를 다 선택했다
    if (selected.length === 11) {
      // 남은 화살이 없다
      if (!remainedCount) {
        // 어피치와 라이언의 점수를 비교
        let apeachScore = 0;
        let ryanScore = 0;

        // 어피치, 라이언의 총 점수 구하기
        for (let i = 0; i <= 10; i++) {
          const apeachCount = info[i];
          const ryanCount = selected[i];
          // 어피치 화살갯수 < 라이언의 화살갯수 라이언 득점
          if (apeachCount < ryanCount) {
            ryanScore += 11 - i;
          } else if (!apeachCount && !ryanCount) {
            continue;
          } else if (apeachCount >= ryanCount) {
            apeachScore += 11 - i;
          }
        }
        // 라이언의 점수가 높은 경우는 answer에 저장
        if (apeachScore < ryanScore) {
          answer.push({
            sum: ryanScore,
            arr: selected,
          });
        }
      }
      return;
    }

    // 0개 ~ 남은 갯수 만큼 선택가능
    for (let count = 0; count <= remainedCount; count++) {
      const newRemainedCount = remainedCount - count;
      const newSelected = [...selected];
      newSelected.push(count);
      dfs(newRemainedCount, newSelected);
    }
  }
  dfs(n, []);

  if (!answer.length) {
    return [-1];
  }
  const sorted = answer.sort((a, b) => b.sum - a.sum);
  const maxNum = sorted[0].sum;
  const maxNumArr = sorted.filter((s) => s.sum === maxNum);
  // console.log(maxNum, maxNumArr);
  // max가 1개만 있을때
  if (maxNumArr.length === 1) {
    return sorted[0].arr;
  } else {
    const sorted = maxNumArr.sort((a, b) => {
      if (a.index === b.index) {
        return b.count - a.count;
      } else {
        return (b.index = a.index);
      }
    });
    return sorted[0].arr;
  }
}

 

 

반타작했다ㅠ 왜일까

• [점수]가 최대가 아닌 [점수차이]가 맥스값이다
• 최대점수가 같을시 최소점수의 인덱스로 구별하고
• 최소점수의 인덱스가 같을시 그 인덱스의 화살의 갯수로 구별

 // 라이언의 점수가 높은 경우는 answer에 저장
if (apeachScore < ryanScore) {
  answer.push({
    sum: ryanScore - apeachScore, // !
    arr: selected,
  });
}

 

2번째 풀이

function getSmallestIndex(arr) {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] !== 0) {
      return {
        index: i,
        count: arr[i],
      };
    }
  }
}

function solution(n, info) {
  var answer = [];

  function dfs(remainedCount, selected) {
    // console.log("--------", remainedCount, selected);
    // [탈출조건] 11개 점수의 화살 갯수를 다 선택했다
    if (selected.length === 11) {
      // 남은 화살이 없다
      if (!remainedCount) {
        // 어피치와 라이언의 점수를 비교
        let apeachScore = 0;
        let ryanScore = 0;

        // 어피치, 라이언의 총 점수 구하기
        for (let i = 0; i <= 10; i++) {
          const apeachCount = info[i];
          const ryanCount = selected[i];
          // 어피치 화살갯수 < 라이언의 화살갯수 라이언 득점
          if (apeachCount < ryanCount) {
            ryanScore += 11 - i;
          } else if (!apeachCount && !ryanCount) {
            continue;
          } else if (apeachCount >= ryanCount) {
            apeachScore += 11 - i;
          }
        }
        // 라이언의 점수가 높은 경우는 answer에 저장
        if (apeachScore < ryanScore) {
          answer.push({
            sum: ryanScore - apeachScore,
            arr: selected,
          });
        }
      }
      return;
    }

    // 0개 ~ 남은 갯수 만큼 선택가능
    for (let count = 0; count <= remainedCount; count++) {
      const newRemainedCount = remainedCount - count;
      const newSelected = [...selected];
      newSelected.push(count);
      dfs(newRemainedCount, newSelected);
    }
  }
  dfs(n, []);

  if (!answer.length) {
    return [-1];
  }
  const sorted = answer.sort((a, b) => b.sum - a.sum);
  const maxNum = sorted[0].sum;
  const maxNumArr = sorted.filter((s) => s.sum === maxNum);
  // console.log(maxNum, maxNumArr);
  // max가 1개만 있을때
  if (maxNumArr.length === 1) {
    return sorted[0].arr;
  } else {
    const sorted = maxNumArr.sort((a, b) => {
        const aSmallestIndex = getSmallestIndex(a.arr);
        const bSmallestIndex = getSmallestIndex(b.arr);
        
        // 가장작은 인덱스가 같을 시에 그 인덱스의 갯수 오름차순
        if (aSmallestIndex === bSmallestIndex) {
        return b[aSmallestIndex] - a[aSmallestIndex];
        } else {
        return bSmallestIndex - aSmallestIndex;
        }
    });
    return sorted[0].arr;
  }
}

왜일까.. 다음날 다시 문제를 읽고 생각해보자..