문제

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

A팀과 B팀의 배열이 주어진다. 이는 각 팀원이 내는 숫자를 나열해둔것이다.
근데 A팀의 순서는 B팀에게 공개되서 B팀은 이에 맞춰 순서를 변경하려한다.
이때 B팀이 얻을수 있는 최대 승점을 return하라

접근

문제를 보니 제한사항에 이렇게 적혀있다.

• A와 B의 길이는 같습니다.
• A와 B의 길이는 1 이상 100,000 이하입니다.
• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

여기서 주의깊게 봐야 했던건 A와 B의 길이이다.
길이가 10만이나 되니 무조건 전체탐색은 안되고 O(log N) 이하의 속도로 풀어야 했다.
모든 순열을 구해서 풀면 100,000!의 시간복잡도가 나오기 떄문이다 😭😭
그래서 어떻게 풀지 한참 고민하다가 그리디로 풀면 될것같다는 생각을 했는데

이유는 이렇다
지금 A와 B의 팀원이 숫자를 내는 순서를 나열해둔 배열이 있는데
B팀의 순서는 물론 A팀의 순서도 바뀔수 있다.
왜냐하면 결국에는 A와 B의 팀원이 1:1로 매칭되기 때문이다.
다시말해, 각 팀의 팀원은 1번을 초과해서 경기에 나갈수 없기 때문이다.

이제 탐색하는 방법이 중요한데 투포인터를 사용하면 간단하게 풀 수 있다.
위에서도 말했든 문제에서 원하는건 최대승점이기 때문에 A팀원의 순서도 얼마든지 변경될 수 있다.
이렇게 구현하기 위해선 A와 B를 정렬해야하는데 내림차순으로 정렬한다.
오름차순으로 정렬하면 for문을 추가로 돌려야 하기 때문이다.
만약 내림차순으로 정렬하면 O(N)의 시간복잡도로 풀이가 가능하다.

코드의 아래처럼 간단하다.

1. A를 1씩 늘리며 탐색한다
2. A < B라면 B의 인덱스와 점수를 1증가한다.

코드

function solution(A, B) {
  let answer = 0;
  let j = 0;
  A.sort((a, b) => b - a);
  B.sort((a, b) => b - a);

  for (let i = 0; i < A.length; i++) {
    if (A[i] < B[j]) {
      answer++;
      j++;
    }
  }
  return answer;
}