def solution(A, B):
answer = 0
A.sort()
B.sort()
for a in A :
for b in B :
if a < b :
answer += 1
B.remove(b)
break
if B.index(b) == (len(B) -1) :
minV = min(B)
B.remove(minV)
return answer
나는 A, B 모두 오름차순해서 작은 숫자부터 비교할거라서 이중 for 문 돌렸다
1) B 배열을 순회하면서 A 보다 커지는 B 가 나온다면 그대로 배치하고 break
2) 만약 끝까지 돌았는데도 A 보다 큰 수가 없다면 남아있는 B 원소 중 가장 작은 수 배치
- 어차피 A 보다 큰 수가 없다면 버리는 숫자로 젤 작은 숫자를 배치한다는 의미..!!!
정확성은 다 통과했는데 시간 초과로 효율성에서 팽 당함 ㅎㅎ
그래서 생각했던 게 어차피 못 이기는 자연수 a 가 있다면
이중 for 문 들어가기 전에 제일 작은 b 로 배치하고 들어가면 좀 낫지 않을까 ,,, 하다가
def solution(A, B):
answer = 0
A.sort()
B.sort()
while (len(A) > 0) :
if A[-1] >= B[-1] :
A.remove(A[-1])
B.remove(B[0])
else :
A.remove(A[-1])
B.remove(B[-1])
answer += 1
return answer
이렇게도 해봤는데
정확성은 다 맞고 효율성은 3개 다 실패함 ㅠㅠ
왜 시간이 더 걸리는 거지 했는데
remove 연산 시간 복잡도가 O(n) 이었다,,,,,
def solution(A, B):
answer = 0
A.sort()
B.sort()
a_i, b_i = -1, -1
while (len(A) > 0) :
if abs(a_i) == len(A) + 1 :
return answer
if A[a_i] >= B[b_i] :
a_i -= 1
B.remove(B[0])
else :
a_i -= 1
b_i -= 1
answer += 1
그래서 remove 로 삭제하는 대신
A 원소 가리키는 a_i 와 B 원소 가리키는 b_i 선언해서 대신 해줬다
그리고 B 의 가장 작은 수로 배치해줄 때 굳이 min() 이용하는 대신
이미 오름차순되어 있으니까 B[0] 으로 바꿔줌 !!
마지막으로 A 원소가 다 없어져서
a 인덱스가 범위 벗어나면 바로 리턴해주고 끝 !!!! 드ㅜ뎌!!!
'알고리즘' 카테고리의 다른 글
[프로그래머스 Lv2 - 2022 KAKAO BLIND RECRUITMENT] 주차 요금 계산 (Python) (0) | 2022.09.16 |
---|---|
[프로그래머스 Lv1 - 2022 KAKAO TECH INTERNSHIP] 성격 유형 검사하기 (Python) (0) | 2022.09.07 |
[프로그래머스 Lv2] 괄호 회전하기 (Python) (0) | 2022.08.04 |
[프로그래머스 Lv3] 베스트앨범 (Python) (0) | 2022.07.28 |
[프로그래머스 Lv2] 예상 대진표 (Python) (0) | 2022.07.27 |