문제(원문)문제(번역)문자열 s가 주어졌을 때 중복되는 문자가 없는 가장 긴 부분 문자열의 길이를 구해라.단, s는 영어문자, 숫자, 기호, 공백이 들어갈 수 있다.접근 방법알파벳이면 26 정도로 범위를 잡으면 되지만, 이는 숫자, 기호, 공백이 모두 들어가서 어떻게 해야할지 감이 안잡혔다. 외부 라이브러리나 직접 dict 같은걸 구현하기에는 코드가 너무 길어질 것 같아서 고민하다가,아스키코드의 범위가 0부터 127이라는 것을 깨달았다. 즉 아스키 코드 범위에 대해서만 flag를 지정하고 매번 겹치는 문자가 있는지 검사하는 방법으로 코드를 구현했다. 소스 코드char map[128] = {0};void initMap(){ for(int t=0;tC언어로 작성한 코드인데, 아래와 같은 실행결과가 나..

문제(원문) 문제(번역)로마 숫자는 I,V,X,L,C,D,M으로 표현할 수 있다.로마 숫자는 보통 큰 수부터 작은 수를 왼쪽에서 오른쪽으로 쓴다. 하지만, 4를 표현할 때는 IIII 대신 IV를 사용한다.왜냐하면 4를 만들기 위해 5에서 1을 빼기 때문이다. 이러한 원칙은 9를 만들때도 사용된다.로마 숫자가 주어졌을 때 이를 정수로 바꿔라.접근 방법처음엔 단순히 로마 숫자 심볼을 정수로 바꾸려고 시도했다. 당연히 실패했다.보통은 큰 수부터 작은 수를 차례대로 쓰나, 일부 숫자를 만들기 위해는 작은수 큰수 순서대로 적힐 수 있다고 했다.이를 활용하자. 문자열의 오른쪽에서 왼쪽으로 순회하면서, 기존 수보다 현재 수가 작으면 빼주는 형식으로 만들면 된다.그게 아니고 기존 수보다 현재 수가 크면 더해주는 형태로..

문제(원문)문제(번역)needle과 haystack 문자열 변수가 주어졌을 때, haystack 안에 needle 변수에 있는 문자열이 처음 나타나는 인덱스를 반환하라.만약 존재하지 않는다면 -1을 반환하라.접근 과정단순하게 생각했다.이중 반복문을 이용해 needle 문자열이 haystack 문자열 안에 있는지 매번 확인했다. 먼저 문자열의 길이를 측정해 h와 n에 각각 저장했다.그리고 0 부터 h-n 까지 반복하면서 그 자리에서 n칸 앞으로 haystack에 needle 문자열이 있는지 확인했다.소스코드int strStr(char* haystack, char* needle) { int h = 0, n = 0, o = 0; while(haystack[h] != '\0') { h++;} w..

문제(원문) 문제(번역)columnTitle 변수의 문자열은 엑셀 시트의 열 제목을 나타낸다. 이에 해당 하는 열 번호를 반환해라.A=1B=2Z=26AA=27 ...접근 방법문자열을 뒤에서 부터 순회하면 될 거 같다는 생각이 들었다.DCBA 라는 열이 있다고 하자.뒤에서부터 첫번째까진 \(26^0 * 1\) 로 표현할 수 있다.뒤에서부터 두번째까진 \(26^1 * 2 + 26^0 * 1\) 로 표현할 수 있다.뒤에서부터 세번째까진 \(26^2 * 3 + 26^1 * 2 + 26^0 *1 \)로 표현할 수 있다.전체 열은 \(26^3 * 4 + 26^2 * 3 + 26^1 * 2 + 26^0 * 1 = 72385\) 로 나타낼 수 있다. 소스 코드#include int titleToNumber(char* ..

문제(원문)문제(번역)정수 배열 nums가 주어질 때, 부분수열의 합 중 가장 큰 합을 구하고 반환해라.접근 방법대표적인 DP문제다. (물론 divide and conquer 방식으로도 풀 수 있지만 코드가 복잡해진다..)현재 원소 이전까지의 합에 현재 원소를 더한 값과 현재 원소 중 더 큰 값을 저장해가면서 가장 큰 부분 수열의 합을 구하면 된다. 소스 코드int max(int a, int b) { return (a>b) ? a : b; }int maxSubArray(int* nums, int numsSize) { int dp[100002] = {0}; int m = nums[0]; dp[0] = nums[0]; for(int i = 1; i이러면 추가 공간 배열이 필요하므로 공간..

문제(원문)문제(번역)크기가 n인 nums 배열이 주어질때, majority 요소를 반환해라.majority 요소는 n/2 이상 등장하는 원소로, majority 요소는 항상 배열에 등장한다고 가정해라. 이 문제를 선형 시간과 O(1)의 공간복잡도로 풀어라. 접근 방법이 문제에서는 majority 요소가 n/2 번 이상 등장한다고 보장이 되어 있다.아무 수를 잡고 해당 수의 등장 횟수를 증감시키다가, 등장횟수가 0이 되면 다른 수로 교체하는 방법을 반복해서 사용하면 majority 요소를 구할 수 있다.소스 코드int majorityElement(int* nums, int numsSize) { int num, cnt=0; for(int i=0;i 추가적인 변수도 단 2개만 사용했으므로 공간복잡..

문제(원문)문제(번역)비어있지 않은 정수 배열 nums에는 하나를 제외한 모든 요소가 정확히 2번 등장한다. 그렇지 않은 하나를 찾아라.이 문제를 풀때 선형시간과 상수 개의 추가 공간만 사용할 수 있습니다. 접근 방법처음에는 nums 만큼의 새로운 배열을 만들고 0으로 초기화해서 모든 수를 세고, count가 2가 아닌것을 찾으려고 했다.이러면 O(n)의 시간복잡도를 갖지만, 공간복잡도가 O(n)이 되면서 문제의 제약조건을 만족하지 못한다. Hint 1에는 XOR(^) 연산자의 특성을 고려하라고 나와 있다. (XOR연산자에 대해 자세한 내용은 이 글을 읽어주세요)XOR 비트연산은 두 비트가 같으면 0, 다르면 1을 반환한다. 즉 같은 두 수에 대해서는 0을 반환한다는 것이다.그리고 무려 교환법칙과 결합..

문제(원문)문제(번역)정수 배열 nums가 주어졌을 때, 배열 속 모든 0을 0이 아닌 원소의 순서를 유지하며 오른쪽 끝으로 이동해라.이 문제를 풀 때 배열을 복사하지 말고 in-place(추가적인 배열 공간을 선언하지 않고)로 풀어야 합니다. 접근 방법처음에는 in-place 제한을 보지 못했다.새 배열을 선언하고, 기존 배열을 순회하면서 0이 아닌 원소만 새 배열에 추가하고 남은 만큼 0을 채우는 솔루션을 생각했다.이러면 \(O(N)\)으로 문제를 풀 수 있다. in-place 제한을 보고 난 뒤에는 배열을 순회하면서 0을 만나면, nested loop를 사용해 가장 가까운 0이 아닌 수를 찾고 swap을 하게 코드를 작성했다. 이러면 \(O(n^2)\)으로 풀 수 있다. 하지만 조금만 더 최적화를 ..

문제(영어)문제(번역)정수 n이 주어질때, n!에서 오른쪽 끝에 있는 0의 개수를 구해라.n! = n * (n-1) * ... * 2 * 1 인 것을 기억해라. 접근 방법 팩토리얼 결과의 맨 뒤에 0은 언제언제 붙을까? 0은 10이 곱해질때마다 생길 것이다. 그럼 10은 2와 5의 곱으로 생긴다.우리는 여기에서 5에 집중을 해야 한다.2는 생각보다 자주 나오지만, 5는 자주 나오지 않는다.즉 뒤에 붙는 0의 수는 5가 나오는 수와 동일하다고 간주하면 된다!그럼 답이 정말로 간단해진다. 소스코드int trailingZeroes(int n) { int c = 0; while(n > 0) { c += ( n/=5 ); } return c;} 공간복잡도도 O(1)이고, 해당 ..

문제(영어) 문제(번역)너는 계단을 오르고 있다. 꼭대기에 다다르려면 n 걸음이 걸린다.한번에 1칸 또는 2칸 오를 수 있다. 정상에 다다르려면 몇가지 구별되는 방법이 있나요? 접근 방법문제를 보자마자 DP가 생각났다.정상이 1인 경우, 갈 수 있는 경우의 수는 1칸만 이동하는 1개 밖에 없다.정상이 2인 경우, 1칸 이동하고 1칸을 이동하거나 바로 2칸을 이동하는 경우가 존재한다.정상이 3인 경우, 1번째 칸에서 올라오거나 2번째 칸에서 올라올 수 밖에 없다. 즉, 정상 t에 오르기 위해서는 t-1에 오는 방법의 수와 t-2에 오는 방법의 수를 더하면 된다! 코드int climbStairs(int n) { int array[46] = {0}; array[0] = 0; array[1] =..