greedy31 [leetcode][1209] Remove All Adjacent Duplicates in String II 문제 : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/ {문자, 문자가 연속으로 나온 횟수}를 요소로 하는 stack을 하나 만든다. 문자열 s를 앞에서부터 탐색하면서 스택이 비어있거나 스택 top에 있는 요소의 문자가 탐색중인 문자와 같다면 top 요소의 문자가 연속으로 나온 횟수를 +1 해준다. 그리고 만약 스택 top의 연속 횟수가 k와 같다면 stack을 pop 시킨다. 모든 문자열 s를 탐색하면서 stack을 세팅했다면 stack을 pop하면서 정답 문자열 앞에 문자열을 추가하면서 정답을 구할 수 있다. 시간 복잡도는 O(N). (N = |s|) 소스코드 : https://github.com/fpdjsns/A.. 2019. 10. 3. [leetcode][1190] Reverse Substrings Between Each Pair of Parentheses 문제 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1190.%20Reverse%20Substrings%20Between%20Each%20Pair%20of%20Parentheses.cpp 스택을 사용했다. Example 3: "(ed(et(oc))el)" 을 예로들어보자. 여는 괄호가 시작될때마다 스택을 하나씩 생성해서 이후에 나오는 문자들을 최근 스택에 쌓는다. 스택이 하나도 없는 경우 문자열 순서에 변경이 없을 것이기 때문에 정답 문자열의 뒤에 추가한다. 닫는 괄호가 나오면 최근 스택을 pop하면서 이전 스택에 push한다. 스택을 pop할때 이전 스택이 없는 경우 (스택이 하나인 경우) 정답 문자열에 추가한다. 시간복잡도는 O(|s|^2).. 2019. 10. 1. [leetcode][1200] Minimum Absolute Difference 문제 : https://leetcode.com/problems/minimum-absolute-difference/ arr 배열을 오름차순으로 정렬한다. b - a 값은 오름차순 정렬시 바로 옆에 있는 요소들의 차가 최소 값이 된다. 따라서 정렬된 arr 배열을 앞에서부터 탐색하면서 [arr[i], arr[i-1]]가 [a, b]이다. arr[i-1] - arr[i] 값을 구하고 이 값이 이때동안 계산한 diff의 최소값보다 크다면 정답이 될 수 있으므로 skip. diff 최소 값이랑 같다면 정답배열에 추가. diff 최소 값보다 작다면 이때동안 구한 정답 배열을 빈 배열로 초기화 시키고 정답 배열에 추가한다. 시간복잡도는 정렬하는데 걸리는 시간인 O(NlogN). 소스코드 : https://github.. 2019. 9. 22. [algospot][STRJOIN] 문자열 합치기 문제 : https://algospot.com/judge/problem/read/STRJOIN 그리디로 풀었다. 문자열의 길이가 가장 짧은 것 2개 부터 차례로 합쳐나간다. 최소 힙에 문자열들을 넣고 top에 있는 것 2개를 꺼내서 두 문자열의 길이의 합을 정답에 더해나간다. 최소 힙에 있는 문자열이 1개 남을 때까지 이를 반복한다. 최소 힙에서 특정 원소를 추가하는 작업은 O(logN)이므로 총 시간복잡도는 O(NlogN)이 된다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/STRJOIN.cpp fpdjsns/Algorithm 알고리즘 정리. Contribute to fpdjsns/Algorithm development by cr.. 2019. 7. 13. [algospot][LUNCHBOX] Microwaving Lunch Boxes 문제 : https://algospot.com/judge/problem/read/LUNCHBOX 그리디하면 나오는 단골 문제. 전자레인지에 돌리는 행동은 선형적이지만 먹는 것은 병렬적으로 처리할 수 있다. 따라서 시간을 효율적으로 사용하려면 중요한 건 먹는 시간이다. 병렬적으로 처리된다고 했을 때 가장 먼저 시작되어야 하는 것은 시간이 가장 오래 걸리는 것이다. 따라서 도시락을 먹는 시간의 내림차순으로 정렬하고 이 때 모든 도시락을 데우고 먹는 데 걸리는 시간(1)을 구하면 이 결과가 정답이 된다. (1)을 구하는 방법은 도시락을 정렬한 뒤 앞에서부터 탐색하면서 데우는 시간과 먹는 시간을 누적해간다. 데우는 시간은 선형적이므로 각 도시락의 데우는 시간의 합이다. 누적된 먹는 시간은 도시락을 데울 때 그 .. 2019. 7. 13. [algospot][MATCHORDER] 출전 순서 정하기 문제 : https://algospot.com/judge/problem/read/MATCHORDER 그리디로 풀었다. 한국팀이 지는 경우는 무시하고 이기는 경우만 고려해보자. 한국이 이길 수 있을 때 최대 효율은 가장 적은 레이팅을 가진 선수로 이기는 경우이다. 따라서 먼저 선수들의 레이팅을 오름차순 정렬했다. 그리고 러시아팀의 레이팅을 앞에서부터 탐색한다. 한국팀 선수의 인덱스 변수(korInd)를 하나 두고 이를 0으로 초기화한다.(한국팀의 레이팅도 앞에서부터 탐색.) 탐색 중인 러시아팀의 레이팅보다 같거나 큰 한국팀 레이팅이 나올 때까지 korInd를 증가시킨다. 찾는 경우 정답 + 1을 하고 korInd는 이미 특정 러시안 선수와 매칭 되었으므로 더이상 사용하지 못한다. 따라서 korInd도 +1.. 2019. 7. 13. 이전 1 2 3 4 5 6 다음
