본문 바로가기

Set7

[programmers][월간 코드 챌린지 시즌1] 두 개 뽑아서 더하기 문제 : programmers.co.kr/learn/courses/30/lessons/68644 정수형 배열이 주어질 때 서로 다른 인덱스 수를 두 개 골라서 합했을 때 나올 수 있는 수들을 오름차순 정렬해서 반환해라. 적절한 자료구조 쓸 수 있나. 묻는거 같은 문제. 나올 수 있는 수 -> 중복 x. set에 저장한다. for(i=0 ~ n-1) for(j=i+1 ~ n-1) set.insert(num[i] + num[j]) 시간복잡도는 O(NlogN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9.. 2020. 9. 15.
[programmers][찾아라 프로그래밍 마에스터] 폰켓몬 문제 : https://programmers.co.kr/learn/courses/30/lessons/1845 총 N 마리의 폰켓몬 중 N/2 마리를 가져갈 수 있다. 최대 고를 수 있는 폰켓몬 종류의 수를 구해라. 최대로 고를 수 있는 폰켓몬 종류의 수는 N마리의 폰켓몬 종류의 수와 N/2 중 최소값이다. N/2는 계산으로 한 번에 구할 수 있고 총 폰켓몬 종류의 수를 구하기 위해 set에 폰켓몬 종류를 저장한다. 모든 폰켓몬을 저장했을 때 set의 크기가 콘켓몬 종류의 총 수가 된다. 시간복잡도는 set을 만드는데 소요되는 시간인 O(NlogN) 소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%B0%BE%EC%95%84%EB%9D%BC%.. 2020. 9. 13.
[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][1207] Unique Number of Occurrences 문제 : https://leetcode.com/problems/unique-number-of-occurrences/ set, map을 사용. arr 배열을 탐색하면서 set에 arr[i]들을 저장한다. map은 arr[i]이 나온횟수를 저장하는 cnt, cnt의 value가 나온 횟수를 저장하는 num. 총 2개의 map을 준비한다. 즉, arr = { 1, 2, 2, 1, 1, 3, 2 } 이라면 cnt = { (1, 3), (2, 3), (3, 1) } num = { (1,1), (3, 2) } 이 된다. arr 배열을 탐색하면서 map1, map2개를 세팅한다. 그리고 num[i] = 1 이 되는 모든 i의 개수(uniqueNumCnt)를 구한다. 위 예제에서는 1이 된다. 만약 uniqueNumC.. 2019. 10. 2.
[leetcode] 1172. Dinner Plate Stacks 문제 : https://leetcode.com/problems/dinner-plate-stacks/ let) capacity = 2 index 0 1 2 3 stack 4 1 3 5 fullStack : 가득찬 스택 인덱스 (2) blankFullStack : fullStack 사이사이의 index (0, 1, 3(3인덱스 스택이 가득찼다가 삭제된 경우)) stackMap : key - index, value - stack ({0, {1}}, {2, {4,3}}, {3, {5}) push 처음 push하는 경우는 0번 인덱스 stack에 push. 가득찬 스택들 중간에 빈 곳이 있는 경우(blankFullStack이 있는 경우) 빈 곳 중 가장 왼쪽에 넣어준다. 왼쪽부터 차례대로 스택들이 모두 차있는 경.. 2019. 8. 30.
[BOJ][1181] 단어 정렬 문제 : https://www.acmicpc.net/problem/1181 문제 조건 중 단어가 여러 번 입력된 경우 한 번씩만 출력을 하라는 항목이 있다.그래서 중복을 제거하기 위해 set을 이용해서 풀었다.그리고 set의 정렬 조건을 수정하였다. 정렬 조건은만약 비교하는 문자열 2개의 길이가 다르다면 앞에 있는 문자열이 길이가 더 짧은 경우 true, 앞에 있는 문자열이 길이가 더 긴 경우 false를 반환.문자열 2개의 길이가 같다면 사전순 정렬로 되어있으면(앞에 있는 문자열 < 뒤에 있는 문자열) true, 아닌 경우 false를 반환한다. C++ set.insert 의 시간복잡도는 O(log(set.size()) 이므로, 총 시간복잡도는 대략 O(NlogN) 소스코드 : https://gist... 2019. 1. 6.

티스토리툴바