전체 글657 [Codejam][2020][QR] 1. Vestigium 문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c Vestigium은 라틴어로 trace를 의미한다. 정사각형 행렬(let, arr)의 trace는 arr[i][i](왼쪽 위에서 오른쪽 아래까지의 요소들) 의 합이다. 정사각형 행렬이 주어질 때, trace의 값과 중복되는 요소가 있는 행, 열의 수를 각각 구해라. 예를 들어, 2 1 3 1 3 2 1 2 3 행렬이 주어지면 trace 값은 2 + 3 + 3 = 8. 중복되는 요소가 있는 행의 수는 0. 중복되는 요소가 있는 열의 수는 1열, 3열이 있으므로 2를 출력한다. trace값은 i = [0, N)을 탐색하면서 arr[i][i].. 2020. 4. 18. [leetcode][238] Product of Array Except Self 문제 : https://leetcode.com/problems/product-of-array-except-self/ 1보다 큰 양수들의 배열이 주어질 때 output[i] = nums[i] 를 제외한 나머지 nums 요소들의 곱 인 output 배열을 구하라. 단, 나누기는 쓰지말고 출력배열을 제외하고는 추가 메모리를 사용하지 말아라. n = nums 배열 크기라 하자. output[i] = nums[0] ~ nums[i-1] 의 곱. => nums를 앞에서부터 탐색하면서 output[i] = output[i-1] * nums[i-1] nums[i] = nums[i] ~ nums[n-1] 의 곱. => nums를 뒤에서부터 탐색하면서 nums[i] = nums[i] * nums[i+1] output[i].. 2020. 4. 16. [leetcode][678] Valid Parenthesis String 문제 : https://leetcode.com/problems/valid-parenthesis-string/ '(', ')', '*' 로 이루어진 문자열이 입력값으로 주어진다. *은 '(', ')'가 될 수 있고 빈 문자도 될 수 있다. * 가 특정 문자로 대체될 때, 괄호들의 쌍이 맞는 경우 유효한 문자열이라 한다. 입력 문자열이 유효한 문자열인지 판단해라. 여는 괄호가 나오는 인덱스를 저장하는 스택 하나와 '*' 가 나오는 인덱스를 저장하는 deque 하나를 사용한다. 입력된 문자열을 앞에서부터 탐색하면서 스택과 deque를 채운다. 1. 탐색중인 문자가 * 인 경우 deque의 뒤에 현재 인덱스를 채운다. 2. 여는 괄호인 경우 스택에 현재 인덱스를 push 한다. 3. 닫는 괄호인 경우 3-1. .. 2020. 4. 16. [leetcode][525] Contiguous Array 문제 : https://leetcode.com/problems/contiguous-array/ 이진수 배열이 주어질 때, 0과 1의 개수가 같은 subarray의 최대 길이를 구하라. 부분합을 키로 하고 해당 부분합이 처음으로 나타난 위치(1이 시작점)를 value로 하는 map을 만든다. 0이 나오는 경우 합에 -1을 해주고 1이 나오는 경우 +1을 한다. 현재 탐색하고 있는 인덱스를 i라 하고 만약 이때까지 나온 부분합들 중 현재까지의 부분합(0~i)을 키로 하는 value가 있다면 i - value가 정답이 될 수 있는 경우이다. 예를 들어, 0011 이 있다면 subSum은 0 -1 -2 -1 0 이 된다. 가장 처음에 있는 0(시작)도 반드시 필요. 이 경우 정답이 될 수 있는 경우는 빨간색과,.. 2020. 4. 13. [BOJ][11585] 속타는 저녁 메뉴 문제 : https://www.acmicpc.net/problem/11585 두번째 문장을 2개 이어붙인 문자열에서 세번째 문장이 몇 번 나오는지 찾는다. 이를 KMP로 찾을 수 있다. 주의할 점은 입력값이 ABCDE, ABCDE인 경우 정답은 1/5 이지만 2/5 가 출력된다. 두번째 문장을 2개 이어붙였기 때문에 ABCDEABCDE에서 실제로는 1개지만 빨, 파 2 번 나타났다고 판단했기 때문이다. 따라서 패턴문자열을 찾았을 때 첫번째 문자열을 시작으로 하는 부분문자열에서 패턴이 나타났다면 1을 빼준다. KMP로 구한 패턴문자열이 나타낸 횟수가 분자, 문자열 길이(N)가 분모가 된다. 기약분수는 최대공약수를 유클리드로 구해서 분자, 분모에 나눠주면 된다. 시간복잡도는 O(N). 소스코드 : https.. 2020. 4. 8. [leetcode][122] Best Time to Buy and Sell Stock II 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ 주식 가격 배열이 주어진다. 어떤 주식을 샀을 때 해당 주식을 팔기 전까지는 주식을 구입할 수 없다고 하자. 주식을 사고 판다고 했을 때 얻을 수 있는 최대 이익은 얼마인가? 투 포인터로 해결했다. 처음에는 DP로 했었는데 이건 그렇게하면 TLE 난다. 다시 생각해보니 주식을 사고 나서 최대가를 찍었을 때 파는 거다. 주식가격이 상승 곡선이 시작하기 전 가장 최소값을 찍었을 때, 주식을 구입한다. 상승 곡선이 끝날 때, 주식의 가격이 최대가 됐을 때 주식을 판다. 주식을 판 다음 날부터 다시 위 과정을 반복한다. 이를 배열 끝날때까지 반복한다. 상승 곡선이 끝나기 전에 배열이 종.. 2020. 4. 6. 이전 1 ··· 59 60 61 62 63 64 65 ··· 110 다음