일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- String
- 아파치 하둡
- 티스토리챌린지
- 우선순위큐
- 하둡
- 리트코드
- 프로그래머스
- BFS
- 오블완
- 알고리즘
- DP
- 이진탐색
- 문자열
- 코딩테스트
- 분산처리
- 그래프
- 도커
- apache kafka
- programmers
- 아파치 카프카
- docker
- Apache Spark
- 분산
- 카프카
- Apache Hadoop
- Python
- leetcode
- 아파치 스파크
- heapq
- 파이썬
- Today
- Total
래원
[LeetCode] 1267. Count Servers that Communicate (Python) 본문
[LeetCode] 1267. Count Servers that Communicate (Python)
Laewon Jeong 2025. 1. 23. 13:30
난이도: Medium
문제 설명
You are given a map of a server center, represented as a m * n
integer matrix grid
, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.
Return the number of servers that communicate with any other server.
문제 예제
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.
Example 2:
Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.
Example 3:
Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other.
The two servers in the third column can communicate with each other.
The server at right bottom corner can't communicate with any other server.
제한사항
m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1
Solution(솔루션)
def get_answer(row_or_col, n, s):
for i in range(n):
if len(row_or_col[i]) >= 2:
for loc in row_or_col[i]:
s.add(loc)
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
check = defaultdict(bool)
row = [[] for _ in range(n)]
col = [[] for _ in range(m)]
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
row[i].append((i,j))
col[j].append((i,j))
s = set()
get_answer(row, n, s)
get_answer(col, m, s)
return len(s)
처음에는 상하좌우로 이어져있는 서버에 수를 구하라라는 건 줄 알고 그렇게 풀었는데 Wrong Answer라고 알려주었다...
그래서 문제를 다시 보니 같은 row에 있거나 같은 column에 있으면 communication이 가능하다는 것을 알게 되었다.
그래서 코드를 다시 짜기 시작했다.
먼저 server가 있는 위치를 row와 col리스트를 각각 저장했다.
예를들어, grid = [[1,0], [1,1]]과 같을 때 row와 col은 다음과 같이 저장된다.
여기서 이제 len(row[i]) 또는 len(col[i])가 2이상이면 이를 세면 된다.
하지만 위 그림에서 그냥 count하게되면 4라는 답이 나오지만 원하는 답은 3이다.
이는 row와 col에서 중복된 위치(위 그림에서 (1,0))도 같이 count하기 때문에 그렇다.
따라서, set을 이용해 중복된 위치를 제거해주었다.
마지막에는 set의 길이를 반환하여 정답을 맞출 수 있었다.
문제: 1267. Count Servers that Communicate
깃허브: github
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] 2948. Make Lexicographically Smallest Array by Swapping Elements (Python) (0) | 2025.01.25 |
---|---|
[LeetCode] 802. Find Eventual Safe States (Python) (0) | 2025.01.24 |
[LeetCode] 1765. Map of Highest Peak (Python) (0) | 2025.01.22 |
[LeetCode] 2017. Grid Game (Python) (0) | 2025.01.21 |
[LeetCode] 2661. First Completely Painted Row or Column (Python) (0) | 2025.01.20 |