🆙 [LeetCode] 88.Merge Sorted Array.

🆙 [LeetCode] 88.Merge Sorted Array. Difficulty: Easy Topic: Array, Two Pointer, Sorting Approach 1: Merge and sort Intuition(직관) 순진한 접근 방식은 nums2의 값을 그저 nums1의 끝에 쓰고, 그다음 nums1을 정렬하는 것입니다. 우리는 값을 반환할 필요가 없으며, nums1을 직접 수정해야 합니다. 이 방법은 코딩하기는 쉽지만, 이미 정렬된 상태를 활용하지 않기 때문에 높은 시간 복잡도를 가집니다. Implementation(구현) class Solution { func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { for i in 0..<n { nums1[i + m] = nums2[i] } nums1.sort() } } Time complexity(시간 복잡도): O((n + m) log(n+m)) 내장된 정렬 알고리즘을 사용하여 길이가 x인 리스트를 정렬하는 비용은 O(xlogx)입니다. 이 경우에는 길이가 m+n인 리스트를 정렬하므로 총 시간 복잡도는 O((n + m) log(n + m))가 됩니다. Space complexity(공간 복잡도): O(n), 하지만 상황에 따라 다를 수 있습니다. 대부분의 프로그래밍 언어는 O(n) 공간을 사용하는 내장 정렬 알고리즘을 가지고 있습니다. Approach 2: Three Pointers (Start From the Beginning) Intuition(직관) 각 배열이 이미 정렬되어 있기 때문에, Two pointer 기법을 활용하면 O(n+m)의 시간 복잡도를 달성할 수 있습니다. Algorithm nums1의 값을 복사하여 nums1Copy라는 새 배열을 만드는 것이 가장 간단한 구현 방법입니다. 그런 다음 두 개의 읽기(read) 포인터와 하나의 쓰기(write) 포인터를 사용하여 nums1Copy와 nums2에서 값을 읽고 nums1에 씁니다. nums1Copy를 nums1의 처음 m 값이 포함된 새 배열로 초기화합니다. 읽기 포인터 p1을 nums1Copy의 시작 부분에 초기화합니다. 읽기 포인터 p2를 nums2의 시작 부분에 초기화합니다. 쓰기 포인터 p를 nums1의 시작 부분에 초기화합니다. p가 여전히 nums1 내에 있는 동안: nums1Copy[p1]이 존재하고 nums2[p2] 보다 작거나 같으면: nums1Copy[p1]을 nums1[p]에 쓰고 p1을 1 증가시킵니다. 그렇지 않으면 nums2[p2]를 nums1[p]에 쓰고 p2를 1 증가시킵니다. p를 1 증가시킵니다. class Solution { func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { // nums1의 처음 m개 원소의 복사본을 만듭니다. let nums1Copy = Array(nums1[0..<m]) // nums1Copy와 nums2에 대한 읽기 포인터입니다. var p1 = 0 var p2 = 0 // nums1Copy와 nums2에서 원소를 비교하여 더 작은 것을 nums1에 씁니다. for p in 0..<(m + n) { // p1과 p2가 각각의 배열 범위를 벗어나지 않도록 확인합니다. if p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2]) { nums1[p] = nums1Copy[p1] p1 += 1 } else { nums1[p] = nums2[p2] p2 += 1 } } } } Complexity Analysis Time complexity(시간 복잡도) : O(n+m) 우리는 n+2*m 번의 읽기와 n+2*m 번의 쓰기를 수행하고 있습니다. Big O 표기법에서 상수는 무시되므로, 이는 O(n+m)의 시간 복잡도를 의미합니다. Space complexity(공간 복잡도) : O(m) 우리는 추가적으로 길이가 m인 배열을 할당하고 있습니다. Approach 3: Three Pointers (Start From the End) Intuition 인터뷰 팁: 이것은 쉬운 문제에 대한 중간 수준의 솔루션입니다. 쉬운 수준의 문제 중 상당수는 더 어려운 해결책을 갖고 있으며, 좋은 지원자는 이를 찾을것으로 예상됩니다. Approach 2는 이미 최상의 시간 복잡도인 O(n+m)을 보여주지만, 여전히 추가 공간을 사용합니다. 이는 nums1 배열의 요소들을 어딘가에 저장해야 하기 때문에, 그것들이 덮어쓰여지지 않도록 해야하기 때문입니다 그렇다면 대신 nums1의 끝부터 덮어쓰기 시작하면 어떨까요? 거기에는 아직 정보가 없으니까요. 알고리즘은 이전과 유사하지만, 이번에는 p1을 nums1의 m - 1 인덱스에, p2를 nums2의 n - 1 인덱스에, 그리고 p를 nums1의 m + n - 1 인덱스에 두는 방식입니다. 이 방식으로, nums1의 처음 m 값들을 덮어쓰기 시작할 때, 이미 각각을 새 위치에 써 놓았을 것이라는 것이 보장됩니다. 이런 방식으로, 추가 공간을 없앨 수 있습니다. 인터뷰 팁: 베열 문제를 제자리에서 해결하려고 할 때는 항상 배열을 앞에서 뒤로 순회하는 대신 뒤에서 앞으로 순회하는 가능성을 고려해보세요 이것은 문제를 완전히 바꾸어 놓고, 훨씩 쉽게 만들 수 있습니다. Implementation 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 6️⃣ class Solution { func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { // 각 배열의 끝을 가리키는 p1과 p2를 설정합니다. var p1 = m - 1 var p2 = n - 1 // p를 배열을 통해 뒤로 이동하면서, 매번 p1 또는 p2가 가리키는 더 작은 값을 작성합니다. for p in stride(from: m + n - 1, through: 0, by: -1) { if p2 < 0 { break } if p1 >= 0 && nums1[p1] > nums2[p2] { nums1[p] = nums1[p1] p1 -= 1 } else { nums1[p] = nums2[p2] p2 -= 1 } } } } Complexity Analysis Time complexity: O(n + m) Same as Approach 2. Space complexity: O(1) Unlike Approach 2, we’re not using an extra array. Proof(optional) 이 주장에 대해 조금 회의적일 수도 있습니다. 정말 모든 경우에 작동하나요? 이렇게 대담한 주장을 하는 것이 안전한가요? 이 방식으로, `nums1`의 처음 `m`개 값을 덮어쓰기 시작하면, 각각을 이미 새 위치에 써 놓았을 것입니다 이런 방식으로 우리는 추가 공간을 없앨 수 있습니다. 훌륭한 질문입니다! 그렇다면 왜 이 방법이 작동할까요? 이를 증명하기 위해, p가 nums1에서 p1이 아직 읽지 않은 값을 덮어쓰지 않는 것을 확실히 해야 합니다. 조언 :증명에 겁을 먹고 있나요? 많은 소프트웨어 엔지니어들이 그렇습니다. 좋은 증명은 간단히 각각의 논리적 주장들이 다음 주장 위에 구축되는 것입니다. 이런 방식으로, 우리는 "명백한" 진술로부터 시작하여 증명하고자 하는 것에 이룰 수 있습니다. 각 진술을 하나씩 읽으며, 다음으로 넘어가기 전에 각각을 이해하는 것이 중요합니다. 초기화 시 p는 p1보다 n만큼 앞서 있다는 것을 알 수 있습니다.(다른 말로, p1 + n = p 입니다.) 또한, 이 알고리즘이 수행하는 p의 반복 동안, p는 항상 1 만큼 감소하고, p1 또는 p2 중 하나가 1 만큼 감소한다는 것도 알고 있습니다. p1이 감소할 때, p와 p1 사이의 간격은 동일하게 유지되므로, 그 경우에 “추월(overtake)”이 발생할 수 없다는 것을 추론할 수 있습니다. 하지만 p2가 감소할 때는, p는 움직이지만 p1은 그렇지 않으므로, p와 p1 사이의 간격이 1만큼 줄어든가는 것을 추론할 수 있습니다. 그리고 이로부터, p2가 감소할 수 있는 최대 횟수는 n번임을 추론할 수 있습니다. 다시 말해, p와 p1 사이의 간격은 최대 n 만큼 1 씩 줄어들 수 있습니다. 결론적으로, 그들이 처음에 n만큼 떨어져 있었기 때문에 추월이 일어날 수 없습니다. 그리고 p = p1일 때, 간격은 n 번 줄어들어야 합니다. 이는 nums2의 모든 것이 병합되었으므로 더 이상 할 일이 없음을 의미합니다.

Archive · 2024-01-21

🆙 [LeetCode] 1089.Duplicate Zeros.

🆙 [LeetCode] 1089.Duplicate Zeros Difficulty: Easy Topic: Array, Two Pointers 문제는 배열을 제자리에서 수정하도록 요구합니다. 제자리 수정이 제약 조건이 아니라면, 원본 배열에서 대상 배열로 요소를 복사하는 방법을 사용했을 것입니다. 0을 두 번 복사한 것을 주목하세요. var s = 0 var d = 0 let N = source.count // 여기서 'source'는 Int 타입의 배열이라고 가정합니다. var destination = [Int]() // 목적지 배열이 가득 찰 때까지 복사가 수행됩니다. while s < N { if source[s] == 0 { // 0을 두 번 복사합니다. destination.append(0) d += 1 destination.append(0) } else { destination.append(source[s]) } d += 1 s += 1 } 문제 설명에는 새 배열을 확장하지 않고 원래 배열의 길이로만 자른다고도 언급되어 있습니다. 이는 배열의 끝에서 몇몇 요소를 버려야 함을 의미합니다. 이러한 요소들은 새로운 인덱스가 원래 배열의 길이를 넘어서는 요소들입니다. 우리에게 주어진 문제 제약 사항에 대해 다시 생각해 봅시다. 추가 공간을 사용할 수 없기 때문에, 우리의 원본 배열과 대상 배열은 본질적으로 동일합니다. 우리는 단순히 원본을 대상 배열로 그대로 복사할 수 없습니다. 그렇게 하면 몇몇 요소를 잃어버릴 것입니다. 왜냐하면, 우리는 배열을 덮어쓰게 될 것이기 때문입니다. 이를 염두에 두고 아래 겁근 방식에서는 배열의 끝 부분에 복사를 시작합니다. Approach 1: Two pass, O(1) space Intuition(직관) 만약 우리가 배열의 끝에서 버려질 요소의 수를 안다면, 나머지는 복사할 수 있습니다. 우리는 어떻게 배열의 끝에서 버려질 요소의 수를 알아낼 수 있을까요? 그 수는 배열에 추가될 여분의 0의 수와 같을 것입니다. 여분의 0은 배열의 끝에서 요소 하나를 밀어내면서 자신을 위한 공간을 만듭니다. 일단 우리가 원래 배열에서 최종 배열의 일부가 될 요소의 수를 알게 되면, 우리는 끝에서부터 복사하기 시작할 수 있습니다. 끝에서부터 복사하는 것은, 마지막 몇 개의 불필요한 요소들을 덮어쓸 수 있기 때문에, 어떤 요소도 잃어버리지 않게 해줍니다. Algorithm 1️⃣. 중복될 제로의 수를 찾습니다. 이를 possible_dups라고 합시다. 최종 배열의 일부가 되지 않을 잘린 제로들을 세지 않도록 주의해야 합니다. 버려진 제로들은 최종 배열의 일부가 되지 않기 때문입니다. possible_dups의 개수는 원래 배열에서 잘릴 요소의 수를 알려줄 것입니다. 따라서 어느시점에서든, length_ - possible_dups는 최종 배열에 포함될 요소의 수입니다. 참고: 위의 다이어그램에서는 이해를 돕기 위해 원본 배열과 대상 배열을 보여줍니다 우리는 이러한 연산들을 오직 하나의 배열에서만 수행할 것입니다. 2️⃣. 남은 요소들의 경계에 있는 제로에 대한 에지 케이스를 처리합니다. 이 문제의 에지 케이스에 대해 이야기해 봅시다. 남은 배열에서 제로를 복제할 때는 특별한 주의가 필요합니다. 이 주의는 경계에 놓인 Zero에 대해서 취해져야 합니다. 왜냐하면, 이 제로는 가능한 중복으로 간주되거나, 그것의 복제를 수용할 공간이 없을 때 남은 부분에 포함될 수 있기 때문입니다. 만약 그것이 possible_dups의 일부라면 우리는 그것을 복제하고 싶을 것이고, 그렇지 않다면 복제하지 않을 것입니다. 에지 케이스의 예는 - [8,4,5,0,0,0,0,7] 입니다. 이 배열에서 첫 번째와 두 번째로 제로의 중복을 수용할 공간이 있습니다. 하지만 세번째 제로의 중복을 위한 충분한 공간이 없습니다. 따라서 복사할 때 세 번째 제로에 대해선 두 번 복사하지 않도록 주의해야 합니다. 결과 = [8,4,5,0,`0`,0,`0`,0] 3️⃣. 배열의 끝에서부터 순회하여, 0이 아닌 요소는 한 번, 0 요소는 두 번 복사합니다. 우리가 불필요한 요소들을 버린다고 할 때, 이는 단순히 불필요한 요소들의 왼쪽에서 시작하여 새로운 값들로 그것들을 덮어쓰고, 결국 남은 요소들은 오른쪽으로 이동시켜 배열 안에 중복된 요소들을 위한 공간을 만들어낸다는 것을 의미합니다. class Solution { func duplicateZeros(_ arr: inout [Int]) { var possibleDups = 0 let length_ = arr.count - 1 // 복제할 0의 개수를 찾습니다. // 원래 배열의 마지막 요소를 넘어서면 중지합니다. // 수정된 배열의 일부가 될 마지막 요소를 넘어서면 중지합니다. for left in 0...(length_ - possibleDups) { // 0 숫자 세기 if arr[left] == 0 { // Edge case: 이 0은 복제할 수 없습니다. 더 이상 공간이 없습니다. // 왼쪽은 포함될 수 있는 마지막 요소를 가리키고 있습니다. if left == length_ - possibleDups { // 이 0의 경우 중복 없이 복사합니다. arr[length_] = 0 break } possibleDups += 1 } } // 새 배열의 일부가 될 마지막 요소부터 거꾸로 시작합니다. var last = length_ - possibleDups // 0을 두 번 복사하고 0이 아닌 것을 한 번 복사합니다. while last >= 0 { if arr[last] == 0 { arr[last + possibleDups] = 0 possibleDups -= 1 arr[last + possibleDups] = 0 } else { arr[last + possibleDups] = arr[last] } last -= 1 } } } Complexity Analysis 시간 복잡도(Time Complexity): O(N), 여기서 N은 배열의 요소 수입니다. 우리는 배열을 두 번 순회하는데, 하나는 possible_dups의 수를 찾기 위해, 다른 하나는 요소들을 복사하기 위해 사용됩니다. 최악의 경우, 배열에 zero가 적거나 없을 때 배열 전체를 순회할 수도 있습니다. 공간 복잡도(Space Complexity): O(1), 우리는 추가적인 공간을 사용하지 않습니다.

Archive · 2024-01-20

📝 배열 삽입 3(배열의 아무 곳에나 삽입하기 - Inserting Anywhere in the Array)

배열 삽입 시리즈 배열 삽입1 (배열의 끝에 삽입하기-Inserting at the End of an Array) 배열 삽입2 (배열의 시작 부분에 삽입하기 - Inserting at the Start of an Array) 마찬가지로, 주어진 인덱스에 삽입하기 위해서는, 해당 인덱스부터 시작하는 모든 요소들을 오른쪽으로 한 자리씩 이동시켜야 합니다. 새 요소를 위한 공간이 생성되면, 삽입을 진행합니다. 생각해보면, 시작 부분에 삽입하는 것은 사실 주어진 인덱스에 요소를 삽입하는 것의 특별한 경우에 해당합니다. 그 경우에 주어진 인덱스는 0이었습니다. 다시 한 번 말씀드리지만, 이것도 비용이 많이 드는 작업입니다. 새 요소를 실제로 삽입하기 전에 거의 모든 다른 요소들을 오른쪽으로 이동시켜야 할 수도 있기 때문입니다. 위에서 보셨듯이, 많은 요소들을 오른쪽으로 한 칸씩 이동시키는 것은 삽입 작업의 시간 복잡도를 증가시킵니다. 다음은 코드의 모습입니다 // 배열 삽입 1,2 코드 참고 var intArray = [Int](repeating: 0, count: 6) var length = 0 for i in 0..<3 { intArray[length] = i length += 1 } func printArray() { for i in 0..<intArray.count { print("Index \(i) contains \(intArray[i])") } } intArray[length] = 10 length += 1 for i in(0...3).reversed() { intArray[i + 1] = intArray[i] } intArray[0] = 20 // 인덱스 2에 요소를 삽입하고 싶다고 가정해봅시다. // 먼저, 새로운 요소를 위한 공간을 만들어야 합니다. for i in stride(from: 4, through: 2, by: -1) { // 각 요소를 오른쪽으로 한 위치씩 이동시킵니다. intArray[i + 1] = intArray[i] } // 이제 새로운 요소를 위한 공간을 만들었으므로, // 필요한 인덱스에 삽입할 수 있습니다. intArray[2] = 30 printArray() 다음은 printArray를 실행한 결과입니다. Index 0 contains 20. Index 1 contains 0. Index 2 contains 30. Index 3 contains 1. Index 4 contains 2. Index 5 contains 10. 주의해야 할 주요한 것은 array.capacity가 베열의 전체 용량을 제공한다는 점을 기억하는 것입니다. 마지막으로 사용된 슬롯을 알고 싶다면 count 변수를 사용하여 직접 추적해야합니다.

Archive · 2024-01-19

📝 배열 삽입 2(배열의 시작 부분에 삽입하기 - Inserting at the Start of an Array)

배열 삽입 시리즈 배열 삽입1 (배열의 끝에 삽입하기-Inserting at the End of an Array) 배열의 시작 부분에 삽입하기(Inserting at the Start of an Array) 배열의 시작 부분에 요소를 삽입하려면, 새 요소를 위한 공간을 만들기 위해 배열의 다른 모든 요소들을 오른쪽으로 하나의 인덱스만큼 이동시켜야 합니다. 이것은 비용이 매우 많이 드는 작업입니다, 왜냐하면 기존의 요소들을 모두 오른쪽으로 한 단계씩 이동시켜야 하기 때문입니다. 모든 것을 이동시켜야 한다는 것은 이 작업이 상수 시간 작업이 아니라는 것을 의미합니다. 사실, 배열의 시작 부분에 삽입하는 데 걸리는 시간은 배열의 길이에 비례할 것입니다. 시간 복잡도 분석 측면에서 이는 선형 시간 복잡도, 즉 O(N)인데, 여기서 N은 배열의 길이입니다. 다음은 코드의 모습입니다. // 배열삽입 1 코드 참고 var intArray = [Int](repeating: 0, count: 6) var length = 0 for i in 0..<3 { intArray[length] = i length += 1 } func printArray() { for i in 0..<intArray.count { print("Index \(i) contains \(intArray[i])") } } intArray[length] = 10 length += 1 // 먼저, 새로운 요소를 위한 공간을 만들어야 합니다. // 이를 위해 각 요소를 오른쪽으로 하나의 인덱스만큼 이동시킵니다. // 이것은 먼저 인덱스 3의 요소를 이동시키고, 그 다음 2, 그 다음 1, 마지막으로 0을 이동시킵니다. // 어떤 요소도 덮어쓰지 않기 위해 뒤에서부터 진행해야 합니다. for i in(0...3).reversed() { intArray[i + 1] = intArray[i] } // 이제 새로운 요소를 위한 공간을 만들었으므로, // 시작 부분에 삽입할 수 있습니다. intArray[0] = 20 printArray() 다음은 printArray()를 실행한 결과입니다. Index 0 contains 20. Index 1 contains 0. Index 2 contains 1. Index 3 contains 2. Index 4 contains 10. Index 5 contains 0.

Archive · 2024-01-19

📝 배열 삽입 1(배열의 끝에 삽입하기-Inserting at the End of an Array)

배열에 새로운 요소를 삽입하는 것은 여러 형태를 가질 수 있습니다: 배열의 끝에 새 요소를 삽입하기. 배열의 시작 부분에 새 요소를 삽입하기. 배열 내의 주어진 인덱스에 새 요소를 삽입하기. 배열의 끝에 삽입하기(Inserting at the End of an Array). 어느 시점에서든, 우리는 length 변수에 추적해둔 배열의 마지막 요소의 인덱스를 알고 있습니다. 끝에 요소를 삽입하기 위해 해야 할 일은 현재 마지막 요소 다음 인덱스에 새 요소를 할당하는 것뿐입니다. 이것은 우리가 이미 본 것과 거의 같습니다. 최대 6개의 항목을 담을 수 있는 새 배열을 만들고, 그 다음 첫 3개의 인덱스에 항목을 추가하는 코드입니다. // 6개의 요소를 가진 정수 배열 선언 var intArray = [Int](repeating: 0, count: 6) var length = 0 // 배열에 3개의 요소 추가 for i in 0..<3 { intArray[length] = i length += 1 } 우리가 무슨 일이 일어나고 있는지 시각화하는 데 도움이 되는 함수, printArray를 정의해봅시다. for i in 0..<intArray.count { print("Index \(i) contains \(intArray[i])") } 우리가 printArray 함수를 실행하면 다음과 같은 출력을 얻을 수 있습니다. Index 0 contains 0. Index 1 contains 1. Index 2 contains 2. Index 3 contains 0. Index 4 contains 0. Index 5 contains 0. 인덱스 3, 4, 5가 모두 0을 포함하고 있는 것을 보셨나요? 이것은 Swift가 사용하지 않는 int 배열 슬롯을 0으로 채우기 때문입니다. 이제 4번째 요소를 추가해봅시다. 숫자 10을 추가할 것입니다. // 배열 끝에 새 요소를 삽입. 다시 한번, // 새 요소를 삽입하기 위해 배열에 충분한 공간이 있는지 확인하는 것이 중요합니다. intArray[length] = 10 length += 1 길이를 1 증가시킨 이유를 알아채셨나요? 길이를 1 증가시키는 것이 중요합니다. 이 단계를 건너 뛰면 다음에 다른 요소를 추가할 때 방금 추가한 요소를 실수로 덮어쓰게 됩니다! printArray를 다시 실행하면 다음과 같은 결과를 얻을 수 있습니다. Index 0 contains 0. Index 1 contains 1. Index 2 contains 2. Index 3 contains 10. Index 4 contains 0. Index 5 contains 0.

Archive · 2024-01-19

📝 기본 배열 작업

기본 배열 작업. 배열은 데이터 구조로, 특정 형식으로 데이터를 저장하고 저장된 데이터에 대해 특정 작업을 지원합니다. DVD 재고 관리 소프트웨어를 생각해 보세요. 이 소프트웨어를 사용하여 수행하고 싶은 몇 가지 작업들을 살펴보겠습니다: 특정 위치에 새 DVD 컬렉션에 삽입(Insert) 합니다. 더 이상 재고에 보관할 필요가 없다면 기존 컬렉션에서 DVD를 삭제(Delete) 합니다. 컬렉션에서 특정 DVD를 검색(Search) 합니다. 이것은 컬렉션에서 가장 흔하게 실행되는 작업 중 하나입니다. 왜냐하면 우리의 재고 관리 소프트웨어는 사용자가 요청한 특정 DVD를 찾기 위해 하루에 수백 번 사용될 것이기 때문입니다. 거의 모든 데이터 구조에서 지원하는 세 가지 기본 작업인 삽입(Insert), 삭제(Delete), 검색(Search) 에 대해 자세히 알아보고 학습해야 합니다.

Archive · 2024-01-19

📝 배열의 용량 vs 배열의 길이

Array Capacity VS Length 만약 누군가가 당신에게 DVD 배열의 길이가 얼마나 되는지 물어본다면, 당신의 대답은 무엇일까요? 당신은 두 가지 다른 대답을 할 수 있습니다. 상자가 가득 차있을 경우, 상자가 담을 수 있는 DVD의 수, 또는 현재 상자에 들어있는 DVD의 수. 이 두 답변은 모두 정확하며, 매우 다른 의미를 가집니다! 이 둘의 차이를 이해하고 올바르게 사용하는 것이 중요합니다. 우리는 첫 번째를 배열의 ‘용량’이라고 부르고, 두번째를 ‘길이’라고 부릅니다. Array Capacity DVD[] array = new DVD[6] array[6]에 요소를 삽입하는 것이 유효한 작업일까요? array[10]은 어떨까요? 아니요, 이 두 경우 모두 유효하지 않습니다. 배열을 생성할 때, 이 배열이 최대 6 개의 DVD를 담을 수 있다고 지정했습니다. 이것이 배열의 용량입니다. 인덱싱이 0부터 시작한다는 것을 기억한다면, 우리는 오직 array[0], array[1], array[2], array[3], array[4] 그리고 array[5]에만 항목을 삽입할 수 있습니다. array[-3], array[6], array[100]과 같이 다른 곳에 요소를 넣으려고 하면 ArrayIndexOutOfBoundsExecption으로 코드가 충돌하게 됩니다. 배열의 용량은 배열이 생성될 때 결정되어야 합니다. 용량은 나중에 변경할 수 없습니다. 우리가 사용한 종이 상자에 DVD를 넣는 비유로 돌아가 보면, 배열의 용량을 변경하는 것은 종이 상자를 더 크게 만들려는 것과 같습니다. 고정된 크기의 종이 상자를 더 크게 만드는 것은 비현실적이며, 컴퓨터의 배열에서도 마찬가지입니다! 그렇다면 7번째 DVD를 얻었을 때, 모든 DVD를 같은 배열에 넣고 싶다면 어떻게 할까요? 불행히도 종이 상자의 경우와 마찬가지입니다. 더 큰 상자를 새로 구해서, 기존의 DVD들과 새로운 것을 모두 옮겨야 합니다 자바에서 배열의 용량은 배열의 length 속성값을 확인함으로써 알 수 있습니다. 이는 arr.length라는 코드를 사용하여 확인되는데, 여기서 arr은 배열의 이름입니다. 다른 프로그래밍 언어들은 배열의 길이를 확인하는 데 다른 방법을 사용합니다. int capacity = array.length; System.out.println("The Array has a capacity of " + capacity); 이 코드를 실행하면 다음과 같은 출력이 나옵니다: The Array has a capacity of 6 capacity property of Swift Instance Property capacity 배열이 새로운 저장 공간을 할당하지 않고 담을 수 있는 요소의 총 수입니다. 모든 배열은 그 내용을 저장하기 위해 특정 양의 메모리를 예약합니다. 배열에 요소를 추가하고 그 배열이 예약된 용량을 초과하기 시작하면, 배열은 더 큰 메모리 영역을 할당하고 그 요소들을 새로운 저장 공간으로 복사합니다. 새로운 저장 공간은 기존 저장 공간 크기의 배수입니다. 이 지수적 성장 전략은 요소 추가 작업이 평균적으로 상수 시간 내에 이루어지게 하여, 많은 추가 작업의 성능을 평균화합니다. 재할당을 유발하는 추가 작업에는 성능 비용이 들지만, 배열이 커짐에 따라 그런 작업은 점점 덜 자주 발생합니다. 다음 예시는 배열 리터럴로부터 정수 배열을 생성한 다음, 다른 컬렉션의 요소들을 추가합니다. 추가 하기 전에, 배열은 결과 요소들을 저장할 수 있을 만큼 충분히 큰 새로운 저장 공간을 할당합니다. var numbers = [10, 20, 30, 40, 50] // numbers.count == 5 // numbers.capacity == 5 numbers.append(contentsOf: stride(from: 60, through: 100, by: 10)) // numbers.count == 10 // numbers.capacity == 10 Array Length 길이(length) 의 또 다른 정의는 배열에 현재 들어 있는 DVD의 수, 또는 다른 항목들의 수입니다 이것은 직접 추적해야 할 것이며, 기존 DVD를 덮어쓰거나 배열에 공백을 남겨두어도 오류는 발생하지 않습니다. 이전 예제에서 length 변수를 사용하여 다음 비어 있는 인덱스를 추적하고 있는 것을 눈치챘을 수 있습니다. // 용량이 6인 새 배열을 생성합니다. int[] array = new int[6]; // 현재 길이는 0이며, 요소가 0개 있기 때문입니다. int length = 0; // 그 안에 3개의 항목을 추가합니다. for (int i = 0; i < 3; i++) { array[i] = i * i; // 요소를 추가할 때마다 길이가 1씩 증가합니다. length++; } System.out.println("배열의 용량은 " + array.length + "입니다."); System.out.println("배열의 길이는 " + length + "입니다."); 이 코드를 실행하면 다음과 같은 출력이 나옵니다: The Array has a capacity of 6 The Array has a length of 3 count property of Swift Instance Property count 배열의 요소(elements) 수 입니다. var count: Int { get } Handling Array Parameters(배열 매개변수 처리하기) LeetCode에서의 대부분의 배열 문제는 “길이”나 “용량” 매개변수 없이 매개변수로 배열을 전달합니다. 이게 무슨 뜻일까요? 예를 들어 설명해 보겠습니다. 여기 당신이 풀게 될 첫 번째 문제의 설명이 있습니다. ‘이진 배열이 주어졌을 때, 이 배열에서 연속된 1의 최대 개수를 찾아라.’ 그리고 여기 주어진 코드 템플릿이 있습니다. class Solution { public int findMaxConsecutiveOnes(int[] nums) { } } 유일한 매개변수는 'nums' 인데, 이는 배열입니다. 'nums'의 길이를 모르면 이 문제를 해결할 수 없습니다. 다행히도 이는 간단합니다. 매개변수로 주어진 배열에 대한 추가 정보가 없을때는 길이 == 용량 (length == capacity) 이라고 안전하게 가정할 수 있습니다. 즉, 배열은 그 데이터를 모두 담기에 정확히 적합한 크기입니다. 따라서 .length를 사용할 수 있습니다. 하지만 조심하세요, 배열은 0부터 시작하는 인덱스입니다. 용량(capacity)/길이(length)는 항목의 수이지 최고 인덱스가 아닙니다. 최고 인텍스는 .lenght -1 입니다. 따라서 배열의 모든 항목을 순회하기 위해 다음과 같이 할 수 있습니다. class Solution { public int findMaxConsectiveOnes(int[] nums) { // 힌트: 여기에 변수를 초기화하고 선언하여 // 연속된 1이 몇 개인지 추적합니다. for (int i = 0; i < nums.length; i++) { // nums[i] 요소로 무언가를 합니다. } } } 이것이 바로 시작하기 위해 필요한 배열의 기본 사항입니다!

Archive · 2024-01-18

devkobe24.com

Contact

Leet-Code