| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- ekskubecost
- CUK
- 파이썬
- AWS
- karpenter
- 프로그래머스
- homelab
- BFS
- kubecostinstall
- ci/cd
- eks비용
- Whatever
- DFS
- CI
- kubecost설치
- 커뮤니티
- 쿠버네티스
- GDSC
- kubecost
- GithubActions
- k8s
- 나동빈
- 비용최적화
- 설치
- eks
- GDGCampusKorea
- Python
- 코테
- AwsCloudClubs
- GDG
- Today
- Total
촬리의늘솔길
프로그래머스 문제풀이 2,3,4,5주차 - 클클 알고리즘 TF 정리 본문
다 노션에 정리해둬서 부랴부랴 옮겨봤다.
덧칠하기
벽을 1미터 길이의 구역 n개로 나누고, 각 구역에 왼쪽부터 순서대로 1번부터 n번까지 번호를 붙였습니다. 그리고 페인트를 다시 칠해야 할 구역들을 정했습니다.
벽에 페인트를 칠하는 롤러의 길이는 m미터이고, 롤러로 벽에 페인트를 한 번 칠하는 규칙은 다음과 같습니다.
- 롤러가 벽에서 벗어나면 안 됩니다.
- 구역의 일부분만 포함되도록 칠하면 안 됩니다.
즉, 롤러의 좌우측 끝을 구역의 경계선 혹은 벽의 좌우측 끝부분에 맞춘 후 롤러를 위아래로 움직이면서 벽을 칠합니다. 현재 페인트를 칠하는 구역들을 완전히 칠한 후 벽에서 롤러를 떼며, 이를 벽을 한 번 칠했다고 정의합니다.
한 구역에 페인트를 여러 번 칠해도 되고 다시 칠해야 할 구역이 아닌 곳에 페인트를 칠해도 되지만 다시 칠하기로 정한 구역은 적어도 한 번 페인트칠을 해야 합니다. 예산을 아끼기 위해 다시 칠할 구역을 정했듯 마찬가지로 롤러로 페인트칠을 하는 횟수를 최소화하려고 합니다.
정수 n, m과 다시 페인트를 칠하기로 정한 구역들의 번호가 담긴 정수 배열 section이 매개변수로 주어질 때 롤러로 페인트칠해야 하는 최소 횟수를 return 하는 solution 함수를 작성해 주세요.
제한사항
- 1 ≤ m ≤ n ≤ 100,000
- 1 ≤ section의 길이 ≤ n
- 1 ≤ section의 원소 ≤ n
- section의 원소는 페인트를 다시 칠해야 하는 구역의 번호입니다.
- section에서 같은 원소가 두 번 이상 나타나지 않습니다.
- section의 원소는 오름차순으로 정렬되어 있습니다.
section 에 해당하는 원소간의 길이가 페인트 롤러 길이보다 작거나 같다면
해당하니까 원소에서 빼고
횟수 추가
처음에 생각한 것
def solution(n, m, section):
for i in (1,len(section)):
if section[i] - section[i-1] <= m :
answer += 1
section.remove(section[i])
section.remove(section[i-1])
return answer
빼면 되는줄 ;;
너무 간만에 풀어서 반복문도 낯설지경이다
조금 더 생각한 것
def solution(n, m, section):
answer =0
check =0
for num in section:
if (num > check):
check = num+m -1
answer +=1
return answer
규칙이 있다.
section = [ 2,3,6] 이고 , m이 4라면
2에서 시작해서 칠할때 2+4-1 = 5 까지만 칠해진다.
3은 < 5 이므로 카운트 추가 안되고
6>5 이므로 카운트 추가된다. 정답은 요렇게…
다른 풀이
나와 가장 비슷한 풀이인데,, 이해가 좀 안되는데 이해를 좀 해야겠음
def solution(n, m, section):
answer = 1 # 칠하는 횟수
paint = section[0] # 덧칠 시작점
for i in range(1, len(section)):
if section[i] - paint >= m:
answer += 1
paint = section[i]
return answer
요격 시스템
문제 설명
A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한 사항
- 1 ≤ targets의 길이 ≤ 500,000
- targets의 각 행은 [s,e] 형태입니다.
- 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
- 0 ≤ s < e ≤ 100,000,000
입출력 예
targets result
| [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]] | 3 |
입출력 예 설명
위 그림과 같이 최소 세 번의 요격 미사일 발사로 전부 방어할 수 있습니다.
문제 풀이
targets 배열에 포함이 안되어야 함 요격 위치가
그리구 최대한 많은 배열을 처리(?) 할 수 있는 위치어야 함
앞선 문제랑 비슷한데….
최대한 많은 배열의 구간에 포함되는. .. 숫자
이걸 어떻게 구하죠
- 일단 정렬을 해야 할 것 같다.
- 근데 뭘 기준으로 정렬해야하는지… ?
- 그냥 정렬해도되는건지
(풀다 말아서 코드가 없네요)
성격검사
https://school.programmers.co.kr/learn/courses/30/lessons/118666
3,2,1,0,1,2,3
제한사항
- 1 ≤ survey의 길이 ( = n) ≤ 1,000
- survey의 원소는 "RT", "TR", "FC", "CF", "MJ", "JM", "AN", "NA" 중 하나입니다.
- survey[i]의 첫 번째 캐릭터는 i+1번 질문의 비동의 관련 선택지를 선택하면 받는 성격 유형을 의미합니다.
- survey[i]의 두 번째 캐릭터는 i+1번 질문의 동의 관련 선택지를 선택하면 받는 성격 유형을 의미합니다.
- choices의 길이 = survey의 길이
- choices[i]는 검사자가 선택한 i+1번째 질문의 선택지를 의미합니다.
- 1 ≤ choices의 원소 ≤ 7
1 매우 비동의 2 비동의 3 약간 비동의 4 모르겠음 5 약간 동의 6 동의 7 매우 동의
입출력 예
survey choices result
| ["AN", "CF", "MJ", "RT", "NA"] | [5, 3, 2, 7, 5] | "TCMA" |
| ["TR", "RT", "TR"] | [7, 1, 3] | "RCJA" |
지표 번호 성격 유형
| 1번 지표 | 라이언형(R), 튜브형(T) |
| 2번 지표 | 콘형(C), 프로도형(F) |
| 3번 지표 | 제이지형(J), 무지형(M) |
| 4번 지표 | 어피치형(A), 네오형(N) |
A: 비동의 N : 동의
5인 경우 → N
C : 비동의 F : 동의
3인경우 → C
M J → M
R T → T
N A 5인경우→ A
알파벳 숫자로 A > N 이니까 A
근데 여기서말하는 점수가 5가 점수가 아니라,, 약간 동의라서 1점임
A 와 N 둘 다 1점임
TR
T : 비동의 ,R : 동의
if ) 1,2,3 ⇒ 비동의
1,2,3 점수는 3,2,1
else if ) 5,6,7 ⇒ 동의
5,6,7 점수는 1,2,3
else) 4
4는 0 → 점수 0 넣기
지표에 점수 추가하는건가
지표 인덱스는 정해져있으니까..?
풀이 고민
이거 2차원 배열…에 튜플로….로 해야겠다. visited = [[0] *4 for _ in range(3))]
인덱스에 따른 값 ,
(R , 0) T , 0
| C , 0 | F , 0 |
| J , 0 | M , 0 |
| A , 0 | N , 0 |
visited = [[('R', 0), ('T', 0)], [('C', 0), ('F', 0)], [('J', 0), ('M', 0)], [('A', 0), ('N', 0)]]
# choices[i] > 4 인 경우 점수를 추가하는 로직
for i in range(len(visited)):
for j in range(len(visited[i])):
char_value, num_value = visited[i][j]
if choices[i] > 4:
if char_value == survey[i][1]:
num_value += (choices[i] - 4)
else:
if char_value == survey[i][0]:
num_value += (4 - choices[i])
visited[i][j] = (char_value, num_value)
answer = ""
이렇게 하고 각 값마다의 num_value 를 비교해서 숫자가 더 크면 그 char_value값을 answer 에 더함
만약 숫자가 같다면, 문자가 사전순으로 더 빠른 char_value을 answer 에 더한다.
# 각 행에 대해 num_value가 가장 큰 char_value를 answer에 추가, 같을 경우 사전순으로 빠른 char_value 추가
for row in visited:
# num_value 기준으로 정렬, 같으면 char_value 사전순으로 정렬
sorted_row = sorted(row, key=lambda x: (-x[1], x[0]))
answer += sorted_row[0][0]
return answer
일단 요렇게 짰는데 잘 될지는 모르겠음..
일단 단단히 잘못짠것같은데
다른사람 풀이
from collections import defaultdict
def solution(survey, choices):
indicator = [('R', 'T'), ('C', 'F'), ('J', 'M'), ('A', 'N')]
answer = ''
personality = defaultdict(int)
for s, c in zip(survey, choices):
if c < 4:
personality[s[0]] += (4 - c)
elif c > 4:
personality[s[1]] += (c - 4)
for i in indicator:
if personality[i[0]] >= personality[i[1]]:
answer += i[0]
else:
answer += i[1]
return answer
신기한 다른사람 풀이 22
def solution(설문_조사_배열, 선택지_배열):
지표 = {}
지표['RT'] = 지표['TR'] = {'R': 0, 'T': 0,}
지표['FC'] = 지표['CF'] = {'C': 0, 'F': 0,}
지표['MJ'] = 지표['JM'] = {'J': 0, 'M': 0,}
지표['AN'] = 지표['NA'] = {'A': 0, 'N': 0,}
점수 = {
'매우 비동의': 3,
'비동의': 2,
'약간 비동의': 1,
'모르겠음': 0,
'약간 동의': 1,
'동의': 2,
'매우 동의': 3,
}
비동의 = [1, 2, 3]
동의 = [5, 6, 7]
선택지 = {
1: '매우 비동의',
2: '비동의',
3: '약간 비동의',
4: '모르겠음',
5: '약간 동의',
6: '동의',
7: '매우 동의',
}
answer = ''
for 인덱스 in range(len(설문_조사_배열)):
비동의_캐릭터, 동의_캐릭터 = 설문_조사_배열[인덱스]
if 선택지_배열[인덱스] in 비동의:
지표[설문_조사_배열[인덱스]][비동의_캐릭터] += 점수[선택지[선택지_배열[인덱스]]]
continue
if 선택지_배열[인덱스] in 동의:
지표[설문_조사_배열[인덱스]][동의_캐릭터] += 점수[선택지[선택지_배열[인덱스]]]
결과_배열 = [지표['RT'].items(), 지표['FC'].items(), 지표['MJ'].items(), 지표['AN'].items()]
정렬된_배열 = []
for 결과 in 결과_배열:
정렬된_배열.append(sorted(결과, key=lambda x: -x[1]))
return ''.join([캐릭터_점수_튜플[0] for [캐릭터_점수_튜플, _] in 정렬된_배열])
미로탈출
https://school.programmers.co.kr/learn/courses/30/lessons/159993
한칸에 1초, 최단거리(시간)을 구하는 문제
bfs dfs 쓰는거고
S 를찾은다음에 → L
L → E 를 찾으면 된다.
How?
재귀,,
bfs
queue 사용..
(온전히 내 힘으로 풀지 못하였다 )
- 고민 : 방문배열을 써야하는가 → 그랬다.
- bfs 풀이에 조금 더 익숙해져야 할 필요성이 있다.
from collections import deque
def solution(maps):
answer = 0
open = False
visited = [[0] *len(maps[0]) for _ in range(len(maps))]
for i,item in enumerate(maps):
for j, char in enumerate(item) :
if char == 'S':
start = (i,j)
visited[i][j] =1
break
q = deque()
q.append((start[0], start[1]))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q:
x, y = q.popleft()
if maps[x][y] == 'L' and not open:
answer += visited[x][y]
open = True
visited = [[0] *len(maps[0]) for _ in range(len(maps))]
visited[x][y] = 1
q = deque()
q.append((x, y))
continue
if maps[x][y] == 'E' and open:
answer += visited[x][y]
return answer - 2 # 시작점 + 레버
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if nx in range(len(maps)) and ny in range(len(maps[0])):
if not visited[nx][ny] and maps[nx][ny] != 'X':
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
answer = -1
return answer
마법의 엘리베이터
https://school.programmers.co.kr/learn/courses/30/lessons/148653
0층이 가장 아래
0보다 작으면 안움직임
버튼한번당 마법의 돌 1개 사용
최소 마법의 돌 개수
최적의 조합을 찾는…
엘베가 있는 층 : storey
마법의 돌 최솟값 : answer
제한사항
- 1 ≤ storey ≤ 100,000,000
입출력 예
10, - 1
6 - 6
20 - 2
4 - 4
6
12
10 -1
2 - 2
20
8
18
20
2
15
10 -1
5 -5
6
20 -2
5 -5
7
storey result
| 16 | 6 |
| 2554 | 16 |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
입출력 예 #2
- 1, +100이 적힌 버튼을 4번, +10이 적힌 버튼을 5번, -1000이 적힌 버튼을 3번 누르면 0층에 도착 할 수 있습니다. 그러므로 16을 return 합니다.
고민과정
그리디인가! 거스름돈 문제같은 느낌쓰 근데이제 거스름돈보다는 어려운
시행착오 1 )
def solution(storey):
answer = 0
storey_str = str(storey)
storey_len = len(storey_str) -1
n = storey // (10 ** storey_len)
if storey % 10 > 5 :
answer += (n+1)
for i in range(storey_len):
answer += ((n+1) * (10 ** storey_len) - storey) // (10 ** (storey_len -i))
else :
answer += n
for i in range(storey_len):
answer += ((n) * (10 ** storey_len)) // (10 ** (storey_len - i))
return answer
요령이 없어서 그냥 .. 2554 면 가장 가까운 10의 거듭제곱이 10^3 * 3 인걸 아니까 어거지로 계산해서 해보려고 했음
안되는듯
다른 방법을 생각해보자
시행착오 2 )
(생각몬함)
레벨 0
한번만등장한 문자
이거 a~z 배열 중에 일치하는 것 있는지 확인하고
만약 그 배열의 값이 1인것들만 answer 에 담고
정렬해서 return
와 파이썬에 이런게 있음
Python 문자열에서 문자의 발생 횟수 계산
이 게시물은 Python에서 문자열의 문자 발생 횟수를 계산하는 방법에 대해 설명합니다.
1. 사용 str.count() 기능
간단하고 효율적인 솔루션은 문자열에서 문자의 총 발생 횟수를 얻는 것입니다. str.count() 기능. 이것은 문자열에서 단일 문자를 계산하는 가장 좋은 솔루션입니다.
if __name__ == '__main__':
s = "ABADACB"
n = s.count('A')
print(n) # 3
def solution(s):
answer = ''
for value in 'abcdefghijklmnopqrstuvwxyz':
if s.count(value) == 1:
answer += value
return answer
레벨1
키패드누르기
https://school.programmers.co.kr/learn/courses/30/lessons/67256
문제)
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
- 4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성
[제한사항]
- numbers 배열의 크기는 1 이상 1,000 이하입니다.
- numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
- hand는 "left" 또는 "right" 입니다.
- "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
- 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
풀이
아니 이게 레벨 1 ..? ……….
- 상하좌우는 생각보다 그렇게 중요하지는 않은듯.. 거리 계산용도 인듯?
- 147* → 왼
- 369# → 오
- 2580 → 왼,오 의 위치를 파악해서 가까운 손으로 누르기
시행착오 1)
left_array = [1,4,7]
right_array = [3,6,9]
middle_array = [ 2,5,8,0]
present = [*,#]
for value in numbers:
if value in left_array:
answer += ‘L’
present[0] = value
elif value in right_array:
answer += ‘R’
present[1] = value
else :
이게 제일 난관이다 어떻게 거리를 계산하지 ..?
좌표로 하면 다 거리가 1씩 이니까, 그렇게 할 수 있겠다.
그렇다면 딕셔너리를 써야 할 것 같은데
시행착오 2)
dic = {1: [0, 0], 2: [0, 1], 3: [0, 2],
4: [1, 0], 5: [1, 1], 6: [1, 2],
7: [2, 0], 8: [2, 1], 9: [2, 2],
'*':[3, 0], 0: [3, 1], '#': [3, 2]}
left_locate = dic[’*’]
right_locate = dic[’#’]
left_array = [1,4,7]
right_array = [3,6,9]
for value in numbers:
if value in left_array:
answer += ‘L’
left_locate = dic[value]
elif value in right_array:
answer += ‘R’
right_locate = dic[value]
else:
left_dis, right_dis = 0,0
present = dic[value]
left_dis = abs(present[0] - left_locate[0]) + abs(present[1] - left_locate[1])
right_dis = abs(present[0] - right_locate[0]) + abs(present[1] - right_locate[1])
if left_dis < right_dis:
answer += ‘L’
left_locate = dic[value]
elif right_dis > left_dis :
answer += ‘R’
right_locate = dic[value]
else :
if hand == “right”:
answer += ‘R’
right_locate = dic[value]
else :
answer +=’L’
left_locate = dic[value]
return answer
def solution(numbers, hand):
answer = ''
dic = {1: [0, 0], 2: [0, 1], 3: [0, 2],
4: [1, 0], 5: [1, 1], 6: [1, 2],
7: [2, 0], 8: [2, 1], 9: [2, 2],
'*':[3, 0], 0: [3, 1], '#': [3, 2]}
left_locate = dic['*']
right_locate = dic['#']
left_array = [1,4,7]
right_array = [3,6,9]
for value in numbers:
if value in left_array :
answer +='L'
left_locate = dic[value]
elif value in right_array :
answer +='R'
right_locate = dic[value]
else:
left_dis=0
right_dis=0
present = dic[value]
left_dis = abs(present[0] - left_locate[0])+abs(present[1] - left_locate[1])
right_dis = abs(present[0] - right_locate[0]) + abs(present[1] - right_locate[1])
if left_dis < right_dis:
answer += 'L'
left_locate = dic[value]
elif right_dis > left_dis:
answer += 'R'
right_locate = dic[value]
else :
if hand == "right":
answer += 'R'
right_locate = dic[value]
else:
answer += 'L'
left_locate = dic[value]
return answer
뭐가 문제일까!
ㅇ와 바보다 left거리 < right 거리
이부분을 부등호를 잘못쓴듯
def solution(numbers, hand):
answer = ''
dic = {1: [0, 0], 2: [0, 1], 3: [0, 2],
4: [1, 0], 5: [1, 1], 6: [1, 2],
7: [2, 0], 8: [2, 1], 9: [2, 2],
'*':[3, 0], 0: [3, 1], '#': [3, 2]}
left_locate = dic['*']
right_locate = dic['#']
left_array = [1,4,7]
right_array = [3,6,9]
for value in numbers:
if value in left_array :
answer +='L'
left_locate = dic[value]
elif value in right_array :
answer +='R'
right_locate = dic[value]
else:
left_dis=0
right_dis=0
present = dic[value]
left_dis = abs(present[0] - left_locate[0])+abs(present[1] - left_locate[1])
right_dis = abs(present[0] - right_locate[0]) + abs(present[1] - right_locate[1])
if left_dis < right_dis:
answer += 'L'
left_locate = dic[value]
elif left_dis > right_dis:
answer += 'R'
right_locate = dic[value]
else :
if hand == "right":
answer += 'R'
right_locate = dic[value]
else:
answer += 'L'
left_locate = dic[value]
return answer
레벨2
전력망 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/86971
문제 )
n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 2 이상 100 이하인 자연수입니다.
- wires는 길이가 n-1인 정수형 2차원 배열입니다.
- wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
- 1 ≤ v1 < v2 ≤ n 입니다.
- 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.
어엇 이거 예전에 풀었던것같은데 기억이안남
풀이 )
예시들의 규칙을 찾아보면,, 연결된 가짓수(일종의 가중치..인가?) 가 많은 것들을 위주로 끊는다.
하나씩 더해나가는 것도 전체노드를 알고있다고 했을때는 상관이 없다.
재귀의 과정을 통해서 끝까지 갔을 때 1을 리턴하는 재귀가 있다.
그렇게 되면,
각 노드에 연결된 노드의 수는 방문배열로 해결할 수 있을 것 같은데,
문제는.. 저기서 끊으면 남는 송전탑 개수( 트리 노드의 수 ) 를 어떻게 세느냐임..
방문된 수가 제일 크거나 같은 배열을 찾아서 [x,y]
방문배열 초기화 하고,
dfs (재귀) 탐색을 통해서, [x] 와 연결된 노드들의 수 count1 를 센다
이때 이미 방문한 노드라면 +1 을 안하면 되는 것,
그리고 [y] 와 연결된 노드들의 개수 count2 도 센다
그래서 ! count1 - count2 하면 답이나옴!
이걸 이제 ㄱ..구현 해야하는데! 하하!
def solution(n, wires):
answer = -1
visit_count = {}
visited = [False] * (n+1)
countA = 0
countB = 0
# wires 배열을 순회하며 각 노드의 방문 횟수를 업데이트합니다.
for wire in wires:
x, y = wire
visit_count[x] = visit_count.get(x, 0) + 1
visit_count[y] = visit_count.get(y, 0) + 1
# 방문 횟수를 기준으로 내림차순 정렬합니다.
# sorted() 함수는 기본적으로 오름차순 정렬을 수행하므로, reverse=True 옵션을 사용하여 내림차순으로 정렬합니다.
sorted_visit_count = sorted(visit_count.items(), key=lambda item: item[1], reverse=True)
# 가장 많이 방문한 노드와 그 방문 횟수를 얻습니다.
max_visit_node, max_visit = sorted_visit_count[0]
# 두번째로 많이 방문한 노드
second_visit_node, second_visit = sorted_visit_count[1]
def dfs(wires,v,visited):
visited[v] = True
for wire in wires:
x,y =wire
if visited[x] = False:
count +=1
dfs(wires,x,visited)
elif visited[y] = False:
countB +=1
dfs(wires,y,visited)
answer = abs(countA-countB) -2
return answer
def dfs(v,wires,visited,count):
visited[v] = True
for wire in wires:
x,y = wire
if visited[x]==False:
count +=1
dfs(x,wires,visited,count)
if visited[y]==False:
count+=1
dfs(y,wires,visited,count)
return count
def solution(n, wires):
answer = -1
visit_count = {}
visited = [False] * (n+1)
countA = 0
countB = 0
count =0
for wire in wires:
x,y = wire
visit_count[x] = visit_count.get(x,0) +1
visit_count[y] = visit_count.get(y,0) +1
sorted_visit_count = sorted(visit_count.items(), key=lambda item: item[1], reverse=True)
max_visit_node, max_visit = sorted_visit_count[0]
second_visit_node, second_visit = sorted_visit_count[1]
countA = dfs(max_visit_node,wires,visited,count) -1
countB = dfs(second_visit_node,wires,visited,count) -1
answer = abs(countA-countB)
return answer
틀림 ㅇㅇㅇ
다른 사람의 정답
def DFS(v, graph, visited, check_link):
cnt = 1
visited[v] = True
for adj_v in graph[v]:
# 방문 이력이 없고, 그 간선이 임시로 없앤 간선이 아닌 경우
if visited[adj_v] == False and check_link[v][adj_v]:
cnt += DFS(adj_v, graph, visited, check_link)
return cnt
def solution(n, wires):
answer = INF
# 없앤 간선인지 아닌지 체크 값이 들어있는 리스트
check_link = [[True]*(n+1) for _ in range(n+1)]
graph = [[] for _ in range(n+1)]
cnt_all = []
for a, b in wires:
graph[a].append(b)
graph[b].append(a)
for a, b in wires:
visited = [False]*(n+1)
check_link[a][b] = False # a-b 간선 끊기
cnt_a = DFS(a, graph, visited, check_link)
cnt_b = DFS(b, graph, visited, check_link)
check_link[a][b] = True # a-b 간선 다시 연결
answer = min(answer, abs(cnt_a - cnt_b))
return answer
뭔가 거의 다 왔는데! (?) 쩝
없앤 간선을 확인하지 않은게 문제인듯
그냥 -1 만 하면 되는줄,,,
알게된 것
lambda .. 볼때마다 새로움
람다(lambda) 총 정리, key sort, key 정렬
visit_count.get(x, 0) + 1
x라는 키가 visit_count 사전에 존재하면 그에 해당하는 값을 반환합니다. 만약 x라는 키가 사전에 존재하지 않는 경우에는 get 메서드의 두 번째 인자로 전달된 기본값 0을 반환
아직도 모르는것
union-find 쓸 줄 모른다.