2. Arrays

배열이란?

같은 타입의 데이터를 연속된 메모리 공간에 위치해 인덱스로 값을 가져올 수 있다. 배열의 크기는 생성할 때 정해지며 한 번 생성하면 사이즈는 고정이기 때문에 변경할 수 없다.

만약 동적 배열이 필요할 경우, 자바에서는 ArrayList를 사용할 수 있다(c++에서는 vector). 

 

코딩테스트 팁 🗝️

배열은 나중에 어려운 문제를 풀 때 기본으로 알고 있어야 하기 때문에 배열 관련 코드는 쉽고 빠르게 작성할 수 있을 만큼 익숙해져야 한다. 배열관련 문제는 종류도 다양하고 난이도가 처음 접하면 생각보다 어려운 문제들이 많다. prefix sum, sliding window, two pointer 같은 개념을 배열 문제를 풀 때 알아두면 좋고, HashMap도 많이 활용하기 때문에 해시맵의 메소드를 어떻게 활용해서 문제를 풀 수 있는지 정리해 놓는걸 추천한다. 

배열 문제를 풀 때 알아야 되는 개념
🎃 prefix sum 
🎃 sliding window
🎃 two pointer (중요!!!)

HashMap 메소드 활용법
🎃 getOrDefault(Object key, V defaultValue): 해당 키에 대한 매핑 값 리턴. 매핑된 값이 없을 경우 디폴트값 리턴
🎃 containsKey(Object key): 해당 키에 대한 매핑이 있을 경우 true 리턴
🎃 putIfAbsent(K Key, V value): 해당 키에 매핑된 값이 없을 경우, 인자로 들어온 값 매핑
🎃 맵 자료구조 반복문 작성 방법

IndexOutOfBoundsException 주의
🎃 반복문이나 조건 검을 할 때 배열의 인덱스를 arr[i - 1] > arr[i] 또는 arr[i] > arr[i + 1] 이런식으로 비교하는 경우 -1 또는 +1을 할 때 인덱스 범위를 벗어 나지 않도록 주의

1차원 -> 2차원 배열로 변경 시 modulo 사용방법
🎃 1차원 배열의 값을 순서대로 2차원 배열에 값을 넣는다고 하면 행은 / division operator, 열은 % modulo operator를 사용해서 위치를 구할 수 있다. 이때 분모로는 열의 길이가 들어간다 (예, 사이즈가 9인 1차원 배열의 5번째 인덱스의 값은 3*3 크기의 2차원 배열 1행 2열에 위치 (5 / 3 = 1, 5 % 3 = 2)
🎃 row = i / m (column length)
🎃 col = i % m (column length)

 

코드

배열에서 값 swap 방법

예를 들어 아래 사진처럼 배열이 있다고 하면

int 배열

특정 인덱스 값의 위치를 변경할 때 코드는 아래처럼 작성한다.

swap하는 메소드

 

temp 변수에 arr[num1]에 넣으면 arr[num1]에 바꿀 값(arr[num2])을 넣고 그럼 arr[num2]에 arr[num1]값을 넣어줘야 하는데,  arr[num1]에는 지금 arr[num2] 값이 들어가 있으니까 원래의 arr[num1] 값이 저장되어 있는 temp 값을 arr[num2]에 넣어야 되는구나 이런식으로 생각하면서 스왑 정도는 반복문 작성하듯이 익숙해져야 한다. 

스왑하는 코드

 

배열의 범위를 지정해서 reverse 하는 방법

배열의 순서를 바꿔야 할 경우, 예를 들어 리트코드의 next permutation 문제를 풀다보면 배열의 특정 부분을 뒤집어야 할 경우가 있다. 이때는 메소드에 배열의 범위, 시작과 끝 인덱스 값을 넣어서 메소드를 작성한다. 

배열의 특정 부분을 reverse 하는 코드

 

reverse() 메소드를 사용하면 해당 범위의 값의 순서를 변경할 수 있다(내림차순 -> 오름차순, 오름차순 -> 내림차순)

 

 

배열 문제 리스트

LeetCode

73. Set Matrix Zeros (공간복잡도를 O(1)로 푸는 방법. 첫번째 행과 열을 사용해서 '0'이 있는지 flag로 기록. 겹치는 부분(0, 0)은 boolean 변수 2개 isFirstRow, isFirstCol를 선언해서 체크)

118. Pascal's Triangle 

31. Next Permutation (제일 긴 접두사를 찾은 뒤 가장 작은 숫자를 찾아서 swap. 나머지 숫자는 정렬함)

53. Maximum Subarray (Kadane 알고리즘. 마이너스 숫자를 sum에 더할 경우 sum을 더 작게 만들기 때문에  sum이 '0'과 같거나 작으면 새로 시작)

75. Sort Colors (Dutch National Flag 알고리즘. 3개의 포인터 활용. 3개의 가상 파티션을 만들어서 정렬)

121. Best Time to Buy and Sell Stock 

48. Rotage Image (시계방향으로 90도 회전한 매트릭스의 열은 기존의 행의 역순과 같음. 매트릭스의 행을 열로 바꾸고 열을 행으로 바꾼 뒤 행을 reverse. 행을 열로 바꿀 때 반복문 조건 주의)

56. Merge Intervals (한번만 순회하면서 다음 인터벌의 시작이 현재 인터벌안에 속할 경우 현재 비교하는 인터벌 종료값 업데이트 ★★★)

88. Merge Sorted Array 

287. Find the Duplicate Number (링크드 리스트의 slow/fast 포인터 개념을 알아야 풀 수 있음 ★★★ )

74. Search a 2D Matrix (2차원 배열을 가상의 1차원 배열로 생각해서 투포인터 사용. )

50. Pow(x, n) (Binary Exponentiation 수학 개념 알면 좋음 ★★★ )

169. Majority Element (Moore's Voting 알고리즘. 2개의 변수, count, elementToCheck를 선언해서 만약 count가 '0'이면 현재 값을 elementToCheck에 저장. 만약 현재 값과 elementToCheck와 같으면 count++, 아니면 count--)

222. Majority Element 2 (Moore's Voting 알고리즘. 4개의 변수를 선언해서 문제를 품)

62. Unique Paths (다이나믹 프로그래밍)

493. Reverse Pairs (merge sort 중간에 필요 로직 추가★★★★)

1. Two Sum 

18. 4Sum (정렬한 다음에 i, j 고정 후 k, l에 대해 투포인터 사용)

128. Longest Consecutive Sequence (set 자료구조 활용. num - 1를 확인해서 만약 현재 비교하는 숫자보다 작은 숫자가 있으면 다음 값 확인. 없으면 연속된 숫자 확인)

3. Longest Substring Without Repeating Characters

238. Product of Array Except Self (prefix, suffix sum 개념 활용)

3070. Count Submatrices with Top-Left Element and Sum Less Than k (submatrices를 구해야 해서 queue를 활용한 bfs로는 풀 수 없고, prefix sum 활용 필요)

42. Trapping Rain Water (prefix max/suffix max를 찾아서 풀 수도 있지만 투포인터 또는 monotonic stack 개념을 활용해서 풀 수도 있음) 

 

프로그래머스

교점에 별 만들기

삼각 달팽이

거리두기 확인하기

행렬의 곱셈

 

 

 

 

 

 

참고자료

도서: 코딩 인터뷰 완전 분석

도서: 프로그래머스 코딩 테스트 문제 풀이 전략 (자바편)

https://github.com/jwasham/coding-interview-university?tab=readme-ov-file#arrays

https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems