티스토리 뷰
Problem
Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.
A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
Example 1:
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]
Example 2:
Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]
Constraints:
- n == grid.length == grid[i].length
- 1 <= n <= 200
- 1 <= grid[i][j] <= 10^5
Solution
2차원 정수 배열 grid가 주어졌을 때, 행과 열이 같은 원소를 갖는 (ri, cj) 쌍의 개수를 계산하는 문제입니다.
package io.lcalmsky.leetcode.equal_row_and_column_pairs;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int equalPairs(int[][] grid) {
int n = grid.length;
Map<String, Integer> map = new HashMap<>();
for (int[] row : grid) {
String rowString = Arrays.toString(row);
map.merge(rowString, 1, Integer::sum);
}
int pairs = 0;
for (int i = 0; i < n; i++) {
int[] col = new int[n];
for (int j = 0; j < n; j++) {
col[j] = grid[j][i];
}
String colString = Arrays.toString(col);
pairs += map.getOrDefault(colString, 0);
}
return pairs;
}
}
- equalPairs 함수는 grid 배열을 입력으로 받습니다.
- n 변수에는 grid 배열의 길이, 즉 행 또는 열의 개수가 저장됩니다.
- 빈 HashMap 객체인 map을 생성합니다. 이 맵은 행의 값을 문자열로 변환하여 저장하고, 해당 문자열이 몇 번 등장하는지를 세는데 사용됩니다.
- grid 배열을 순회하면서 각 행에 대해 다음을 수행합니다.
- Arrays.toString() 메서드를 사용하여 행 배열을 문자열로 변환합니다. 이 문자열은 해당 행을 나타내는 고유한 키가 됩니다.
- map.merge(rowString, 1, Integer::sum)을 호출하여 map에 행을 키로 가지는 값(등장 횟수)을 추가합니다. 만약 이미 해당 키가 존재하면, 기존 값과 1을 더한 값을 저장합니다.
- 이 과정을 통해 각 행의 등장 횟수가 map에 저장됩니다.
- pairs 변수를 0으로 초기화합니다. 이 변수는 최종적으로 반환될 결과값으로, 같은 원소를 갖는 (ri, cj) 쌍의 개수를 나타냅니다.
- grid 배열의 각 열에 대해 다음을 수행합니다:
- 빈 배열 col을 생성합니다. 이 배열은 현재 순회 중인 열의 값을 저장하는데 사용됩니다.
- grid 배열의 각 행에 대해 grid[j][i] 값을 col 배열에 저장합니다. 이로써 col 배열은 현재 순회 중인 열의 값들로 채워지게 됩니다.
- Arrays.toString() 메서드를 사용하여 col 배열을 문자열로 변환합니다. 이 문자열은 현재 순회 중인 열을 나타내는 고유한 키가 됩니다.
- map에서 해당 열에 대한 등장 횟수를 가져옵니다. 만약 colString이 map에 존재하지 않는다면, 0을 가져옵니다.
- pairs 변수에 해당 열의 등장 횟수를 더합니다.
- pairs 변수를 반환하여 같은 원소를 갖는 (ri, cj) 쌍의 총 개수를 반환합니다.
시간 복잡도(Time Complexity)
먼저, for 루프를 통해 grid 배열을 한 번 순회하면서 각 행의 값을 문자열로 변환하고 map에 저장합니다. 이 작업은 O(n^2) 시간이 걸립니다.
그 다음, for 루프를 통해 grid 배열의 열을 순회하면서 col 배열을 생성하고 각 열의 값을 문자열로 변환하고 map에서 해당 열의 등장 횟수를 가져오는 작업을 수행합니다. 이 작업 역시 O(n^2) 시간이 걸립니다.
따라서, 전체 시간 복잡도는 O(n^2) + O(n^2) = O(n^2)입니다.
공간 복잡도(Space Complexity)
map을 사용하여 각 행의 값을 문자열로 변환하고 등장 횟수를 저장합니다. 최악의 경우, map에는 모든 서로 다른 행의 문자열이 저장될 수 있으므로, 공간 복잡도는 O(n^2)입니다.
추가적으로, col 배열을 생성하여 열의 값을 임시로 저장합니다. 이 배열은 열마다 새로 생성되므로 O(n)의 공간을 차지합니다.
따라서, 전체 공간 복잡도는 O(n^2) + O(n) = O(n^2)입니다.
Test
package io.lcalmsky.leetcode.equal_row_and_column_pairs;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SolutionTest {
@Test
void testAll() {
assertAll(
() -> test(new int[][]{{3, 2, 1}, {1, 7, 6}, {2, 7, 7}}, 1),
() -> test(new int[][]{{3, 1, 2, 2}, {1, 4, 4, 5}, {2, 4, 2, 2}, {2, 4, 2, 2}}, 3)
);
}
private void test(int[][] grid, int expected) {
// when
Solution solution = new Solution();
int actual = solution.equalPairs(grid);
// then
assertEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 735. Asteroid Collision (0) | 2023.08.01 |
---|---|
[LeetCode] 2390. Removing Stars From a String (0) | 2023.07.31 |
[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element (0) | 2023.07.29 |
[LeetCode] 1004. Max Consecutive Ones III (0) | 2023.07.28 |
[LeetCode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.07.27 |
- Total
- Today
- Yesterday
- intellij
- 스프링 부트 애플리케이션
- proto3
- r
- 함께 자라기
- spring boot jwt
- gRPC
- spring boot application
- 스프링 부트 회원 가입
- @ManyToOne
- 스프링 데이터 jpa
- spring boot app
- Spring Boot
- 스프링 부트
- Linux
- 알고리즘
- JPA
- Jackson
- Spring Boot JPA
- 스프링부트
- 스프링 부트 튜토리얼
- JSON
- Spring Data JPA
- 헥사고날 아키텍처
- 클린 아키텍처
- 함께 자라기 후기
- Java
- leetcode
- QueryDSL
- Spring Boot Tutorial
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |