전체 글405 [C++] LeetCode - Remove Duplicates from Sorted Array (Hash Map) 이번에는 Remove Duplicates from Sorted Array 문제를 다뤄봤습니다. 저는 Hash Map을 활용하여, 이게 중복된 값인지 아닌지 여부를 확인하는 식으로 진행했습니다. 문제 정의 접근 방법 while loop을 통해 원소 하나하나씩 보면서, 해쉬 맵에 저장된 형태라면 중복된 값이므로 pass. 저장되지 않았다면 중복되지 않았으므로 그대로 유지합니다. 중복일 경우, 제공된 벡터 값에 -101을 넣어 알 수 있게 합니다. 마지막에 for 문을 통해 -101이 아닌 값들만 가져옵니다. 결과 Runtime: 12 ms, faster than 66.91% of C++ online submissions for Remove Duplicates from Sorted Array. Memory U.. 2022. 1. 14. [C++] LeetCode - Merge Two Sorted Lists 이번에는 merge two sorted lists를 풀어봤습니다. 역시나 쉬운 예제이며, linked list가 2개가 주어지고, 작은 순서대로 차례차례 새로운 링키드 리스트를 만드는게 목표입니다. 문제 정의 접근 방법 두 리스트 중 하나라도 nullptr가 아니라면, 계속 while loop 이 돌아갑니다. 차례차례 next를 써가면서 원소의 값을 비교하고, 작은 것을 선택한 뒤 정답 리스트에 추가합니다. 단순합니다. 만약 두 리스트 중 하나가 nullptr인지도 체크해서 메모리 에러가 발생하지 않도록 주의합니다. 결과 확실히 쉬운 문제는 고수들이 없는건지, 답이 한정적인건지 생각보다 런타임이 빠르게 나옵니다. 메모리 사용은... 자료구조에 대해 좀 더 이해가 필요한 것 같아요. Runtime: 8 m.. 2022. 1. 13. [C++] LeetCode - Valid Parentheses (Stack) 그 유명한 괄호 열고 닫기 문제입니다. 열었을 때 스택에 추가하고, 닫았을 때 스택에서 제거하는 방식을 통해 정합성을 확인합니다. Stack 스택은 LIFO를 따르는 자료 구조 (Last in First out) push: 스택의 끝에 값이 추가 pop : 스택의 끝의 값을 날려버림. top : 스택의 끝의 값을 구함. stack st; st.push('('); st.top(); st.pop(); 등으로 활용. 문제 정의 접근 방법 여는 괄호는 스택에 push, 닫는 괄호는 스택에 pop하되, top의 값의 괄호가 맞는지를 확인한다. 실행 결과 딱히 좋진 않지만 차이가 미미합니다. 얼마나 if문을 최대한 줄이고, false 조건일 때 빨리 리턴하느냐에 따라 다른 정도. Runtime: 3 .. 2022. 1. 12. [C++] LeetCode - Longest Common Prefix 딱히 어떤 자료구조나 알고리즘을 사용할지 애매한 문제인 것 같습니다. 그저 완전탐색처럼 다 보는 수밖에 없겠다 싶은 문제같아요. 문제는 직관적이고 딱히 어렵지 않습니다. 문제 정의 접근 방법 모든 원소들에 대해 첫 문자부터 지켜보면서 같은지 판별합니다. 만약 하나라도 다른 케이스가 발생한다면, 그 전의 문자까지만 정답에 집어넣습니다. 가장 길이가 짧은 원소를 구하고, 그 길이 만큼만 while loop이 실행되도록 합니다. 만약 문자열 1개만 주어졌을 경우, 그 자체가 정답이 되므로 while loop이 돌기 전에 return 합니다. 결과 웬일인지 다른 제출안들보다 비교적 좋은 평가를 받았네요. 너무 별거 없어서 고수들이 참여를 안했나봅니다.. Runtime: 3 ms, faster than 75.16.. 2022. 1. 11. [C++] LeetCode - Roman to Integer (Map) LeetCode의 1위부터 100위까지 순서대로 하려고 했는데, 생각보다 난이도가 어려운 문제는 시간이 너무 오래 걸려서... 연습차원에서 EASY 등급부터 모두 끝내기로 했습니다. 어려운 문제는 아닌데, C++을 하면서 char, string 등을 구분해야하는 트뤼키한 부분이 있었습니다. 문제 정의 로만 문제를 정수로 변환하는데 규칙이 있습니다. 보통은 큰 숫자가 앞에 나올 수 있는데, 6가지 케이스에 대해서는 작은 숫자가 먼저 나올 수 있다고하네요. 접근 방법 문제를 두번 풀었습니다. 처음에는 for문을 통해 첫 글자와 다음 글자를 비교하고, 6가지 케이스에 해당하면 각각 값을 더하는 식으로 했습니다. 아래 코드를 보시면 아시겠지만 좀 더러운 코드 같다는 느낌이 들고, 하위 5%의 속도로 결과를 맞출.. 2022. 1. 10. [C++] LeetCode - Add Two Numbers (Linked List) 이번에는 linked list를 다루는 Add Two numbers 문제를 풀어봤습니다. linked list는 c++ 공부할 때 꼭 나오는 자료구조인데, 말그대로 포인터와 value로 이루어진 원소들이 서로 링크되어 있는 겁니다. next 를 통해서 링크를 타고 다음 원소로 넘어갈 수 있는데요. 깔끔한 풀이는 아니고, 속도 면에서 하위권에 속해있긴 하지만 어쨌든 풀게되었네요. 다른것보다 c++로 linked list를 다루려니, 문법적으로 잘 적응이 안되어 시간이 오래 걸렸네요. 만약 코딩 인터뷰에서 이렇게 헤맸으면 광탈날 뻔 했습니다. 문제 정의 접근 방법 두 개의 리스트가 nullptr가 아닐 때 차례대로 접근합니다. 두 수의 합이 10을 넘어가면, cnt 값에 1을 줘서, 다음 계산 시 더하게 합.. 2022. 1. 7. 이전 1 2 3 4 ··· 68 다음
