Daim's blog

Python으로 푸는 LeetCode 965. Univalued Binary Tree (Easy)

2진 트리에서 모든 노드가 같은 값을 가지고 있는지 확인하는 프로그램을 짜시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 leetcode에서는 기본 자료구조를 잘 활용할 수 있도록 다양한 문제를 준다. 이 문제도 트리의 순회문제이다. 순회를 할 때는 재귀를 이용할 수 있고 While문을 이용해서 모든 노드를 탐색할 수 있다. 나는 두가지 방식 모두를 활용해서 문제를 풀어보았다. 재귀를 별로 좋아하진 않은데 while문과 재귀 모두를 짜보게 되면 문제를 한단계 깊게 생각할 수 있어서 좋다. 파이썬 코드 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..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 6. 17. 15:30

Python으로 푸는 LeetCode 938. Range Sum of BST (Easy)

BST(이진 탐색 트리)가 있다. 입력받은 L, R의 범위에 속하는 값들의 합을 반환하는 프로그램을 짜시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 트리는 깊이가 있는 자료 구조이므로 개인적으로 나는 재귀로 문제를 해결하기가 쉽다. 나는 Node를 인자 값으로 넘기면 그 노드를 root로 하는 이진 탐색트리에서 L, R을 범위로 하는 Node를 찾아 값을 더하고 그 결과값을 반환해주는 checkChildBST라는 함수를 만들었다. 이런 재귀 함수를 짤 때에 가장 중요한 것은 재귀를 언제 중단하느냐에 대한 조건을 반드시 명시하는 것이라고 생각한다. 내 코드에서는 총 2번의 반환 작업이 일어난다. - 현재의 노드가 아무런 자식을 가지고 있..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 6. 14. 09:00

Python으로 푸는 LeetCode 506. Relative Ranks (Easy)

LeetCode 506. Relative Ranks 점수가 가장 높은 순서대로 3명에게는 메달을 수여하고, 그 외에는 순위를 구한 값이 담긴 리스트를 반환한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 nums를 역순으로 정렬한 리스트 sorted_nums를 생성한다. sorted_nums에서부터 값을 하나씩 꺼내게 되면 해당 점수의 순위를 알 수 있다. index 2까지의 점수는 순위가 아닌 medal을 받아야 한다. 따라서 medal 리스트로부터 index를 활용해 어떤 메달을 받게 될지 구한다. 그 외에는 index + 1 한 값이 순위이므로 그 값을 nums에 추가시킨다. 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 1..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 16. 23:30

Python으로 푸는 LeetCode 744. Find Smallest Letter Greater Than Target (Easy)

주어진 문자보다 가장 처음으로 큰 숫자를 찾아 반환하는 코드를 짜시오 LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 풀이 주어진 문자보다 가장 처음으로 큰 숫자를 반환하여야 한다. 단, 주어진 문자가 주어진 문자리스트의 모든 문자보다 클 경우에는 list의 가장 처음 문자를 반환하면 된다. "Letters also wrap around" 라는 문제 조건이 있기 때문이다. 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def nextGreatestLetter(self, letters, target: str) -> str: target = ord(target) for letter i..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 15. 23:30

Python으로 푸는 LeetCode 599. Minimum Index Sum of Two Lists (Easy)

LeetCode 599. Minimum Index Sum of Two Lists 주어진 두 리스트의 공통 부분을 찾아서 각각의 리스트에서 위치한 Index의 값의 합이 최소인 결과값을 리스트로 반환하시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 이 문제는 Hash Table로 문제를 풀 경우에 쉽게 풀 수 있다. 주어진 두 리스트 중 하나를 기준으로 잡은 다음, 리스트의 원소와 index를 Key, Value로 하는 hash table을 구성한다. (파이썬에서는 dictionary 컨테이너를 활용한다) 두번째 리스트를 순회하면서 dictionary에 해당 원소를 key로 하는 값이 있는지 확인하고, 있다면 value와 현재 원소의 in..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 7. 22:30

Python으로 푸는 LeetCode 917. Reverse Only Letters (Easy)

알파벳이 아닌 문자(-,!,? 등등)를 제외한 알파벳 문자를 뒤집어서 반환하는 코드를 짜시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 문제를 푸는 방법은 다양하다. 처음 풀었던 방식은 문자열의 맨앞(start_index)와 맨뒤(last_index)의 index를 하나하나 확인하면서 앞뒤 모두 알파벳 문자열인 경우에만 두 자리를 바꿔주는 방법이다. 방법 1. 포인터를 이동하며 문자열 교환 만약 알파벳이 아니라면 index를 낮추거나 높여서 가리키고 있는 index를 문자열의 가운데로 점점 이동하며 문자열을 바꿔준다. start_index와 last_index가 서로 만나면 문자열 교환을 중지하고 str()으로 변환하여 결과값을 반환한다..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 6. 23:40

Python으로 푸는 LeetCode. 942. DI String Match (Easy)

문제의 조건에 따라 완성한 list를 반환한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 조건 인자값으로 "I"와 "D"로만 구성된 문자열 S를 받는다. N은 S의 길이 값이다. 반환해야 하는 결과값인 리스트 A는 0~N까지의 구성된 원소들로 구성되어 있다. 단, 그 원소들의 순서는 다음과 같은 조건으로 정해진다. 문자열 S의 문자열이 "I"(Increase)이고 그 Index가 1이면 Index 1번째의 리스트 A의 원소는 그 다음번에 나타날 원소들 보다 가장 작아야 한다. 문자열 S의 문자열이 "D"이고 그 Index가 2이면 Index 2번째 리스트 A의 원소는 그 다음버넹 나타날 원소들보다 가장 커야 한다. 문제 풀이 이미 주어진 조건..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 4. 19:00

Python으로 푸는 LeetCode 804. Unique Morse Code Words (Easy)

List의 원소인 단어들이 Morse Code로 바꾸었을 때, 중복되지 않은 모스 코드의 수를 반환하는 프로그램을 짜시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 조건 알파벳 26자에 대응되는 Morse Code가 주어진다. Morse Code에는 각 알파벳에 대응되는 Morse Code가 중복되기도 한다. 문제 풀이 주어진 Morse Code가 어떤 알파벳을 뜻하는지 정의해두기 위해서 파이썬의 dict()에 알파벳을 Key로 하고 모스 부호를 value로 하는 딕셔너리를 만들었다. 알파벳을 순회하여 출력하기 위하여 해당 문자의 아스키 코드 값을 알 수 있는 ord() 메소드를 활용하였다. 알파벳 'a'와 'z'의 아스키 코드 값이 97과 ..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 3. 21:00

Python으로 푸는 LeetCode 929. Unique Email Addresses (Easy)

문제의 조건에 따라 완성한 list를 반환한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 조건 이메일은 @를 기준으로 다음과 같이 구성되어 있다. (local name@domain names) local name 부분에서 '.'이 나올 경우 '.'이 없는 것처럼 취급한다. local name 부분에서 '+'가 나올 경우 '+' 이하의 local name 부분은 없는 것처럼 취급한다. 문제 풀이 여러 이메일 주소가 담긴 List가 주어지고, 이 이메일들을 순회하면서 조건에 따라서 local name 부분을 수정한다. 이때 정정된 이메일 주소는 set()에 담아 중복을 제거한다. List의 모든 이메일 주소를 수정하였을 때 set()에 담긴 이메..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 2. 17:00

Python으로 LeetCode 994. Rotting Oranges (Easy)

LeetCode 994. Rotting Oranges (Easy) 이 문제는 백준 7576. 토마토 문제와 유사하다. 썩은 오렌지가 신선한 오렌지를 썩게 한다고 하였을 때, 모든 오렌지가 다 썩으려면 며칠이 걸리는지 그 최소 일수를 구하도록 해야 한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 조건 주어진 2차원 배열 Grid에는 각각 숫자가 들어 있고, 0은 빈 칸, 1은 신선한 오렌지, 2는 썩은 오렌지를 의미한다. 썩은 오렌지는 상하좌우의 신선한 오렌지를 썩게 만들수 있다. 신선한 오렌지가 모두 사라질 때의 시간을 구해야 하며, 처음부터 신선한 오렌지가 없을 경우에는 0을, 신선한 오렌지는 있으나 썩은 오렌지가 없을 경우에는 -1을 출력..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 4. 29. 18:00

Python으로 푸는 LeetCode 268. Missing Number (Easy)

이 문제는 0, 1, 2....n으로 이루어진 숫자들을 원소로하는 리스트에서, 빠진 숫자가 무엇인지를 찾아 반환할 수 있도록 코드를 짜야한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 n까지의 숫자의 총합은 계산하였을 때, n(n+1)/2 이다. 이 식을 이용하여 총합에서 list의 모든 값을 더한 값을 뺐을 때, 빠진 숫자를 찾을 수 있다. 단, 총합에서 list의 모든 값을 더한 값을 뺐을 때읙 결과 값이 0인 경우는 예외처리해주어야 한다. 리스트 내에 0이 있을 경우, 리스트에서 빠진 숫자는 가장 큰 값인 n이므로 리스트이 최대값에서 1을 더한 숫자를 반환하여야 한다. 리스트 내에 0이 없을 경우, 리스트에서 빠진 숫자는 0이므로 ..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 4. 26. 17:00

Python으로 푸는 LeetCode 21. Merge Two Sorted Lists (Easy)

LeetCode 21. Merge Two Sorted Lists (Easy) 주어진 정렬된 2개의 Linked List의 Head를 가지고, 두 List의 원소들을 작은 값부터 차례로 정렬된 List의 Head를 반환하시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 input에서 주어진 두 Linked List는 이미 정렬되어 있다. 따라서 각각의 head부터 순회하면서 작은값들을 가져와 Linked list를 새로 만들어주면 된다. 만약 두 List 중에 하나라도 빌 경우 나머지 Linked List를 현재의 node에다가 이어주기만 하면 된다. 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 4. 25. 18:00