2657. Find the Prefix Common Array of Two Arrays

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/description/

 

이번 문제는 최적의 방법으로 풀지는 못했지만 일단 정석대로 풀었다.

문제
길이가 n인 두 개의 0-인덱스 정수 순열 A와 B가 주어집니다.

A와 B의 접두사 공통 배열은 C[i]가 A와 B 모두에서 인덱스 i에 있거나
그 앞에 있는 숫자의 개수와 같은 배열 C입니다.

A와 B의 접두사 공통 배열을 반환합니다.

n개의 정수 시퀀스는 1에서 n까지의 모든 정수를 정확히 한 번씩 포함하는 경우 순열이라고 합니다.

예 1:
입력: A = [1,3,2,4], B = [3,1,2,4]
출력: [0,2,3,4]
설명:
i = 0일 때: 공통된 숫자가 없으므로 C[0] = 0입니다.
i = 1일 때: A와 B에서 1과 3이 공통이므로 C[1] = 2입니다.
i = 2일 때: A와 B에서 1, 2, 3이 공통이므로 C[2] = 3입니다.
i = 3일 때: A와 B에서 1, 2, 3, 4가 공통이므로 C[3] = 4입니다.

예 2:
입력: A = [2,3,1], B = [3,1,2]
출력: [0,1,3]
설명:
i = 0일 때: 공통된 숫자가 없으므로 C[0] = 0입니다.
i = 1일 때: A와 B에서 공통적인 것은 3뿐이므로 C[1] = 1입니다.
i = 2에서: A와 B에서 1, 2, 3이 공통적이므로 C[2] = 3입니다.

제약 조건:
1 <= A.length == B.length == n <= 50 1 <= A[i],
B[i] <= n A와 B가 모두 n개의 정수 순열임이 보장됩니다.

 

요약하자면 두개의 배열이 주어지는데 i번째 배열까지 같은 값이 포함된다면 카운트 해서 순서대로 반환해라 이다.

 

처음에 이 문제를 잘못 이해해서 이렇게 작성했었다.

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int size = A.length;
        int[] c = new int[size];
        int temp = 0;
        
        for(int i = 0; i < size; i++){
            temp = 0;
            for(int j = 0; j <= i; j++){
                if(A[i] == B[j] && (i-1) > 0){
                    c[i-1] = temp;
                }else{
                    temp++;
                }
            }
        }
        c[size-1] = size;

        return c;
    }
}

 

일단 모든 배열의 크기는 같기 때문에 size를 먼저 구하고,

2중 for문으로 반복하며 같은 값이 있다면 개수를 세서 넣었다.

마지막에는 제대로 값이 안들어가서 c[size - 1] = size 로 집어넣었다.

 

아주 엉망진창이고 별로인 코드지만 일단 테스트 케이스는 통과했기에 그대로 제출했다가 바로 틀렸다.

 

이후에 친구를 만나 이야기를 나눴는데 내가 문제를 제대로 이해하지 못하고 있다고 했다.

그래서 이번에는 차근차근 노트에다 한줄씩 적어서 생각을 정리한 다음 작성했다.

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int size = A.length;
        int[] c = new int[size];

        for(int i = 0 ; i < size; i++){     // 순서
            for(int j = 0; j <= i; j++){    // A의 값
                for(int k = 0; k <= i; k++){// B의 값
                    if(A[j] == B[k]){
                        c[i]++;
                    }
                }
            }
        }
        return c;
    }
}

 

3중 for문을 써서 i번째 배열에 대한 값을 각각 비교해서 c[i]를 증가시켜 반환하는 코드이다.

가장 기본적이고 이번  문제의 핵심이다.

런타임은 21ms, 메모리 45.4mb로, 아마 제약조건에 A와 B의 값이 50보다 더 높았다면 시간이 초과됐을것이다.

 

이 다음에는 한번 해시셋을 이용해서 풀어보았는데

class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int size = A.length;
        
        int[] result = new int[size];
        HashSet<Integer> n1 = new HashSet();
        HashSet<Integer> n2 = new HashSet();

        for(int i = 0; i < size; i++){
            n1.add(A[i]);
            n2.add(B[i]);
            
            HashSet<Integer> n3 = new HashSet(n1);
            n3.retainAll(n2);

            result[i] = n3.size();
        }
        return result;
    }
}

 

코드 자체는 더 깔끔해졌고 알아보기 쉬워졌지만 런타임 41ms, 메모리 45.3mb로 더 나빠졌다.

아마 이유는 for문에서 해시셋을  반복적으로 생성하기 때문이라고 생각하는데,

처음에 해시셋을 쓸 때, retainAll이라는 함수가 있다는것을 보고 배열의 공통된 값을 제거하고 나머지만 남긴다고 해서

아 이걸 쓰면 되겠구나 했는데, 그 결과값을 객체에 저장할줄은 몰랐다...

 

그래서 하는수 없이 n3를 하나 생성해서 남은 값들을 저장하고 그 사이즈를 측정해서 배열에 집어넣어 반환했다.

중간에 해시셋을 빼고 if문으로 바꾸면 최적의 결과가 나오겠지만 일단 여기까지 하기로 했다.

 

나는 항상 문제를 풀 때 먼저 생각난걸 바로바로 코드로 작성해서 테스트로 돌려본 다음 오류를 하나씩 수정해나갔지만

다음부턴 알고리즘 문제를 풀 땐 한번 내가 손으로 동작을 써본다음에 코드를 작성해서 풀어보는게 좋단걸 배웠다.

 

이번에도 그런식으로 문제를 풀다가 처음부터 틀린채로 계속 나아가다가 결국 해결하지 못하고 처음부터 다시 시작하는걸 반복했지만 한번 먼저 손으로 써본다음에 작성하면 그렇게 여러번 시도하기 전에 틀린걸 알수있을 것이다.