안녕하세요 임창록입니다 안녕하세요 임창록입니다

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3813/ 주어진 문자열을 임의의 순서(다른 문자열 order이 주어짐)로 정렬해야 하는 문제였다. order을 보고 만든 dictionary를 이용해서 std::sort에 compare를 이용해 정렬 순서를 바꿀 수 있다. 원래 compare함수를 따로 만들고 넣어줬는데, 오류가 났다. g++로 직접 돌려보니까 오류가 나지 않아서 뭐지 싶었다. 리트코드 사이트에서 인식을 못하는 듯 해서 어떡하지 하다가 람다식을 검색해서 해봤더니 해결되었다. class Solution { public: unordered_map dict..

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3811/ 문제를 보고, dictionary 구조를 쓰면 빨리 풀 수 있을 것 같았다. 그런데 c++로 하는지라 dictionary구조가 있었나? 해서 고민하다가 결국 솔루션을 찾아봤더니 dictionary를 사용하더라. c++에 unordered_map이 비슷하게 동작한다고 해서 그걸 사용해서 풀었다. class Solution { public: bool isIsomorphic(string s, string t) { unordered_map sm; unordered_map tm; int n = s.size(); for..

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3810/ 입력이 계속 들어오고, 그 입력으로 만들어진 리스트에서 중간값을 찾는 문제였다. 벡터에 넣고 입력마다 정렬을 돌렸더니 시간 초과가 났다. 입력값과 중간값을 찾으라는 요청이 5*10^4만큼 들어올 수도 있어서였다. 여러가지 방법으로 시도해봤지만 답이 안나와서 검색해보고 풀었다. 검색해서 나온 방법은 다음과 같다. 입력받은 리스트의 크기를 n, k=n/2라고 할 때, 그 리스트를 절반으로 나눠서 [1...k], [k+1...n]이 있다고 생각해보자. 이때 앞의 리스트를 A, 뒤의 리스트를 B라고 하자. A는 ma..

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3809/ 정규식 해석? 비슷한 문제였다. A=1, Z=26으로 해석할 수 있을 때, 문자열 s가 주어지고, s를 해석할 수 있는 가짓수를 묻는 문제였다. 예를들어, 123은 (1,2,3), (12,3), (1,23)의 3가지 방법으로 해석할 수 있다. 특이한 점은 1~9로 모두 해석가능한 * 문자도 s 에 들어있다는 것이다. DP를 사용해 배열 끝쪽부터 보면서 1. i번째에서 문자 1개로 읽을 수 있는 경우(1

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3808/ LIS 문제이다. dp를 이용해서 풀었다. n이 작아서 O(N^2)으로 풀었다. lower_bound 쓰는 O(NlogN)방법도 있다 코드 class Solution { public: int dp[2501]; int lengthOfLIS(vector& nums) { int n = nums.size(); int max = -1; for(int i=0; i

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3807/ 두 배열에서 가장 긴 공통 수열을 찾는 문제였다. dp를 이용해서 풀었다. dp식은 nums1[i-1]==nums2[j-1]일때, dp[i][j] = dp[i-1][j-1]. 코드 int findLength(vector& nums1, vector& nums2) { int M = 0; for(int i=1; i

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3805/ n x n 행렬이 주어지고, 행렬의 각 열과 행은 정렬되어 있는 상태이다. 이 때, 행렬에서 k 번째로 작은(unique 하지 않게) 원소를 구하는 문제였다. 그냥 행렬 돌면서 벡터에 넣어서 정렬해서 풀었다. 이미 정렬된걸 이용하면 더 빨리 정렬할 수 있는 방법이 있을거 같은데 몰라서 일단 저렇게 풀었다. 이진 탐색으로도 풀 수 있는 듯하다 코드 class Solution { public: int kthSmallest(vector& matrix, int k) { int n=matrix.size(); vector..

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3804/ 주어진 배열에서 어떤 집합에 해당하는 원소를 모두 제거했을 때, 원래 배열의 크기의 반보다 작아지려면 최소 몇개의 원소를 빼야하는가를 묻는 문제였다. 주어진 배열을 돌면서 원소별로 몇 개가 있는지 세고, 센 것을 내림차순 정렬하고, 원래 배열 크기의 반이 될 때까지 정렬한 배열을 돌며 값을 세면서 더했다 코드 class Solution { public: int minSetSize(vector& arr) { int cnt[100001]={0,}; vector v; for(auto i=arr.begin(); i!=..