👨‍🏫ps

[leetcode] 198. House Robber [kotlin]

문제분석1. dp 문제이다.2. nums input 으로 각 집에있는 돈 양이 들어온다.3. nums array에 연속된 인덱스는 인접한 집으로 판단한다.4. 인접한 집을 털 수 없다. 문제해결1. 도둑이 선택할 수 있는 방법은 두가지이다. 현재 집을 털거나 털지 않거나이다.2. 현재 집을 턴다면 바로 전 집을 털 수 없기 때문에, 전 집을 털었을 때의 최대 돈과 전전집을 털고 현재 집을 털었을 때, 최대 돈을 비교하여 현재 집 기준으로 최대 돈을 구한다.3. 현재가 i라고 한다면 [i의 최대돈] = max([i-1 까지의 돈], [i-2 까지의 돈] + [i를 털었을때 돈] 이다.class Solution { fun rob(nums: IntArray): Int { if (nums.s..

[leetcode] 2.Add Two Numbers [Kotlin]

문제분석1. linkedList 문제이다.2. Int는 10자리지만, 첫째자리가 2가 넘으면 안되기 때문에, 일반적으로 먼저 계산을 한 후, linkedList로 만드는 형식으로는 Int value값이 넘어 갈 수 있다. 문제해결1. l1과 l2의 각 자리 수를 차례대로 더 해준다.2. 만약, 더 한 값이 10을 넘어간다면 다음 자리 수 더할 때 더해주도록 한다.3. l1과 l2의 자리 수가 같진 않기 때문에, 없는 값이라면 0을 더해주도록 한다.4. 만약, l1과 l2를 순회했는데, 다음 자리 수에 더해야되는 값이 1이라면 추가 Node를 만들어 더해준다. class Solution { fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? { ..

[leetcode] 128.Longest Consecutive Sequence [kotlin]

문제 분석1. sorting 되지 않은 array가 input으로 주어진다.2. 연속된 숫자들이 가장 긴 경우의 숫자를 파악해야되는 문제이다.3. 시간복잡도 제한은 O(n)이다. 문제 해결1. sortedSet을 사용했다.2. sortedSet의 정렬은 logN이 걸리기 때문에, sortedSet을 사용했다.3. 각 숫자들을 정렬한다음. 현재 숫자와 앞의 숫자와 비교하여, 길이를 계산하였다.    - 가장 첫번째의 경우 다음 숫자를 null로 두어, null 일 경우에는 첫번째 숫자로 가정하여 길이만 더하고, 다음 숫자를 (현재 숫자 + 1)로 지정하였다.4. 마지막 순회는 O(n)이기 때문에 O(n) 시간복잡도 이내에 문제를 해결할 수 있다. class Solution { fun longestCo..

[프로그래머스] 미로 탈출 [python]

문제 bfs로 풀면되는 문제이다. 출발점-> 레버 + 레버 -> 도착점 두 합의 최소를 구하면 된다. 코드 from collections import deque def solution(maps): answer = 0 startDot, leverDot, endDot = None, None, None for i in range(len(maps)): for j in range(len(maps[i])): if maps[i][j] == "S": startDot = (i,j) elif maps[i][j] == "L": leverDot = (i,j) elif maps[i][j] == "E": endDot = (i,j) else: continue startToLever = bfs(maps,startDot, leverD..

[프로그래머스] 혼자 놀기의 달인 [python]

문제 결국 풀어여 되는 건 간단한데, 문제가 너무 장황하다. dfs로 사이클이 있는 그래프를 찾고, 그래프의 노드의 수가 많은 것들을 곱하면 되는 문제이다. dfs로 그래프들을 모두 구한 후, sort를 하고 가장 큰 두 개를 골랐다. 그래프가 하나만 있을 수도 있기 때문에, 미리 0을 넣어서 무조건 두 개의 그래프가 생길 수 있도록 하였다. 코드 def solution(cards): global cnt answers = [0] isChecked = [False for i in range(len(cards) + 1)] for i in range(1,len(cards) + 1): cnt = 1 if isChecked[i] == False: isChecked[i] = True dfs(cards, i, isC..