문제 파악
A팀과 B팀이 각각 숫자를 하나씩 내서 대결한다.
- B의 숫자가 A의 숫자보다 크면 B팀이 1점을 얻는다.
- B의 숫자가 A의 숫자보다 작거나 같으면 점수를 얻지 못한다.
- 모든 팀원은 한 번씩 경기에 참여한다.
구해야 하는 것은 B팀이 얻을 수 있는 최대 승점이다.
처음 생각한 해결 방법
처음에는 이 문제을 보고 보드게임 다빈치 코드를 떠올렸다.
상대방이 어떤 숫자를 내는지에 따라 B의 숫자를 전략적으로 배치해서, 결국 B가 최대한 이길 수 있는 알고리즘을 만들어야 한다고 생각했다.
그래서 다음과 같은 전략을 떠올렸다.
이길 때는 근소한 차이로 이기고, 질 때는 큰 차이로 지자.
예를 들어 A가 3을 냈고 B에게 4와 10이 있다면, 10이 아니라 4를 내는 것이 좋다.
A: 3
B: 4 → 근소한 차이로 승리4만으로도 이길 수 있으므로, 더 큰 숫자인 10은 나중에 더 큰 숫자를 상대할 때 사용할 수 있다.
반대로 어차피 질 경기라면 작은 차이로 지는 것보다, 이기기 어려운 상대에게 가장 작은 숫자를 내서 크게 지는 것이 낫다고 생각했다.
이길 때는 최소한의 숫자를 사용하고,
질 때는 가장 약한 숫자를 희생한다.그런데 여기서 막혔다.
그래서 어떤 경기에서 이기고, 어떤 경기에서 져야 하지?
이길 때와 질 때의 전략은 생각했지만, 정작 현재 경기를 이겨야 하는지 포기해야 하는지를 결정하는 기준을 만들지 못했다.
문제를 다시 읽어보기
막혀서 문제를 다시 읽어보았다.
문제는 B가 모든 경기에서 이길 수 있는 전략을 구하라고 하지 않았다.
구해야 하는 것은 단순히 다음 값이었다.
B팀이 얻을 수 있는 최대 승점
즉, 각 경기에서 미리 이길지 질지를 정할 필요가 없었다.
A의 숫자를 하나씩 확인하면서, 현재 A를 이길 수 있는 B의 숫자가 있다면 그중 가장 작은 숫자를 사용하면 된다.
이길 수 없다면 해당 A는 넘어가면 된다.
이렇게 문제를 다시 해석하니 해결 방법이 단순해졌다.
해결 아이디어
A와 B를 모두 오름차순으로 정렬한다.
A = [1, 3, 5, 7]
B = [2, 2, 6, 8]그 후 A의 작은 숫자부터 확인하면서 다음 조건을 만족하는 B의 숫자를 찾는다.
현재 A의 숫자보다 큰 B의 숫자 중 가장 작은 숫자를 매칭한다.
A가 1인 경우
A: 1
B: 2B의 2가 A의 1보다 크므로 승리한다.
더 큰 6이나 8을 사용할 필요는 없다.
A가 3인 경우
다음 B의 숫자는 2이다.
A: 3
B: 22는 3을 이길 수 없다.
그리고 A는 오름차순으로 정렬되어 있다.
따라서 현재 A인 3도 이길 수 없는 2는 이후에 나올 5와 7도 이길 수 없다.
이 숫자는 앞으로도 사용할 수 없으므로 버리고, 다음 B의 숫자인 6을 확인한다.
A: 3
B: 66은 3보다 크므로 승리한다.
전체 진행 과정은 다음과 같다.
| A의 숫자 | 확인한 B의 숫자 | 결과 |
|---|---|---|
| 1 | 2 | B 승리 |
| 3 | 2 | 이길 수 없으므로 2를 버림 |
| 3 | 6 | B 승리 |
| 5 | 8 | B 승리 |
| 7 | 남은 숫자 없음 | 승리 불가능 |
따라서 B팀이 얻을 수 있는 최대 승점은 3점이다.
JavaScript 코드
function solution(A, B) {
// A와 B를 오름차순으로 정렬
A.sort((a, b) => a - b);
B.sort((a, b) => a - b);
// A = [1, 3, 5, 7]
// B = [2, 2, 6, 8]
let i = 0;
let count = 0;
for (const a of A) {
while (i < B.length) {
// 현재 B의 숫자가 A보다 크면 승리
if (a < B[i]) {
count += 1;
i += 1;
break;
}
// 현재 A도 이길 수 없는 B는 버린다.
i += 1;
}
}
return count;
}i는 현재 확인하고 있는 B의 인덱스이다.
현재 B의 숫자가 A보다 크다면 승점을 얻는다.
if (a < B[i]) {
count += 1;
i += 1;
break;
}승리한 B의 숫자는 이미 사용했으므로 i를 증가시킨다.
현재 A와 B의 매칭이 끝났으므로 break를 통해 다음 A를 확인한다.
반대로 B의 숫자가 A보다 작거나 같다면 승리할 수 없다.
i += 1;현재 A도 이길 수 없는 B의 숫자는 이후의 더 큰 A도 이길 수 없다.
따라서 해당 B의 숫자는 버리고 다음 숫자를 확인한다.
Python 코드
def solution(A, B):
# A와 B를 오름차순으로 정렬
A.sort()
B.sort()
# A = [1, 3, 5, 7]
# B = [2, 2, 6, 8]
count = 0
i = 0
for a in A:
while i < len(B):
# 현재 B의 숫자가 A보다 크면 승리
if a < B[i]:
count += 1
i += 1
break
# 현재 A도 이길 수 없는 B는 버린다.
i += 1
return countJavaScript 코드와 같은 방식으로 동작한다.
- A는
for문으로 앞에서부터 확인한다. - B는 인덱스
i를 사용해 앞에서부터 확인한다. - 현재 B가 A보다 크면 승점을 얻고 다음 A로 넘어간다.
- 현재 B가 A보다 작거나 같으면 해당 B를 버린다.
왜 시간복잡도가 안 터졌을까?
코드를 작성하면서 가장 걱정했던 부분은 이중 반복문이었다.
배열의 길이는 최대 100,000이다.
A의 모든 숫자마다 B 전체를 확인한다면 다음과 같은 연산 횟수가 발생한다.
100,000 × 100,000
= 10,000,000,000
= 100억 번100억 번의 연산은 시간 초과가 발생할 가능성이 크다.
그런데 작성한 코드는 for문 안에 while문이 있었다.
for a in A:
while i < len(B):처음에는 이 코드도 O(N²)일 것이라고 생각했다.
하지만 제출해 보니 시간 초과 없이 통과했다.
그 이유는 일반적인 이중 반복문과 달리 B의 인덱스 i가 매번 초기화되지 않기 때문이다.
i = 0
for a in A:
while i < len(B):
i += 1i는 코드가 시작할 때 한 번만 0으로 설정된다.
이후에는 계속 증가하기만 하며 이전 위치로 돌아가지 않는다.
예를 들어 첫 번째 A를 확인하면서 B를 2번 확인했다면, 다음 A에서는 세 번째 B부터 확인한다.
첫 번째 A에서 B를 2번 확인
두 번째 A에서 B를 1번 확인
세 번째 A에서 B를 1번 확인
네 번째 A에서 B를 0번 확인각 A를 확인할 때 while문이 여러 번 실행될 수는 있다.
하지만 모든 while문의 실행 횟수를 합치면 B의 길이를 넘을 수 없다.
2 + 1 + 1 + 0 = 4즉, B의 각 원소는 전체 과정에서 최대 한 번씩만 확인된다.
따라서 정렬 이후 탐색의 시간복잡도는 O(N)이다.
전체 시간복잡도는 다음과 같다.
A 정렬: O(N log N)
B 정렬: O(N log N)
A와 B 탐색: O(N)최종 시간복잡도는 정렬의 시간복잡도가 가장 크므로 다음과 같다.
O(N log N)이 풀이가 투 포인터인 이유
처음에는 단순히 for문과 while문을 이용한 풀이인 줄 알았다.
하지만 코드를 다시 살펴보면 두 배열에서 각각 현재 위치를 가리키고 있다.
for (const a of A)또는for a in A가 A의 위치를 이동시킨다.i가 B의 위치를 이동시킨다.
두 위치 모두 배열의 앞에서 뒤로만 이동한다.
또한 이미 확인한 원소로 다시 돌아가지 않는다.
따라서 이 풀이는 두 배열을 두 개의 위치로 탐색하는 투 포인터 알고리즘이다.
투 포인터라고 해서 반드시 두 개의 인덱스 변수를 직접 선언해야 하는 것은 아니다.
하나의 배열은 for문으로 순회하고, 다른 배열은 인덱스로 순회하는 방식도 투 포인터가 될 수 있다.
전형적인 투 포인터 형태로
A와 B의 인덱스를 모두 변수로 만들면 투 포인터의 구조가 더 명확하게 보인다.
JavaScript
function solution(A, B) {
A.sort((a, b) => a - b);
B.sort((a, b) => a - b);
let aIndex = 0;
let bIndex = 0;
let count = 0;
while (aIndex < A.length && bIndex < B.length) {
if (A[aIndex] < B[bIndex]) {
// B가 승리했으므로 두 숫자를 모두 사용한다.
count += 1;
aIndex += 1;
bIndex += 1;
} else {
// 현재 B는 가장 작은 A도 이길 수 없으므로 버린다.
bIndex += 1;
}
}
return count;
}Python
def solution(A, B):
A.sort()
B.sort()
a_index = 0
b_index = 0
count = 0
while a_index < len(A) and b_index < len(B):
if A[a_index] < B[b_index]:
# B가 승리했으므로 두 숫자를 모두 사용한다.
count += 1
a_index += 1
b_index += 1
else:
# 현재 B는 가장 작은 A도 이길 수 없으므로 버린다.
b_index += 1
return count현재 B가 A보다 크다면 승리한다.
if A[a_index] < B[b_index]:
count += 1
a_index += 1
b_index += 1A와 B의 숫자를 모두 사용했으므로 두 포인터를 함께 이동한다.
반대로 현재 B가 A보다 작거나 같다면 B의 포인터만 이동한다.
else:
b_index += 1현재 A는 남아 있는 A의 숫자 중 가장 작은 숫자이다.
그런데 현재 B가 가장 작은 A조차 이길 수 없다면, 이후의 더 큰 A도 이길 수 없다.
따라서 현재 B는 버려도 된다.
배운 점
처음에는 다빈치 코드처럼 B의 전체 승패 전략을 먼저 만들어야 한다고 생각했다.
그래서 다음과 같은 전략부터 고민했다.
이길 때는 근소하게 이기고,
질 때는 큰 차이로 진다.
큰 숫자를 불필요하게 사용하지 않고, 어차피 질 경기에는 작은 숫자를 희생하려는 생각이었다.
하지만 이 전략만으로는 어떤 경기에서 이기고, 어떤 경기에서 져야 하는지를 결정할 수 없었다.
문제를 다시 생각해 보니, 각 경기의 승패를 미리 계획할 필요가 없었다.
A와 B를 모두 오름차순으로 정렬한 뒤, A의 가장 작은 숫자부터 확인하면서 현재 A보다 큰 B 중 가장 작은 숫자를 매칭하면 된다.
현재 A를 이길 수 있는 B가 있다면 가장 작은 B로 승리하고, 이길 수 있는 B가 없다면 해당 A는 자연스럽게 승리 대상에서 제외된다.
즉, 어떤 경기에서 이기고 질지를 먼저 결정하는 것이 아니라, 가능한 가장 작은 승리를 반복해서 선택하면 최종적으로 B가 얻을 수 있는 최대 승점이 만들어진다.
