본문 바로가기

알고리즘풀이

 (38)
LeetCode: Rotate Array 문제설명 정수형 배열이 주어졌을 때, 배열의 오른쪽으로 k 만큼의 항목 까지만 회전하라 문제풀이 하나씩 꺼내어 앞으로 추가하기 배열을 linked list로 구현했을 때 적합하다. // 1. Pop and Push one by one func rotate_popAndPush(_ nums: inout [Int], _ k: Int) { for _ in 0.. 1 else { return } let k2 = k%nums.count if k2 == 0 { return } // reverse left section let leftSectionLastIndex = nums.count-k2-1 reverse(&nums, startIdx: 0, endIdx: leftSectionLastIndex) // reverse ..
LeetCode: Best Time to Buy and Sell Stock II 문제설명 가격이 담긴 배열, prices가 주어졌을 때, prices[i]는 i번째 날의 주식의 가격을 의미한다. 주어진 배열 내에서 주식을 사고 팔 수 있는 최대 수익을 계산하라. 문제풀이 다양한 방법이 있지만, 동적 프로그래밍으로 풀 수 있다. 이전의 주식 가격과 비교하기 위해, 배열의 0번째가 아닌 1번째 부터 순회한다. 이전 주식 가격에 현재 가격을 빼서 수익이 0 이상 일 때, 이전의 수익 값과 더한다. 수익이 0 이하라면, 이전의 수익 값을 그대로 복사한다. 가장 마지막에 계산된 수익 값을 반환한다. func maxProfit(_ prices: [Int]) -> Int { var profits = [0] for i in 1.. 0 { profits.append(profits[i-1] + pro..
LeetCode: Remove Duplicates from Sorted Array 문제설명 정렬된 배열이 주어졌을 때, 중복을 제거하라 주어진 배열을 in-place로 수정해야 한다. 반환하는 값은 중복이 제거된 배열까지의 길이다. 문제풀이 Two pointers 전략을 사용하여, 차례로 배열을 순회할 인덱스 교체할 인덱스 두 개를 둔다. 교체할 인덱스와 순회하는 인덱스가 가리키는 값이 다를 때, 교체할 인덱스에 하나를 더한 인덱스 위치에 현재 인덱스의 값을 복사한다. func removeDuplicates(_ nums: inout [Int]) -> Int { var replacedIdx = 0 for i in 0..
LeetCode: Missing Number 문제설명 0부터 배열의 개수 n까지의 숫자 중, 주어진 배열의 수에서 없는 숫자를 반환하라 문제풀이 0부터 배열의 개수 n까지를 더하고, 그 수에서 주어진 배열의 합을 뺀다. func missingNumber(_ nums: [Int]) -> Int { let count = nums.count let sum = (count * (count + 1)) / 2 let subtract = nums.reduce(0,+) return sum - subtract } print(missingNumber([0,1,2,3,4,5])) // 6 print(missingNumber([3,0,1])) // 2 print(missingNumber([9,6,4,2,3,5,7,0,1])) // 8 print(missingNumber..
LeetCode: Valid Parentheses 문제설명 문자열 s는 다음 3가지 종류의 괄호를 갖는다. '(', ')', '{', '}', '[', ']', 괄호가 적절하게 닫혔는지를 판별하라. 문제풀이 여는 괄호라면, stack에 넣는다. 여는 괄호가 아니라면, stack에서 값을 가져와서 현재 괄호와 비교한다. 만약 stack이 비어있다면, 여는 괄호 없이 닫는 괄호가 먼저 나왔다는 것이므로 false를 리턴한다. 주의할점은 swift의 removeLast()가 아닌, popLast()를 사용해야 옵셔널로 반환한다. func isValid(_ s: String) -> Bool { let strArray = Array(s) var stack = [Character..
LeetCode: Pascal's Triangle, 파스칼 삼각형 문제설명 입력으로 받은 행의 개수로 파스칼 삼각형을 배열로 반환하라. 파스칼 삼각형은 각 숫자가 바로 윗행의 두 개의 숫자의 합으로 이루어진다. 문제풀이 func generate(_ numRows: Int) -> [[Int]] { var result = [[1]] for i in 1..
LeetCode: Reverse Bits, 비트 뒤집기 문제설명 32비트 unsigned 정수가 주어졌을 때, 비트를 뒤집어서 반환하라 문제풀이 입력된 정수의 비트를 하나하나씩 새로운 변수에 옮겨준다. 32비트 unsigned 정수는 32자리 비트가 모두 1로 채워진다. 32비트 unsigned 정수의 최대값인 2^32 을 뒤집으면, 그대로 2^32이 나온다. func reverseBits(_ n: Int) -> Int { var result = 0 var num = n for i in 0.. 1 } return result } print(String(reverseBits(1), radix: 2)) // 10000000000000000000000000000000 print(String(reverseBits(2), radix: 2)) // 10000000000..
LeetCode: Hamming Distance, 해밍 거리 문제설명 두 정수가 주어졌을 때, 두 수의 해밍거리를 구한다. 거리(distance)라고 해서 두 수의 다른 비트 거리라고 생각하면 안되고, 다른 비트의 개수라고 이해해야 한다. 문제풀이 func hammingDistance(_ x: Int, _ y: Int) -> Int { var xor = x ^ y var count = 0 while xor != 0 { if xor & 1 == 1 { count += 1 } xor = xor >> 1 } return count } print(hammingDistance(1, 4)) // 2 print(hammingDistance(4, 8)) // 2

티스토리툴바