컴퓨터공학/LeetCode 1000

[LeedCode] 2. Add Two Numbers 파이썬 Medium

문제 해석: 두개의 링크드 리스트가 주어진다. 각 한자리 숫자가 연결되어 있다. 각 링크드 리스트에 연결되어있는 숫자로 거꾸로 뒤집어 꺼낸다. 이후, 두 숫자를 합하여 링크드리스트에 다시 뒤집어 넣어 리턴한다. 문제 해설: ( 처음에는 숫자를 꺼내서 뒤집고 계산한 다음에 다시 거꾸로 넣어줬다.. BTW 더 좋은 방법이 아래 있다. ) 1. 링크드 리스트에서 순서대로 한자리 숫자를 더하고, 나머지를 저장한다 2. 1번과 마찬가지로 숫자를 더하고, 10으로 나눈 몫을 저장한다. 3. 1번에서 구한숫자는 정답으로 리턴할 리스트에 넣는다. 4. 2번에서 구한 10의 자리 숫자는 다음 숫자를 합할때 포함시킨다. 5. 숫자 두개를 더 했을때 두자리 숫자가 나오는것을 나누기와 모듈러 연산으로 나눠서 다음 계산때 넣어..

[LeetCode] 200. Number of Islands 파이썬 Medium

200. Number of Islands 문제 해석: 2차원 바이너리 그리드에서 1은 땅이고 0은 물이다. 그렇다면 이어져있는 땅의 갯수를 세어야한다. 문제 해설: 1. BFS를 진행해서 이어져있는 섬들을 찾아야한다. 2. BFS를 실행하면 모든 이어진 섬을 찾을 수 있는데, 떨어져있는 섬이 존재할 수도 있다. 3. 2중 for문을 사용해서 모든 그리드의 섬을 하나씩 확인해봐야한다. 4. 그리드 리스트에 들어가있는 숫자가 문자라서 그부분을 조심하자. Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded..

[LeedCode] 56. Merge Intervals 파이썬 Medium

문제 해석: 배열에 각 시작점, 종료점을 가진 값들이 저장되어 있다. 겹쳐져 있는 구간들을 합치고, 겹치지 않는 모든 간격들은 배열에 넣어 반환한다. 문제 해설: 1. 주어지는 점들은 길이가 모두 다르기 때문에, 간격마다 모두 확인을 해야한다. 처음나온 간격이 다음 간격보다 클수도, 작을수도, 혹은 모두 포함될 수 도 있다. 2. 간격들을 오름차순으로 정렬하여, 하나씩 저장해나가야한다. 3. 새로만든 리스트가 비어있으면 바로 넣는다. 4. 리스트 가장 뒤의 간격의 끝 숫자가 새로 확인되는 간격 첫 숫자보다 작을 경우 리스트에 넣는다. 5. 3번과 4번이 아니라면 간격이 겹친다. 리스트는 이미 정렬되어있기 때문에 마지막의 간격 끝점과 새로 확인될 간격의 시작점을 비교하여 큰 값을 끝점으로 갱신한다. Giv..

[LeetCode] 1710. Maximum Units on a Truck 파이썬 easy 정렬

1710. Maximum Units on a Truck 문제 해석: 2차원 배열에는 박스의 개수와 박스안에 들어있는 유닛의 개수가 저장되어있다. 그리고 Maximum 값이 주어지는데, 이것은 트럭에 올릴 수 있는 최대 박스 개수이다. 박스를 최대한 트럭에 실었을때, 최대의 유닛 개수를 구하자. 문제 풀이: 1. 트럭에 가장 많이 실어올리기 위해선 유닛이 가장 많은 박스를 올리는 것이 유리하다. 2. 정렬을 이용해 유닛 순으로, 오름차순으로 정렬한다. 3. 트럭에 실은 박스의 개수가 TruckSize가 넘기 전까지 박스 X 유닛의 값을 더해준다. 4. 박스의 개수가 TruckSize를 넘겼을때, 값을 더해주지 않고 실을 수 있는 만큼의 마지막 박스만 계산한다. You are assigned to put s..

[LeetCode] 937. Reorder Data in Log Files - Easy 파이썬 sorted key 함수

937. Reorder Data in Log Files 문제 해석 : 두가지 단어로 구성되어있는 리스트가 주어진다. Letter-logs와 Digit-logs가 있다. Letter-logs : 식별자외에는 모두 소문자 영어 문자로 되어있다. Digit-logs : 식별자 외에는 모두 숫자로 되어있다. 정렬 규칙: 1. Letter-logs는 순서상 Digit-logs보다 앞에 있다. 2. Letter-logs는 식별자보다 내용이 먼저 정렬되고, 내용이 같으면 식별자 순으로 정렬된다. 3. Digit-logs는 그대로 기존 정렬을 유지한다. 풀이 방법: 1. 식별자와 내용을 분리한다. 2. key로 사용할 함수를 생성한다. 3. 문자와 숫자 단어들에서 식별자를 제외하고, 무조건 문자, 숫자만 나오기 때문에..

[LeetCode/릿코드] - 10. Regular Expression Matching - (Hard/하드)

문제 : Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). 문제 해설 : 이번 문제는 어려워서,, 다른 코드를 조금 참고 했다. Dynamic Programming / Recursion 으로 풀 수 있는데, 처음에 구현 문제라고 생각한 것이 문제였다. 주어지는 문자열 s 와 p 가..

[LeetCode/릿코드] - 4. Median of Two Sorted Arrays - (Hard/하드)

문제 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). 문제 설명 : 두 개의 리스트가 주어진다. 각 리스트는 크기가 다르며 두 개의 리스트의 모든 값들 중에서 중간 값을 반환해야 한다. 시간 복잡도는 O(log (m+n)) 이어야 한다. 아이디어 : 1. 시간 복잡도와 데이터 제한을 봤을때, 반복문으로 문제를 풀 수 없다. 2. 중간 값을 구하려면, 모든 값의 상태를 알아야 하기 때문에 sort를 사용했다. 최악의 경우 O(NlogN) 3. 시간복잡도도..

[LeetCode/릿코드] - 238. Product of Array Except Self (Medium/미디엄)

238. Product of Array Except Self 문제: Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. 문제 해설: 1. 정수 숫자 배열이 주어진다. 2. 자기 자신을 제외한 모..