목록프로그래밍/알고리즘+코딩테스트 (97)
有希
괜히 오기가 생겨서 처음 떠오른 아이디어로 풀다가 머리가 쪼개질 뻔하였다. STL은 쉬운데...막상 구조체로 직접 구현하려니 어려웠다. 1. 그냥 두 개 합친다음에, 버블정렬 같은거로 해도 될거 같다. 포인터 저장하는게 귀찮겠지만... 2. 나는 우선 head를 하나 만들고, 두 리스트에 따로 각자 Cur 포인터를 만들어서 head에서 다음 연결을 위해 두 리스트를 참조할 때, 각자의 Cur포인터를 타고 따라가 val을 찾고 선택한 node를 head->next 해준뒤, 해당 Cur는 전진시켜주었다. 8ms, 14.9MB. 73%보다 빠르다고 하니 맘에 든다. head = l1 or l2를 해서 원본이 훼손되는 것이 싫다면, head선언에서 null이 아닌 new ListNode()를 하면 된다. 다들 ..
괄호의 짝을 맞추는 문제. 간단하게 stack으로 여는 괄호면 넣고 닫는 괄호면 짝이 맞는지 확인한다. 주의할 점은 if에서 체크할 때 비어있는지 먼저 체크해야 한다. 안그러면 ch.top()을 통해 null을 보려고 하기 때문에 runtime에러가 발생한다. 0ms 6.4MB 사용. 같은 6.4MB사용해도 50% less than이 뜨는걸 보면 다들 반올림 정도의 오차정도만 있는거 같아서 더 최적화는 고려하지 않았다. class Solution { public: bool isValid(string s) { stack ch; for (int i = 0; i < s.size(); ++i) { switch (s[i]) { case '(': ch.push(s[i]); break; case '{': ch.pus..
여러 문자열이 벡터로 들어올 때, 그 녀석들의 가장 긴 접두어?를 찾는 것이다. 예시에 나와있듯이 flower, flow, flight에서 처음부터 시작해서 가장 긴 공통알파벳모음?은 fl이다. 우리가 이걸 찾는 과정을 그대로 따라 구현했다. flower에서 처음에 f니까, 나머지 단어들도 f로 시작하는지 보고.. flower에서 다음이 L이니까 나머지 단어들도 L로 시작하는지 보고.. class Solution { public: string longestCommonPrefix(vector& strs) { int min = INT_MAX; string ret = ""; for (int i = 0; i < strs.size(); ++i) { if (strs[i].size() < min) min = strs..
못풀고 낑낑대다가 해답에 손을 대고 말았다. 핵심은 '연속된 두 수를 비교했을 때, 작은 숫자가 앞에 온다면' 이다. 이런 경우에만 뒤쪽 수 - 앞쪽 수 한다. (IV = 5-1) 와 같이... 당연히 숫자 2개를 비교하니 루프는 사이즈-1 까지만 돌리고 마지막 숫자는 얄짤없이 더하는 숫자이니 그냥 더하면 된다. class Solution { public: int romanToInt(string s) { int sz = s.size(); //만약 길이가 1일 경우에는 맞는 숫자 찾아서 반환하면 된다. if (s.size() == 1) return hmap[s[0]]; int sum = 0; for (int i = 0; i < sz - 1; ++i) { int curNum = hmap[s[i]]; if (..
가운데 숫자를 기준으로 앞으로 읽으나 뒤로 읽으나 같은 수를 팰린드롬 숫자 라고 한댄다. 처음에는 문제를 잘못 이해하고, 가운데를 기준으로 했을 때 좌우가 같아야 한다고 생각하고 풀었다 ㅡㅡ; 24ms에 10MB 사용 class Solution { public: bool isPalindrome(int x) { //음수는 무조건 아니다 if (x < 0) return false; vector nums; while (x != 0) { nums.push_back(x % 10); x /= 10; } int loop = nums.size(); cout
올바른 자료구조를 사용할 수 있는지 묻는 문제 같다. 거꾸로니까 선입말출? 정도가 되겠다. queue를 사용하면 될듯.(%10으로 1자리부터 넣은다음 앞에서부터 빼면 거꾸로가 된다.) 혹은 while로 처리하던가. class Solution { public: int reverse(int x) { int ret=0; while(x!=0) { int pop = x%10; x/=10; if(ret>INT_MAX/10 || (ret==INT_MAX/10 && pop > 7)) return 0; if(ret INT_MAX / 10 || (ret == INT_MAX / 10 && q.front() > 7)) return 0; if (ret < INT_MIN / 10 || (ret == INT_MIN / 10 && ..