📠 문제Container With Most Water난이도: Medium주어진 배열에서 양 끝점으로 한 가장 큰 직사각형의 넓이를 구하는 문제Input: height = [1,8,6,2,5,4,8,3,7]Output: 49Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.💡 풀이첫 번째로 가장 무식하게 모든 경우의 수를 체크하는 방법이 있다. 물론 n의 입력값이 10^5이기 때문에 시간초과!func maxArea(_ height: [Int]) -> Int ..
📠 문제Clone Graph난이도: Medium주어진 그래프를 깊은 복사하는 문제이다.class Node { public int val; public List neighbors;}Input: adjList = [[2,4],[1,3],[2,4],[1,3]]Output: [[2,4],[1,3],[2,4],[1,3]]💡 풀이어어...? 이 문제를 풀면서 살짝 당황했다. 당연히 쉽게 생각했던 깊은 복사가 생각보다 쉽지 않구나라는 것을 알게 되었다. 왜냐하면 새로운 객체를 생성하면서 연결된 객체들을 다시 연결해줘야 하기 때문에 이것이 생각보다 까다롭다. 문제에서 가지고 있는 val을 key로 사용하고 새롭게 인스턴스를 만들면 된다. 만약 val이 없다면 Swift는 ObjectIdentifier를 ..
📠 문제Longest Palendromic Substring난이도: Medium문자열 s가 주어질 때, s에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제이다.팰린드롬이란, 앞에서 읽든 뒤에서 읽든 같은 문자열을 말한다.Input: s = "babad"Output: "bab"Explanation: "aba" is also a valid answer.💡 풀이결국 팰린드롬은 중심을 기준으로 대칭이 되어야 한다. 팰린드롬의 종류는 두가지인데 aa처럼 짝수로 된 팰린드롬이 있을 수 있고, aba처럼 홀수로 된 팰린드롬이 있을 수 있다. 따라서 중심으로부터 펼쳐(?)나가는 식으로 코드를 작성하면 O(n^2)의 시간복잡도로 구할 수 있다.func longestPalindrome(_ s: String) -> Str..
📠 문제Longest Consecutive Sequence난이도: Medium정수 배열이 주어질 때, 정렬하지 않고 가장 긴 연속 수열의 길이를 구하는 문제이다.Input: nums = [100,4,200,1,3,2]Output: 4Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.💡 풀이처음에 오름차순, 내림차순이 생각나기 때문에 정렬을 할 수 있는데 정렬을 하는 순간 O(nlogn)이 되어버린다. 이 문제의 핵심은 O(n)으로 푸는 것이다. (문제에서 You must write an algorithm that runs in O(n) time. 라고 나와있다) 생각해보면 단순..
🧐 문제🧙 문제풀이만만하게 봤지만(?) 생각할 거리가 꽤 있는 문제였다. 첫번째는 일단 무식하게 풀어보자였다. Array를 내 위치부터 잘라서 그 뒤로 해당 숫자보다 큰 숫자를 찾아서 반환해줬다. 하지만 당연하게도 시간초과가 났다. numbers의 길이가 최대 1,000,000이기 때문에 아래와 같은 풀이 방법은 결국 O(n^2)으로 시간초과가 나게 된다.func solution(_ numbers: [Int]) -> [Int] { var answer: [Int] = [] for i in numbers.indices { let first = numbers[i...].first { $0 > numbers[i] } ?? -1 answer.append(first) ..
🤓 문제https://www.acmicpc.net/problem/16638🧙 풀이과정우선 아래의 문제와 비슷하고, 이번에는 괄호를 아무렇게나 씌울 수 있다는 조건이 추가되었다. [Algorithm] 백준 - 16638번 괄호 추가하기2 (Swift)🧐 문제https://www.acmicpc.net/problem/16638✨ 풀이괄호, 곱하기, 그외 연산자 순으로 연산을 진행하면 되겠다라고 생각했다. 그리고 괄호는 중복되면 안되기 때문에 오른쪽부터 괄호를 씌우게 하지만swift-library.tistory.com✨ 첫 번째 풀이 (단순하게)첫 번째는 아주 간단하게 접근했다. 그냥 모든 경우를 계산했다. let n = Int(readLine()!)!let expression = Array(readLin..
🧐 문제https://www.acmicpc.net/problem/16638✨ 풀이괄호, 곱하기, 그외 연산자 순으로 연산을 진행하면 되겠다라고 생각했다. 그리고 괄호는 중복되면 안되기 때문에 오른쪽부터 괄호를 씌우게 하지만 이전에 괄호가 있다면 무조건 한칸 건너띄게 괄호를 넣을 수 있게 했다.let n = Int(readLine()!)!let math = Array(readLine()!).map { String($0) }var cap = Array(repeating: false, count: n)/// ["숫자", "부호", "숫자"] 연산func operation(_ array: [String]) -> String { let left = Int(array[0])! let right = In..
🤓 문제https://www.acmicpc.net/problem/1700✨ 풀이캐싱과 느낌이 정말 비슷하다. 왜냐하면 멀티탭에 꽂혀있느면 바로 사용이 가능한 것이고(Hit), 멀티탭에 없으면 플러그를 꽂아야 한다. 하지만 코드는 한정적이기 때문에 효과적으로 멀티탭을 관리해야 한다. 첫번째 풀었던 방법은 캐싱을 생각하면서 가장 사용이 많이 된 것을 남기고 나머지를 교체하는 알고리즘을 사용했지만 이 문제의 중요한 점은 미래를 안다는 것이다. 미래를 모르는 상황에서는 가장 사용이 많이 되거나 가장 최근에 사용한 것을 살리는 식으로 캐싱을 하면 되지만 미래를 아는 순간 이야기는 달라진다. 멀티탭이 꽉차게 되면 가장 늦게 쓰는 플러그를 빼면 된다. 어자피 가장 최근에 쓰는건 결국 사용하기 때문에 일단 넣어두어야..
