목록프로그래밍/알고리즘+코딩테스트 (97)
有希
두 가지 방법이 있다. 1. 정렬 후, 0번째, 마지막 제외하고 더하면 최소 최대가 된다. nlogn + n = NlogN 2. 최소값, 최대값 찾은후 전부 더한다음 빼주면 그게 최소 최대값이 된다. n + n + n (최소탐색, 최대탐색, 더하기) = N N이 빠르다. 2번이 좀 더 좋다. 문제에서 overflow 조심하랬소 64비트 쓰랬으니 long long 써준다. void miniMaxSum(vector arr) { sort(arr.begin(), arr.end()); long long sum = 0; for(int i=0; i
필요한 헤더는 이다. find_if는 있다면 해당 위치 반환, 없으면 두번째 인자를 반환한다. isspace의 not이므로 "123" 같은 경우는 1을 발견했으니 0의 iter를 반환하고, " " 같은 경우는 문자열의 end() iter를 반환해서 다 지운다. string ltrim(const string &str) { string s(str); s.erase( s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun(isspace))) ); return s; } string rtrim(const string &str) { string s(str); s.erase( find_if(s.rbegin(), s.rend(), not1(ptr_fun(isspace))).base..
Interview Preparation Kits가 있길래 이것도 풀어보려 한다. plusMinus함수 부분만 채우면 되는데, 기본적으로 작성된 코드가 꽤 재미있다. find_if는 첫번째인자~두번째인자까지 순회하며 세번째 인자와 맞는 원소를 가리키는 iterator를 반환한다. 없다면 두번째 인자를 뱉는다. 그런데, 세번째 인자가 not1(어떤 함수객체에 붙어서 결과를 반대로. 2의 배수를 찾는 것이라면 2의 배수가 아닌 녀석일때 true가 된다) 붙어서 ptr_fun 가 되어있다. 그럼 ptr_fun은 무엇인가 하고 또 의문이 생긴다. 이는 함수 포인터를 래핑해서 함수 포인터 어댑터로 만들어서 템플릿인수를 적용할 수 있도록 해준다. 즉, 템플릿 문법이 적용된 인자에 어떤 함수를 쓰고 싶을때 쓴다. 첫번..
싸메다가 중국 사이트에서 좋은 풀이를 찾았다. 시간,공간 복잡도 분석은 물론이고 c++ 11 문법을 적극적으로 활용하고 있다. 개안한 기분이다. 1. DFS 시간 초과. 시간 초과이지만 이런 풀이도 가능하다는걸 알 수 있다. class Solution { public: int findCheapestPrice(int n, vector& flights, int src, int dst, int k) { g_.clear(); //map에 다가 pair로 연결된 점과 비용 저장 for(const auto& e : flights) { g_[e[0]].emplace_back(e[1], e[2]); } //visited를 저장할 벡터 선언 vector visited(n, 0); //처음 출발 src 도시 방문 표시 v..
맨하탄 거리니, 피타고라스 거리니 어렵게 수학적 용어 가져올 필요 없이 좌표축에 대입시켜서 x,y 좌표 합 구하면 그게 거리다. 물론 이게 맨하탄 거리이긴 하지만. 그리고 Pos 배열을 하드코딩 하는게 싫다면 0은 특수 경우이니 직접 넣어주고 나머지는 for문으로 채워넣으면 된다. 프로그래머스는 테스트 케이스를 보여주지 않는다는 점이 진짜 짜증난다. 영업비밀인건가? LeetCode는 다 보여주는데. int garo_max = 3; int sero_max = 3; vector Pos; for(int i=sero_max; i>=0; --i) { for(int j=0; j
꼴에 나름 발전시켜서 풀겠다고 여러 단계를 합쳐서 (예시로 1,4단계를 한꺼번에 처리한다던가...) 함수로 빼서 풀다가 자꾸만 오류가 나서 나 스스로에 대해 의심이 들고... 슬퍼했었다가 시키는 대로 해보자 했더니 됐다. 심지어 시간도 거의 차이 안났다. 시키는 대로 풀자... #include #include #include using namespace std; string solution(string new_id) { string answer = ""; //step1 for(int i=0; i= 'A' && new_id[i]
적절한 자료구조를 쓰면 풀 수 있다. 1. 숫자면 아무 거리낌 없이 더한다. 2. 문자라면 완성된 문자인지 확인하고, 완성됐다면 map에서 확인하고 값 꺼내서 저장한다. answer = answer * 10 + value; 하는 부분이 핵심이라면 핵심? #include #include #include using namespace std; int solution(string s) { int answer = 0; map match; match["zero"] = 0; match["one"] = 1; match["two"] = 2; match["three"] = 3; match["four"] = 4; match["five"] = 5; match["six"] = 6; match["seven"] = 7; match..
풀라면 다양하게 풀 수도 있지만, 이게 가장 효율적인거 같다. 1. unordered_set에 뽑은 숫자들 저장하며 0개수 센다 2. 맞춘 숫자 센다 3. 맞춘숫자 + 0개수 가 전부 맞은게 최고 순위이므로 저장 4. 맞춘숫자의 순위만 저장. 순위 저장은 6개 맞추면 1등 이니까 7-맞춘숫자 했다. 그 이하는 6등 이니까 저렇게 했다. 1개 맞추면 6이지만 0개 맞추면 7이므로 삼항 연산자를 사용하여 6으로 맞춘다. #include #include #include using namespace std; vector solution(vector lottos, vector win_nums) { vector answer; unordered_set nums; int zeros = 0; //0이 아닌 값 set에 ..
난 이진탐색에 약하다. 문제에서 O(log n)이내에 해야한다고 힌트를 줬으므로 이진탐색으로 풀어야 한다. 우선 while문에 들어가고 나서는 mid를 정하고 mid가 hit인지 판단한다. 아니라면 이제 high와 low중 mid로 옮길 녀석을 찾아야 한다. 문제에서 주어진 4567012의 예시를 생각해보자. 1. 5를 찾는 경우 1) mid = 3, 7이다. 아니므로 else들로 이동 2) 첫번째 else문의 조건에 해당한다. 3) high = mid-1, 2로 조정 4) mid = 1, 찾았으므로 1 반환 2. 0을 찾는경우 1) mid=3, 7이다. 아니므로 else로 이동 2) 첫번째 else 3) low = mid+1, 4로 조정 4) mid = 5, else로 이동 5) high = 4 6) ..
dividend와 divisor의 부호 경우의 수를 4가지로 나눠서 빼가면서 계산할 경우에는 시간 제한에 걸린다. 이러면 bit 조작을 하라는 말이고... 쌈빡한 풀이가 있어 공유한다. https://leetcode.com/problems/divide-two-integers/discuss/1516367/Complete-Thinking-Process-or-Intuitive-Explanation-or-All-rules-followed-or-C%2B%2B-code Complete Thinking Process | Intuitive Explanation | All rules followed | C++ code - LeetCode Discuss Level up your coding skills and quickl..