https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 풀이 과정 #include #include #include #include #include using namespace std; map m; map m1; vector v; bool cmp(pair a, pair b) { if (a.first == b.first) return m1[a.second] b.first; } int main() { ios::sync_with_stdio(f..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이과정 map의 find 함수를 알게 해 준 문제이다. res를 입력받고 res의 key값을 찾으면 그에 맞는 value를 출력해주면 된다. #include #include #include #include #include using namespace std; int N, M; string adress, passwd, res; int main() { ios::sync..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이과정 처음에는 단순히 배열에 값을 넣어서 있으면 cnt하는 반복문을 돌렸었다. 그러나 실버3은 역시 간단할리 없었다. map에 string 값을 key로 넣고 bool 값을 value로 넣어서 bool이 true라면 값이 있었다는 뜻이므로 cnt를 해줬다. #include #include #include #include using namespace std; in..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이과정 처음 풀어본 map 문제라 조금 헤맸던 문제이다. mp1은 string-key 값을 넣으면 int-value값이 나오는 맵이며, mp2는 int index 값을 넣으면 string이 나오는 기본적인 배열이다. #include #include #include #include using namespace std; int N, M; string str, quest;..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이과정 string을 key로 하고, int를 value로 한다. 팔린 책의 개수인 second 개수가 가장 큰 값을 res에 넣는다. 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력해야 되니 팔린 책의 개수인 second 개수가 res일 경우에 first인 key를 출력해주고 함수를 끝낸다. (map은 삽입이 되면서 오름차순으로 자동 정렬된다.) 반복문 데..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이과정 기본 문제인 것 같았지만, 생각해야 될 것이 많았던 문제이다. 입력을 받고 나서, 두 노드의 부모가 다른 집합일 때와 같은 집합일 때로 나눈다. 다른 집합일 때는 부모의 노드를 통일시켜주고, 만약에 두 부모 중 한 집합이라도 사이클이 존재한다면 두 집합 모두 사이클로 변경해준다. 같은 집합일 때는 시작 노드를 사이클로 변경해준다. 만약 사이클이 존재한다면 넘어가주고, 사..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이과정 이 문제는 유니온 파인드와 map 알고리즘이 섞인 문제이다. 유니온 파인드 알고리즘을 하려면, 처음에 parent 배열에 각자 자신의 번호로 초기화시켜준다. 한 줄에 2명씩 입력되므로 최대 노드 개수는 2 * F 개가 된다. 입력을 받을 때, 만약 map.count가 0이라면 idx를 넣어주고 1씩 플러스 해준다. 그다음 unionParent 함수를 실행하고, 다른 집합일 경우..