넘치게 채우기
[LeetCode] 2657. Find the Prefix Common Array of Two Arrays 본문
[LeetCode] 2657. Find the Prefix Common Array of Two Arrays
riveroverflow 2025. 1. 14. 11:01https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/description/
leetcode - Find the Prefix Common Array of Two Arrays
문제 유형: 구현, 카운팅, 구간합
문제 난이도: Medium
문제
You are given two 0-indexed integer permutations A and B of length n.
A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.
Return the prefix common array of A and B.
A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.
정수의 순열 A와 B가 n의 길이로 주어진다.
A와 B의 prefix common array란 A와 B의 인덱스 0부터 i까지의 같은 수를 가진 개수를 C[i]에 저장한 것을 만한다.
A와 B의 prefix common array를 반환하시오.
풀이
n <=50이므로, 그대로 구현해도 맞긴 한다.
더 효율적으로 풀고 싶다면, 등장여부를 저장하는 배열 seenA, seenB에 대해, seenA에 업데이트한 값이 seenB에 이미 있는지 검사하고 있다면, 매치되는 수를 늘리면 된다. 그 반대도 그렇다.
c[i]에 현재까지 매치되는 수를 저장한다.
코드
C++
무식하게 구현하기
class Solution {
public:
int getCommon(vector<bool>& a, vector<bool>& b, int n) {
int res = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] && b[i]) res++;
}
return res;
}
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<bool> aFreq(n+1, false);
vector<bool> bFreq(n+1, false);
vector<int> ans;
for(int i = 0; i < n; ++i) {
aFreq[A[i]] = true;
bFreq[B[i]] = true;
ans.push_back(getCommon(aFreq, bFreq, n));
}
return ans;
}
};
더 효율적인 풀이
class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
vector<bool> seenA(n+1, false), seenB(n+1, false);
vector<int> c(n);
int x = 0;
for(int i = 0; i < n; ++i) {
seenA[A[i]] = true;
if(seenB[A[i]]) x++;
seenB[B[i]] = true;
if(seenA[B[i]]) x++;
c[i] = x;
}
return c;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 2425. Bitwise XOR of All Pairings (0) | 2025.01.16 |
---|---|
[LeetCode] 2429. Minimize XOR (0) | 2025.01.15 |
[LeetCode] 3223. Minimum Length of String After Operations (0) | 2025.01.13 |
[LeetCode] 2116. Check if a Parentheses String Can Be Valid (0) | 2025.01.12 |
[LeetCode] 1400. Construct K Palindrome Strings (0) | 2025.01.11 |