컴퓨터공학/LeetCode 1000

[LeedCode] 1167. Minimum Cost to Connect Sticks 파이썬 Medium

문제 해석: 주어진 양의 정수 리스트에서 두개의 숫자를 뽑아 하나의 막대로 연결해야한다. 하나의 막대를 연결하는 비용은 각 막대의 값의 합과 같다. 모든 막대를 연결했을때 가장 최소비용은 얼마인가? 문제 해설: 1. 최소비용을 구하기 위해서는 가장 작은 막대들부터 연결해야한다. 2. 막대들 중에 작은 숫자를 순서대로 꺼내서 연산해야하기 때문에, Priority Queue, Heap을 사용할 수 있다. (자료구조를 사용하지 않고, 매번 정렬하면 시간이 오래걸린다.) 3. 힙에서 두개의 숫자를 꺼내, 합하고 그비용을 결과에 더한다. 4. 그리고 연결되어 생성된 막대를 다시 힙에 넣는다. 5. 위의 과정을 막대가 1개가 될때까지 반복한다. 1167. Minimum Cost to Connect Sticks Yo..

[LeedCode]819. Most Common Word 파이썬 Easy

문제 해석: 문장이 주어진다. 문장은 대소문자, 여러 기호들이 들어간다. banned 리스트에는 답에서 걸러낼 단어들이 들어있다. banned 에 들어있지 않는 단어들중에 가장 많이 언급된 단어를 구해라. 문제 해설: 1. 문장리스트를 한글자씩 받는다. 2. 알파벳이면 소문자로 다 변환해준다. 3. 다른 기호거나 띄어쓰기는 모두 띄어쓰기로 넣는다. 4. 띄어쓰기를 기준으로 split한다. 5. banned에 있는 단어가 아니면 딕셔너리에 넣고 개수를 올려준다. 6. 딕셔너리에 저장된 개수를 이용하여 최대값을 구한다. 819. Most Common Word Given a string paragraph and a string array of the banned words banned, return the m..

[LeedCode] 53. Maximum Subarray 파이썬 Easy

문제 해석: 정수 배열이 주어진다. 연속적으로 이어진 부분합중 최대값을 구해라. 문제 해설: 1. Brute Force 로 모든 값을 찾아보는 방법외에, 다이나믹 프로그래밍으로 값을 구할 수 있다. 2. 현재 값과 최대값을 담을 변수를 저장하고 3. 두번째 값부터, 최대값을 찾아나간다. 4. 현재 위치와, 이전 위치 + 현재 위치의 값을 비교해서 최대값을 저장한다. 5. 최대값 변수와 4번에서 비교한 최대값을 비교하여 최대값을 구한다. 예제 : -2, 1, -3, 4, -1, 2, 1, -5, 4 에서, 처음 -2은 저장하고 시작한다. -2와 1의 합과, 1의 값을 비교했을때 1이 더크니 더하지않고 1을 저장한다. -3에서 -3과 1과의 합 비교시, 합이 더 크기 때문에 값을 갱신한다. 4로 넘어가기전에..

[LeedCode] 175. Combine Two Tables SQL Easy

문제 설명: 테이블이 두개가 있다. Person 테이블과 Address 테이블이 있는데, personId를 기준으로 주소를 연결해줘야한다. 만약 주소가 존재하지 않으면 null로 표기한다. 문제 풀이: 1. left join으로 Address 테이블을 Person 테이블에 연결한다. 2. 그리고 Person테이블의 PersonId 와 Address테이블의 PersonId를 조건으로 달아준다. Table: Person+-------------+---------+ | Column Name | Type | +-------------+---------+ | personId | int | | lastName | varchar | | firstName | varchar | +-------------+--------..

[LeedCode] 423. Reconstruct Original Digits from English 파이썬 Medium

문제 설명: 문자열이 주어진다. 문자열에는 0 부터 9까지 나타내는 단어들이 들어있다. 그 단어들은 섞여 있어서 숫자를 알아볼 수 없다. 이 숫자들을 알아내여, 오름차순 순으로 출력해야한다. 문제 풀이: 숫자들은 개수에 제한없이 문자열에 저장되있다. 특정 알파벳의 개수를 이용하여 숫자들을 재구성해야한다. 1. 0 부터 9까지의 숫자의 영어단어들을 봤을때, 하나의 숫자에만 들어가는 알파벳이있다. 2. z, w, u, x, g 다섯개가 오직 하나의 단어에만 들어가는 알파벳이다. zero, two, four, six, eight. 3. 문자 스트링에서 위 다섯개의 알파벳 개수를 센다. ( 0, 2, 4, 6, 8 ) 의 개수를 의미하게 된다. 4. 그리고 five는 f개수를 세서 four의 개수를 빼면 도출할..

[LeetCode] 3. Longest Substring Without Repeating Characters 파이썬 Medium

문제 해석: 문자열이 주어지면, 문자열내에 가장 긴 부분 문자열을 찾아야한다. 반복 문자가 없어야 하는데, 그 말의 뜻은 연속이나 단어 단위로 반복이 되는게 아니다. 단지 이미 있었던 알파벳인지만 확인하면된다. 문제 해설: ( 이해가 갑자기 잘안되서, 많이 해맸다.... ) 슬라이딩 윈도우 1. 아스키코드로 문자의 개수를 저장한다. 2. 투포인터로 시작점 끝점을 지정하고, 와일문을 이용하여 끝점부터 이동시킨다. 3. 끝점을 이동시키기전에, 끝점에 해당하는 알파벳에 카운트를 올려준다. 4. 만약 새로 카운트를 올린 알파벳이 1보다 많다면, 줄어들때까지 와일문을 돌린다. 5. 줄이는 방법은 시작점 인덱스를 늘려주면서, 확인되는 문자들의 카운트들을 내려준다. 6. 그리고 시작점과 끝점을 계산하여 최대값을 구한..

[LeedCode] 1041. Robot Bounded In Circle 파이썬 Medium

문제 해석: 명령어가 문자열로 입력된다. 명령어는 각각, G, L, R로 주어지는데, G : 앞으로가기 L : 왼쪽으로 방향전환 G : 오른쪽으로 방향전환 이렇게 로봇은 명령어에 따라 움직일 수 있다. 이 명령어를 계속 수행했을때, 로봇이 무한한 서클에 빠지는지 아닌지를 확인해라. 문제 해설: ( 처음에 방향이 4개니까 최대 5번 반복하면 어찌됬던 같은 위치에 도착한다고 생각했다가 실패했다. ) 1. 두가지 조건으로 무한 써클에 빠지는지 아닌지 알 수 있다. 2. 처음 명령어를 한번 진행했을때 처음 좌표로 오게 된다면 그것은 무한 써클이다. 3. 처음 명령어를 한번 진행했을때 북쪽을 보고 있지 않는다면 그것은 무한 써클이다. 이에 대한 증명이 있는데, 2번은 사실 명령어를 모두 수행후 초기 위치로 오면 ..

[leedCode] 7. Reverse Integer 파이썬 Medium

문제 해석: 숫자 한개가 32비트 signed 정수로 주어진다. 이 숫자를 뒤집어야한다. 하지만 정답을 리턴할때 그 뒤집은 숫자가 32 비트 숫자를 넘을 경우 0을 리턴한다. 문제 해설: 1. 입력 받은 숫자를 양수와 음수였을때 처리를 다르게 해야한다. 2. 파이썬에서 숫자를 뒤집는 방법은 문자로 바꾼후에 쉽게 처리할 수 있다. ( 10의 몫과 나머지로 계산하는 무식한 방법도 있다. ) 3. 양수일 경우 그냥 문자로 뒤집은 후, 정수로 리턴한다. 4. 음수일 경우 문자로 변환, 앞의 -를 때고 뒤집는다. 리턴할때 다시 붙이고 정수로 변환한다. 7. Reverse Integer Given a signed 32-bit integer x, return x with its digits reversed. If r..