[프로그래머스💯] 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 > 다른 사람의 풀이
해답) def solution(n, computers): check = [1] * n network = 0 def find(Coms, Com, Com_index): check[Com_index] = 0 for objCom_i,obj_com in enumerate(Com): if obj_com: if check[objCom_i]: find(Coms, Coms[objCom_i], objCom_i) for index, com in enumerate(computers): if check[index]: find(computers, com,index) network += 1 return network 풀이) * check = 컴퓨터가 네트워크에 포함되었는지 여부를 반환합니다. (1: 아직안됨 0: 연결됨) 1. 한..
2020. 1. 16.
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트
해답) def solution(people, limit): people.sort() boat = 0 last_index = len(people)-1 for i in range(last_index): for j in range(last_index, i-1, -1): boat += 1 last_index -= 1 if people[i] + people[j] 무거운사람에게 1인용 보트를 준 후(boat +=1) 방금 검사했던 가벼운사람과 그 다음 무거운 사람을 다시 검사합니다. 2-2. 같이 탈 수 있을 경우 => 두 사람에게 보트를 1개 준 후(boat +=1), 다음으로 가벼운사람과 다음으로 무거운 사람을 검사합니다. 3. 루프가 다 돌았으면 , boat를 리턴합니다. * 첫번째 for문이 처음 설정된 l..
2020. 1. 12.
[프로그래머스💯] 코딩테스트 연습 > 스택/큐 > 주식가격 / *스택 활용
해답) def solution(prices): time = 0 stk = [(0,prices[0])] res = [0] * len(prices) print(stk[0]) for i, v in enumerate(prices[1:]): # 들어오려는 숫자가 더 작은 경우 while len(stk) > 0 and v < stk[len(stk)-1][1]: for (s_i, s_v) in stk: res[s_i] += 1 # 스택 안에있던 요소들 시간 증가 stk.pop() stk.append((i+1,v)) while stk: # 남아있는 것들 시간 넣어주기 (i,v) = stk.pop() res[i] += time time += 1 return res 1. 스택을 반드시 이용하겠다는 마인드로 풀었습니다. 2..
2020. 1. 11.
[프로그래머스💯] 코딩테스트 연습 > 스택/큐 > 탐욕법
풀이) 이 문제는 '()' 가 나왔을 때 레이저를 쏜다. 레이저를 쏘는 시점에 쌓여있던 막대기 수 만큼 부분 막대기가 생성될 것이고, '()' 가 아닌 '))' (이전 문자가 '(' 인 경우) 이라면 막대기 층이 하나 낮아지므로 막대기가 1개 의 부분막대기가 생성된다. 요약하자면 ')' 가 나왔을 때 case A : 쌓여있던 막대기 수-1 만큼 블럭 result를 늘려준다. - 막대기 수 - 1 인 이유는 '()' 에서 나오는 '(' 도 쌓인 막대기로 계산한다고 가정 때문. case B : result 를 1만큼만 늘려주고 막대기를 하나 줄인다. def solution(arrangement): stk = [] count = 0 # 스택에 들어가있는 ( 수 recent = 0 # 이전 문자가 '(' = 0..
2019. 12. 29.
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 체육복
해답) def solution(n, lost, reserve): # 그리디한 알고리즘 이므로 소트를 해줘야한다. reserve.sort() # 여벌이 있는 친구가 도난당한 경우 for i in reserve: if i in lost: lost.remove(i) reserve[reserve.index(i)] = -5 # 체육복을 빌려주는 경우 for i in reserve: if i-1 in lost: lost.remove(i-1) elif i+1 in lost: lost.remove(i+1) return n-len(lost) * 알고리즘 순서 여벌이 있는 친구들을 기준으로 (정렬이 되어있음을 가정) 빌려줄수있는 앞번호 부터 쭈욱 빌려준다. 1. 자신이 잃어버린경우 2. 자신의 앞번호가 잃어버린 경우 3...
2019. 11. 25.
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 조이스틱
해답) def solution(st): res = 0 A_Count =0 A_Max = 0 # 가장 긴 A묶음의 A 수 A_StartIndex = 0 A_EndIndex = 0 vertical_count = 0 start = True for i,v in enumerate(st): # 연속해서 나온 A 횟수 검사 if v == 'A' and start == False : A_Count += 1 if A_Count > A_Max: A_Max = A_Count A_EndIndex = i else: A_Count = 0 # 알파벳이 N보다 크면 위로넘기는게 빠르다 if ord(v) > ord('N'): count = ord('Z')-ord(v)+1 else: count = ord(v) - ord('A') res..
2019. 11. 24.
[프로그래머스💯] 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 > 다른 사람의 풀이
해답) def solution(n, computers): check = [1] * n network = 0 def find(Coms, Com, Com_index): check[Com_index] = 0 for objCom_i,obj_com in enumerate(Com): if obj_com: if check[objCom_i]: find(Coms, Coms[objCom_i], objCom_i) for index, com in enumerate(computers): if check[index]: find(computers, com,index) network += 1 return network 풀이) * check = 컴퓨터가 네트워크에 포함되었는지 여부를 반환합니다. (1: 아직안됨 0: 연결됨) 1. 한..
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트
해답) def solution(people, limit): people.sort() boat = 0 last_index = len(people)-1 for i in range(last_index): for j in range(last_index, i-1, -1): boat += 1 last_index -= 1 if people[i] + people[j] 무거운사람에게 1인용 보트를 준 후(boat +=1) 방금 검사했던 가벼운사람과 그 다음 무거운 사람을 다시 검사합니다. 2-2. 같이 탈 수 있을 경우 => 두 사람에게 보트를 1개 준 후(boat +=1), 다음으로 가벼운사람과 다음으로 무거운 사람을 검사합니다. 3. 루프가 다 돌았으면 , boat를 리턴합니다. * 첫번째 for문이 처음 설정된 l..
[프로그래머스💯] 코딩테스트 연습 > 스택/큐 > 주식가격 / *스택 활용
해답) def solution(prices): time = 0 stk = [(0,prices[0])] res = [0] * len(prices) print(stk[0]) for i, v in enumerate(prices[1:]): # 들어오려는 숫자가 더 작은 경우 while len(stk) > 0 and v < stk[len(stk)-1][1]: for (s_i, s_v) in stk: res[s_i] += 1 # 스택 안에있던 요소들 시간 증가 stk.pop() stk.append((i+1,v)) while stk: # 남아있는 것들 시간 넣어주기 (i,v) = stk.pop() res[i] += time time += 1 return res 1. 스택을 반드시 이용하겠다는 마인드로 풀었습니다. 2..
[프로그래머스💯] 코딩테스트 연습 > 스택/큐 > 탐욕법
풀이) 이 문제는 '()' 가 나왔을 때 레이저를 쏜다. 레이저를 쏘는 시점에 쌓여있던 막대기 수 만큼 부분 막대기가 생성될 것이고, '()' 가 아닌 '))' (이전 문자가 '(' 인 경우) 이라면 막대기 층이 하나 낮아지므로 막대기가 1개 의 부분막대기가 생성된다. 요약하자면 ')' 가 나왔을 때 case A : 쌓여있던 막대기 수-1 만큼 블럭 result를 늘려준다. - 막대기 수 - 1 인 이유는 '()' 에서 나오는 '(' 도 쌓인 막대기로 계산한다고 가정 때문. case B : result 를 1만큼만 늘려주고 막대기를 하나 줄인다. def solution(arrangement): stk = [] count = 0 # 스택에 들어가있는 ( 수 recent = 0 # 이전 문자가 '(' = 0..
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 체육복
해답) def solution(n, lost, reserve): # 그리디한 알고리즘 이므로 소트를 해줘야한다. reserve.sort() # 여벌이 있는 친구가 도난당한 경우 for i in reserve: if i in lost: lost.remove(i) reserve[reserve.index(i)] = -5 # 체육복을 빌려주는 경우 for i in reserve: if i-1 in lost: lost.remove(i-1) elif i+1 in lost: lost.remove(i+1) return n-len(lost) * 알고리즘 순서 여벌이 있는 친구들을 기준으로 (정렬이 되어있음을 가정) 빌려줄수있는 앞번호 부터 쭈욱 빌려준다. 1. 자신이 잃어버린경우 2. 자신의 앞번호가 잃어버린 경우 3...
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 조이스틱
해답) def solution(st): res = 0 A_Count =0 A_Max = 0 # 가장 긴 A묶음의 A 수 A_StartIndex = 0 A_EndIndex = 0 vertical_count = 0 start = True for i,v in enumerate(st): # 연속해서 나온 A 횟수 검사 if v == 'A' and start == False : A_Count += 1 if A_Count > A_Max: A_Max = A_Count A_EndIndex = i else: A_Count = 0 # 알파벳이 N보다 크면 위로넘기는게 빠르다 if ord(v) > ord('N'): count = ord('Z')-ord(v)+1 else: count = ord(v) - ord('A') res..