목록전체 글 (179)
有希
문제를 잘 봐야 한다. 등장할 수 있는 숫자는 0이상 100 미만이다. 그러므로 vec의 공간은 딱 100만 잡으면 된다. 그리고 0도 출력해야 하므로 100 고정으로 잡야아 하고 동적으로 arr.size() 처럼 이상한걸 잡을 필요가 없다. 추가로, Counting Sort를 완성하려면 이제 저 빈도수를 저장한 ret을 순회하면서 해당 숫자의 빈도수만큼 다른 vec에 저장시키면 된다. 1이 3번, 2가 2번 섞여서 등장하는 배열이 있다면 1이 3번 2가 2번 있으므로 11122 이렇게 출력해주면 된다. 이게 Couting Sort 이다. vector countingSort(vector arr) { vector ret(100, 0); for(int i=0; i
대각합들의 차를 abs로 반환하는 문제. 행렬식을 내놓으라는 문제였으면 못 풀었다. int diagonalDifference(vector arr) { int left = 0; int right = 0; //left 00 11 22 ... NN //right 0N 1N-1 2N-2 NN-N int size = arr.size() - 1; for(int i=0; i
맨날 본 문제인듯? set으로 해볼까 하다가 이러면 숫자를 집어넣을때마다 있으면 빼고 없으면 insert 하고(탐색 비용 소모)를 반복하고 다 돌고나서 set에 마지막 하나 남은 녀석이 홀수개(1개) 있는 녀석이므로 return 하면 되는데, 이러면 n * log n 이다. map으로 하면 2n 돌리면 끝이니까 차라리 하던대로 map으로 했다. int lonelyinteger(vector a) { map nums; int ret = 0; for(int i=0; i
두 가지 방법이 있다. 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]
리플렉션? Runtime 중에 Class 클래스로부터 다른 클래스의 정보를 취득하거나 인스턴스를 생성하는 것. Class 클래스는 또 머여? 자바의 모든 클래스와 인터페이스는 컴파일 후 class 파일로 생성된다. class 파일에는 멤버변수, 메소드, 생성자 등 객체의 정보가 포함되어 잇는데, Class 클래스는 이 class파일에서 객체에 정보를 가져올 수 있다. 여담) 1년 정도 전에 외국 회사의 서류를 뚫고(!) 면접을 봤었는데 거기서 리플레션이 뭔지 아냐, 써봤냐에 대해 물어봤다. C++, nodejs를 만지적거리던 나는 당연히 몰랐고 이어지는 Iaas, Paas, Saas 등의 질문에 박살이 났고 떨어졌다 -_-... DI컨테이너가 리플렉션을 이용해 인스턴스를 생성하면 그에 따른 성능 저하?를..