1차 접근
처음에는 단순하게 B팀이 가능한 경우의 수를 dfs를 통해 모두 구해서 비교해보았지만, 시간 초과로 실패했다
예를 들어 [1,4,2,3] 이라는 배열이 있다면
[1,4,2,3]
[1,2,3,4]
[2,1,3,4]
[2,3,4,1]등등 가능한 경우의 수를 모두 찾아서 A팀의 순서와 비교해 보았지만 시간 초과로 실패했다
아마 [1,1,2,3] 같이 원소에 중복된 숫자가 들어있을 경우에
[1,1,2,3]
[1,1,2,3] 이렇게 두 경우를 모두 찾게 되는데, 일단 이런 중복값을 걸러줘야 할 것 같다
- 하지만 효율성 검사도 있었고, 뭔가 더 간단한 방법이 있을 것 같아 패스
두번째 접근
- 어떻게 보면 사실 순서는 중요하지 않다
A배열 , B배열의 순서보다는 A의 숫자에 대해 어떤 값을 낼지만 하나씩 짝을 맞추는 것에 초점을 맞추면 된다
[5,1,3,7] [8,2,6,6] 이나
[1,3,5,7] [2,6,6,8] 이나 동일뭔가 정렬을 하면 좀 편할 것 같다는 생각이 들어서, A와 B를 오름차순으로 정렬을 했다
[1,3,5,7]
[2,6,6,8]이렇게 정렬을 하고 보니 각 원소 인덱스마다 비교해서 이기는지 지는지 체크하면 끝 아닌가? 했지만
[2,6,7,9]
[3,5,7,8]각 원소마다 비교하면 1이 나오지만 정답은 2여야 한다
- 3번째 인덱스의 값이
7이어서 비기기 때문에 1점도 못 얻어가지만, 만약7을8이 상대할 경우 1점이라도 얻어갈 수 있다
그래서 결론은
- 어떤 경우던 간에 이길 거라면, 이길 수 있는 숫자 중에서 가장 작은 수로 이기는 게 이득이다
- A에게 지거나 비긴 경우에는, B의 다음 인덱스의 원소와 비교한다
- 두 배열의 포인터가 꼭 같은 곳을 가리킬 필요는 없다
- 투 포인터로 해결 가능하다는 의미
A [1,10,20,30]
B [1,2,3,11]이 경우 투 포인터를 이용하여
- 1과 1은 동일함 ->
B(포인터를 의미) ++ - 2가 1보다 큼 ->
A,B ++&&점수 ++ - 3은 10보다 작음 ->
B ++ - 11은 10보다 큼 ->
A,B ++&&점수 ++ - B가 길이를 벗어낫기 때문에 끝
