Today I Learned

오늘은 주제를 안정하고 그냥 랜덤하게 문제를 골라서 풀어봤다.
아 그리고 TIL에 코테풀이랑 개념정리랑 구분하지 않고 올리다 보니 헷갈려서 앞으로 코테는 CT라는 말머리를 붙이기로 했다.

숫자게임

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

• 문제
  두 집단의 구성원들이 랜덤한 자연수를 분배받아서 숫자가 더 크면 승점을 버는 게임을 한다. 이때 A 집단의 숫자가 다 공개되어있다면 B 집단에서 쌓을 수 있는 최대 승점 수를 구하라.

• 풀이 과정

1. 답이 B의 순서도 아니고 최대 승점 수기 때문에 양쪽의 배열을 우선 오름차순으로 sort했다.

2. 최소값끼리 비교해서 b가 크면 승점 1씩 올리고 a와 b의 인덱스를 다음으로 넘긴다. b가 더 크지않으면 b의 인덱스만 다음으로 넘겨 그 a값을 다음 b와 비교한다.

3. 간단히 이중 for문과 break을 써서 구현.

• 구현 코드

import java.util.*;
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        int l = B.length;
        int b = 0;
        
        for(int i=0; i<l; i++){
            for(int j=b; j<l; j++){
                if(B[j]>A[i]){
                    answer++;
                    break;
                }
               b++;
            }
        }
        
        
        return answer;
    }
}

리팩토링

• 위의 코드는 이중 for문이긴 하지만 안쪽의 b가 순회를 한번만 하므로 O(n^2)까지 가진 않는다.

• 하지만 문제가 너무 쉽게 풀려서 이 코드를 조금이라도 더 개선할 수 있는지 생각해봤다.

• 이중 for문을 수정해서 a와 b 인덱스를 변수에 할당해 while문으로 돌렸다.

• 시간복잡도 상으로는 어차피 sort에서 O(n log n)을 잡아먹으므로 달라질게 없지만 효율성 검사에서 시간이 조금이나마 줄었고 가독성도 좋아진 것 같다.

• 수정 코드

import java.util.*;
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        int l = B.length;
        int a = 0;
        int b = 0;
        
        while(a<l && b<l){
            if(B[b] > A[a]){
                answer++;
                a++;
                b++;
            } else{
                b++;
            }
        }
        
        
        return answer;
    }
}