0과 1의 쉼터

풀이 입력받은 이름에 대해 공통 부모를 갱신하며, 집합의 크기를 출력해야 되는 문제다. 공통 부모와, 집합의 크기를 저장할 parents, count 배열을 선언해주자. 문제에서 입력받은 친구 관계 F에 대해 입력받은 이름의 수는 최대 2F가 될 것이다. 때문에 위에서 선언한 배열의 크기 또한 2F로 할당받아야 한다. 모든 집합은 자기 자신에 대해 크기가 1이기에 count 배열은 1로 초기화 해주면 된다. 알다시피 parents 배열은 int형을 저장하는 배열이다. 때문에 입력받은 String형에 대해서는 Disjoint Set 구현이 불가능하다. 또한, parents 배열의 초깃값 설정을 할 때 자기 자신의 번호로 초기화를 해야하므로 String형 parent로 선언한다 하더라도 입력을 모두 받은 후..

풀이 새로운 사람이 오픈 채팅방에 입장하면 "ENTER" 이라는 문자열이 입력된다. 그 이후로 곰곰티콘을 사용한 사람이 총 몇명인지를 구하면 되는 문제이다. 즉, 새로운 사람이 들어온 후 곰곰티콘을 사용한 사람의 수를 구하면 된다. 일반적으로 채팅한 모든 사람들에 대해 몇 번 채팅했는지 살펴보는 방법은 O(N^2), N이 100,000이기에 시간초과가 발생할 것이다. 따라서 O(1) 만에 이미 채팅이력이 있는지 확인을 해주어야 한다. map과, set을 사용한 풀이들을 소개한다. HashMap 먼저 이름을 저장할 HashMap으로 nameList를 선언해주자. 누가 몇 번을 채팅했든 상관없이, 1번이라도 채팅했다면 곰곰티콘을 사용한 채팅이 아닌 평범한 채팅 기록이기 때문에 횟수를 계산할 필요가 없다. 때..

풀이 map을 사용해 간단히 풀이했다. 소스코드 #include #include #include using namespace std; int main(){ cin.tie(NULL); ios_base :: sync_with_stdio(0); int N, M; cin >> N >> M; map info; string site, pw; while (N--){ cin >> site >> pw; info[site] = pw; } while (M--){ cin >> site; cout

풀이 알고리즘은 엄청 간단하다. N명의 이름을 입력받아서 정렬 후, M명의 이름을 입력받아 이진탐색으로 찾은 명단과 총 인원을 출력하면 된다. 하지만, 이를 C로 구현하는 것은 끔찍하다... 소스코드 #include #include #include #include using namespace std; int main(){ int N, M, i; scanf("%d %d", &N, &M); vector v1(N), v2; char name[21]; for (i = 0; i < N; i++){ scanf("%s", name); v1[i] = name; } sort(v1.begin(), v1.end()); for (i = 0; i < M; i++) { scanf("%s", name); if (binary_sea..

풀이 구조체 배열의 index와 문자열을 이용해 숫자를 입력받을 떄는 별도의 탐색없이 출력이 가능하지만, 문자열 검색시에는 탐색을 필요로 하고, 이 과정에서 시간 초과가 발생해 map을 사용해 풀이했다. 소스코드 #include #include #include #include using namespace std; map name; map num; int main(){ int N, M; scanf("%d %d", &N, &M); char temp[21]; for (int i = 0; i < N; i++){ scanf("%s", temp); name[temp] = i; num[i] = temp; } for (int i = 0; i < M; i++){ scanf("%s", temp); if (temp[0]