[프로그래머스💯] 코딩테스트 연습 > 탐욕법(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.
[프로그래머스💯] 코딩테스트 연습 > 스택,큐 > 기능개발
스택, 큐는 이용하지 않고 풀었습니다! time 변수를 만들어서 시간 초를 고려하며 큐 형태로 풀 수 도 있습니다~ 참고만 하시길! 정답) * 다른 사람들의 풀이를 보니 이차원 배열을 이용하여 짧고 깔끔하게 풀 수도 있더라구요. 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
2019. 11. 12.
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(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..
[프로그래머스💯] 코딩테스트 연습 > 스택,큐 > 기능개발
스택, 큐는 이용하지 않고 풀었습니다! time 변수를 만들어서 시간 초를 고려하며 큐 형태로 풀 수 도 있습니다~ 참고만 하시길! 정답) * 다른 사람들의 풀이를 보니 이차원 배열을 이용하여 짧고 깔끔하게 풀 수도 있더라구요. 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges