백준84 [11478] 서로 다른 부분 문자열의 개수 문자열 슬라이싱과 관련된 문제이다 string에 내장되어있는 substr 함수를 사용하여 문자열의 일부를 집합에 넣는다 substr(i, j) : i번째 인덱스부터 j개의 문자를 반환함 또한 이중 for문을 이용하여 겉 for : 몇 개의 문자를 반환할건지 ( 1개 ~ 문자열 길이 ) 안 for : 어디 index부터 문자열을 새로 만들건지 ( 0 ~ 문자열 길이 - 1 ) 구상했다 사실 만들 수 있는 문자열의 개수가 중요한 것이지, 그 안에 있는 문자열이 정렬될 필요는 없다 그래서 시간이 훨씬 빨리 걸리는 unordered_set을 이용하여 중복된 값만 없애주고, 빠르게 동작(시간 복잡도 O(1))하여 최종 문자열의 개수를 출력하였다 완성된 코드는 아래와 같다 #include #include #incl.. 2022. 7. 30. [1269] 대칭 차집합 대칭 차집합 : (A-B) U (B-A) 처음에는 메모이제이션을 이용하여 배열을 크게 잡았더니 메모리 초과가 났다 #include using namespace std; int N, M; int A[100000001]; int B[100000001]; int larger1 = -1; int larger2 = -1; int cnt; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> M; for (int i = 0; i > input; A[input]++; if (input > larger1)larger1 = input; } for (int i = .. 2022. 7. 30. [1764] 듣보잡 듣지도, 보지도 못하는 명단의 교집합을 구하는 문제이다 듣도 못한 사람을 집합에 insert한 다음, 보도 못한 사람이 집합에 있는지 찾는다 찾으면 새로운 string 배열에 넣고, 듣보잡의 수를 1 증가시킨다 모두 탐색하고 난 후 string 배열을 사전순으로 정렬한 다음 출력한다 #include #include #include using namespace std; int N, M, cnt; set myset; string Answer[500000]; bool cmp(string a, string b) { // 사전순 정렬 return a >.. 2022. 7. 29. [10816] 숫자 카드 2 hash를 이용한 map 또는 set을 쓰라고 권유했지만 난 구조체를 썼다 구조체 사랑해 key값의 중복을 허용하는 multiset을 사용하였다 하지만 내장된 count함수를 사용하니 시간초과가 떴다 #include #include using namespace std; int N, M; multiset myset; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N; for (int i = 0; i > input; myset.insert(input); } cin >> M; for (int i = 0; i < M; i++) { int input; cin.. 2022. 7. 29. [1620] 나는야 포켓몬 마스터 이다솜 일단 도감 순서와 문자열 알파벳 순서가 일정하게 정렬되어있지 않다 key값으로 정렬하면 문자열이 정렬이 안되고, value로 정렬하면 도감 순서가 뒤죽박죽이 되었다 map을 사용하니 시간초과가 발생하였다 그래서 찾는 시간이 빠르다는 unordered_map을 사용했다 hash map이랑 유사하다고 보면 된다 map보다 빠른 탐색이 가능하며, 시간복잡도는 O(1)이다 중복된 데이터를 허용하지 않는다 unordered_map 2개를 사용하였는데 결론적으로 보면 그냥 구조체 배열 2개를 써도 괜찮았을 거라는 생각이 든다 key가 숫자인 경우와 key가 문자열인 경우를 나눠 unordered_map 2개를 사용하였다 myunorderedmap1 : key가 숫자임. 도감순서로 포켓몬 이름을 찾을 때 사용 myu.. 2022. 7. 27. [14425] 문자열 집합 집합에 문자열들을 넣고, M개의 문자열 중에서 집합에 있는 문자열과 동일하면 count를 해줘서 총 몇 개가 있는지 출력한다 set이란 노드 기반 컨테이너이며 균형 이진트리로 구성되어있다 key값은 중복이 허용되지 않고, insert에 의해 삽입이 되면 원소는 자동으로 정렬(default는 오름차순)된다 "[10815] 숫자 카드" 와 비슷한 문제여서 설명을 생략한다 https://kmyobin.tistory.com/27 [10815] 숫자 카드 집합을 이용한다 set이란 노드 기반 컨테이너이며 균형 이진트리로 구성되어있다 key값은 중복이 허용되지 않고, insert에 의해 삽입이 되면 원소는 자동으로 정렬(default는 오름차순)된다 상근이가 kmyobin.tistory.com #include #i.. 2022. 7. 27. [10815] 숫자 카드 집합을 이용한다 set이란 노드 기반 컨테이너이며 균형 이진트리로 구성되어있다 key값은 중복이 허용되지 않고, insert에 의해 삽입이 되면 원소는 자동으로 정렬(default는 오름차순)된다 상근이가 가지고 있는 숫자 카드 N개를 집합으로 입력받은 후, 입력받은 카드가 있는지 find()함수를 이용하여 찾는다 auto pos = myset.find(x); 변수 x가 myset에 들어있지 않다면 pos는 myset.end()를 출력한다 만약 찾는다면 1을, 못찾았다면 0을 출력하도록 구현한다 #include #include using namespace std; int N, M; set myset; int main() { ios::sync_with_stdio(false); cin.tie(nullptr).. 2022. 7. 27. [18870] 좌표 압축 N의 조건, Xi의 조건이 명시되어 있다 처음에는 집합이 오름차순 정렬, 중복 제거가 되는 장점이 있어 아래와 같이 코드를 구현해보았다 #include #include #include using namespace std; int N; int A[1000000]; set B; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N; for (int i = 0; i > A[i]; B.insert(A[i]); } for (int i = 0; i < N; i++) { set::iterator iter = B.begin(); int j = 0; for (iter;; iter++) { if ((*iter) == A[i]) .. 2022. 7. 22. [1181] 단어 정렬 1. 길이가 짧은 순으로 2. 길이가 같으면 사전 순으로 정렬하는 문제이다 char형 배열로 할까 고민했지만 string 배열로 문제를 풀었다 같은 단어가 입력될 수도 있으므로 같은 단어가 입력되면 배열에 넣지 않았다 algorithm 라이브러리에 있는 sort함수를 이용하였다 근데 조건이 2개 있으니 cmp 함수를 만들어 주었다 사전순으로 정렬하려면 a N; for (int i = 0; i > input; for (int j = 0; j < k; j++) { if (input == A[j]) { isit = true; break; } } if (isit == true) {} // 이미 입력되어있으면 pass els.. 2022. 7. 22. [2108] 통계학 구해야 할 것은 총 4가지이다 1. 산술평균 : (N개의 수들의 합 / N)을 소수 첫째 자리에서 반올림한 값 2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 때 중앙에 위치하는 값 3. 최빈값 : N개의 수들 중 가장 많이 나타난 값 4. 범위 : N개의 수들 중 최댓값 - 최솟값 입력을 어떻게 받을까 고민했다 최빈값을 위해 num의 빈도수를 나타내는 cnt 변수를 사용하였다 그리하여 num, cnt 두 변수를 담는 구조체 배열을 선언해주었다 입력을 받을 때는 이미 입력됐었던 수인지 일단 따져본다 입력된 적이 있던 수라면 ? -> cnt만 1 증가 새로 입력된 수라면 ? -> num 대입, cnt 1 증가 1. 산술평균 for문을 돌리면서 입력을 받을 때 sum을 더해준다 그리고 그것을 N으로 .. 2022. 7. 17. 이전 1 ··· 5 6 7 8 9 다음
