์ฝ๋ฉํ ์คํธ ๊ณ ๋์ Kit์ ์๋ ์ฒซ๋ฒ์งธ ๋ฌธ์ !
์๊ฐ๋ณด๋ค ์ด๋ ต๋ค. ํนํ ๋์ฒ๋ผ ๋ฐฐ์ด๋ก ๊ทธ๋ํ๋ฅผ ๊ตฌํํ๋ ์ต๊ด์ด ์์ผ๋ฉด ใ ใ ใ
๋ฌธ์ ์ค๋ช
n๊ฐ์ ๋ ธ๋๊ฐ ์๋ ๊ทธ๋ํ๊ฐ ์์ต๋๋ค. ๊ฐ ๋ ธ๋๋ 1๋ถํฐ n๊น์ง ๋ฒํธ๊ฐ ์ ํ์์ต๋๋ค. 1๋ฒ ๋ ธ๋์์ ๊ฐ์ฅ ๋ฉ๋ฆฌ ๋จ์ด์ง ๋ ธ๋์ ๊ฐฏ์๋ฅผ ๊ตฌํ๋ ค๊ณ ํฉ๋๋ค. ๊ฐ์ฅ ๋ฉ๋ฆฌ ๋จ์ด์ง ๋ ธ๋๋ ์ต๋จ๊ฒฝ๋ก๋ก ์ด๋ํ์ ๋ ๊ฐ์ ์ ๊ฐ์๊ฐ ๊ฐ์ฅ ๋ง์ ๋ ธ๋๋ค์ ์๋ฏธํฉ๋๋ค.
๋ ธ๋์ ๊ฐ์ n, ๊ฐ์ ์ ๋ํ ์ ๋ณด๊ฐ ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด vertex๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, 1๋ฒ ๋ ธ๋๋ก๋ถํฐ ๊ฐ์ฅ ๋ฉ๋ฆฌ ๋จ์ด์ง ๋ ธ๋๊ฐ ๋ช ๊ฐ์ธ์ง๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ ์ฌํญ
- ๋ ธ๋์ ๊ฐ์ n์ 2 ์ด์ 20,000 ์ดํ์ ๋๋ค.
- ๊ฐ์ ์ ์๋ฐฉํฅ์ด๋ฉฐ ์ด 1๊ฐ ์ด์ 50,000๊ฐ ์ดํ์ ๊ฐ์ ์ด ์์ต๋๋ค.
- vertex ๋ฐฐ์ด ๊ฐ ํ [a, b]๋ a๋ฒ ๋ ธ๋์ b๋ฒ ๋ ธ๋ ์ฌ์ด์ ๊ฐ์ ์ด ์๋ค๋ ์๋ฏธ์ ๋๋ค.
์ ์ถ๋ ฅ ์
n | vertex | return |
6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
์ ์ถ๋ ฅ ์ ์ค๋ช
์์ ์ ๊ทธ๋ํ๋ฅผ ํํํ๋ฉด ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ๊ณ , 1๋ฒ ๋ ธ๋์์ ๊ฐ์ฅ ๋ฉ๋ฆฌ ๋จ์ด์ง ๋ ธ๋๋ 4,5,6๋ฒ ๋ ธ๋์ ๋๋ค.
ํ์ด
- ์ฒ์์ ๋ฐฐ์ด๋ก ๋ง๋ค์ด์ ํ๋ค๊ฐ ๋ญ๊ฐ ์ด์ํ๋ค๋ ๊ฒ์ ๋๋ ใ ใ
- ์ฌ๊ธฐ๊น์ง ์งฐ๋ ์ฝ๋๊ฐ ํ ์ผ3๋ฒ์์ 300ms ๊ฑธ๋ฆฌ๋ฉด์ ์คํจํจ.
- ์ผ๋จ edge๋ฅผ for๋ฌธ์ผ๋ก ํ๋ฒ ๋๊ณ , for๋ฌธ ์์ ์๋ฏธ ์์ด 1000๋ฒ ๋๋ ์ฝ๋๋ฅผ ์คํํด๋ณธ ๊ฒฐ๊ณผ.
- ์ด๋ ๊ฒ ํ๋ฉด ์๋ ๊ฐ ใ ใ ใ
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ์คํจ (0.66ms, 10.3MB)
ํ
์คํธ 2 ใ ์คํจ (1.10ms, 10.1MB)
ํ
์คํธ 3 ใ ์คํจ (3.33ms, 10.2MB)
ํ
์คํธ 4 ใ ์คํจ (27.39ms, 10.2MB)
ํ
์คํธ 5 ใ ์คํจ (117.88ms, 10.5MB)
ํ
์คํธ 6 ใ ์คํจ (282.72ms, 10.5MB)
ํ
์คํธ 7 ใ ์คํจ (1892.57ms, 15.3MB)
ํ
์คํธ 8 ใ ์คํจ (2736.92ms, 17.6MB)
ํ
์คํธ 9 ใ ์คํจ (2885.05ms, 17.7MB)
- ํ๋ ฌ ๋ง๊ณ ๋ค๋ฅธ ๋ฐฉ์์ผ๋ก ๊ทธ๋ํ๋ฅผ ์จ์ผ ํจ.
- ์ ์ ๋ณด๋๊น ๋์ ๋๋ฆฌ๋ก ์์๋ ธ๋ - ์ฐ๊ฒฐ๋ ธ๋ ๋ง๋ค์ด์ ๊ตฌํํ๋ ๊ฑฐ ๋ณธ ๊ฑฐ ๊ธฐ์ต๋ฌ๋ค.
- ์๋ฐฉํฅ์ด๋๊น 2๊ฐ ๋ง๋ค์ด์ผ ํ๊ณ , ๋์ ๋๋ฆฌ ์์ set์ด ๋๋๊ฐ?? ๊ทธ๋ฅ 2์ค ๋ฐฐ์ด...
- ๊ทธ๋ฆฌ๊ณ ๋ํ์ ์นด์ดํฐ...
import collections
def solution(n, edge):
answer = 0
node = [0 for _ in range(n+1)] # ์ต๋จ๊ฒฝ๋ก ์ฒดํฌ
graph = [[] for _ in range(n+1) ]
for s,e in edge: # ์๋ฐฉํฅ ๋
ธ๋
graph[s].append(e)
graph[e].append(s)
queue = collections.deque()
queue.append(1)
while queue:
q = queue.popleft()
gr = graph[q]
for g in gr:
if node[g] == 0:
node[g] = node[q] + 1
queue.append(g)
node[1] = 1
answer = max(node)
cnt_node = collections.Counter(node)
return cnt_node[answer]
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.03ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.04ms, 10.1MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.05ms, 10MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.20ms, 10.4MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.65ms, 10.5MB)
ํ
์คํธ 6 ใ ํต๊ณผ (1.84ms, 10.8MB)
ํ
์คํธ 7 ใ ํต๊ณผ (20.04ms, 16.9MB)
ํ
์คํธ 8 ใ ํต๊ณผ (38.01ms, 20.8MB)
ํ
์คํธ 9 ใ ํต๊ณผ (46.69ms, 19.8MB)
- ๊ณ ์์ ์ฝ๋
- ์ฝ๋ ์ ๊ฐ์ ๊ฑฐ ์์ฐ๊ณ ํ๋ ๋ฐฉ๋ฒ...
def solution(n, edge):
graph =[ [] for _ in range(n + 1) ]
distances = [ 0 for _ in range(n) ]
is_visit = [False for _ in range(n)]
queue = [0]
is_visit[0] = True
for (a, b) in edge:
graph[a-1].append(b-1)
graph[b-1].append(a-1)
while queue:
i = queue.pop(0)
for j in graph[i]:
if is_visit[j] == False:
is_visit[j] = True
queue.append(j)
distances[j] = distances[i] + 1
distances.sort(reverse=True)
answer = distances.count(distances[0])
return answer
์ ํ์ฑ ํ
์คํธ
ํ
์คํธ 1 ใ ํต๊ณผ (0.01ms, 10.2MB)
ํ
์คํธ 2 ใ ํต๊ณผ (0.02ms, 10.3MB)
ํ
์คํธ 3 ใ ํต๊ณผ (0.03ms, 10.3MB)
ํ
์คํธ 4 ใ ํต๊ณผ (0.20ms, 10.1MB)
ํ
์คํธ 5 ใ ํต๊ณผ (0.87ms, 10.6MB)
ํ
์คํธ 6 ใ ํต๊ณผ (2.49ms, 11MB)
ํ
์คํธ 7 ใ ํต๊ณผ (29.41ms, 18.9MB)
ํ
์คํธ 8 ใ ํต๊ณผ (40.27ms, 23.6MB)
ํ
์คํธ 9 ใ ํต๊ณผ (56.52ms, 23.3MB)
์๊ฐ๋ณด๋ค ์ด๋ ต๋ค.
'๊ฒ์ ํ๋ก๊ทธ๋๋ฐ > Python ํ๋ก๊ทธ๋๋ฐ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ๋ก๊ทธ๋๋จธ์ค ์์ (์ฝ๋ฉํ ์คํธ ๊ณ ๋์ Kit, ๊ทธ๋ํ) (0) | 2023.03.06 |
---|---|
ํ๋ก๊ทธ๋๋จธ์ค ์ฌํ๊ฒฝ๋ก (๊น์ด/๋๋น ์ฐ์ ํ์ DFS/BFS) (0) | 2023.03.05 |
ํ๋ก๊ทธ๋๋จธ์ค ์ฐ์ ํ์ค ๋ถ๋ถ ์์ด์ ํฉ (DP) (0) | 2023.03.02 |
ํ๋ก๊ทธ๋๋จธ์ค ๋ง์น ํ๊ธฐ (for๋ฌธ) (0) | 2023.03.02 |
ํ๋ก๊ทธ๋๋จธ์ค ๋ฐํํ๋ฉด ์ ๋ฆฌ (for๋ฌธ, ํ์ด ํผ์ดํฌ) (6) | 2023.03.02 |