3. Brute Force (1)

 

안녕하세요, ICMP입니다.

오늘은 저번 시간에 이어서 InterestingParty 문제를 풀어 보도록 하겠습니다.

 

 

참고 내용)

Brute Force(전체 탐색) ??

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

 

 

Problem Statement

Mr. White is a very versatile person - absolutely everything is interesting to him. Perhaps this is why he has many friends.

(화이트 씨는 매우 다재다능한 사람이다. 그는 정말 모든 것이 흥미롭다. 아마도 이것이 그에게 친구가 많은 이유일 것이다.)

 

Quite unfortunately, however, none of his friends are versatile at all. Each of them is interested only in two topics and refuses to talk about anything else.

(하지만 불행히도 그의 친구 중 다재다능한 사람은 하나도 없다. 그들 각자는 두 가지 주제에만 관심을 갖고 다른 얘기는 하지 않으려 한다.)

 

Therefore, each time Mr. White organizes a party, it's a big problem for him to decide whom to invite so that the party is interesting to everybody.

(그러므로 화이트 씨가 파티를 열 때마다, 모든 사람들에게 그 파티가 흥미롭도록 누구를 초대할지 결정하는 것은 그에게 큰 문제다.)

 

Now that Mr. White has a lot of experience in organizing parties, he knows for sure that a party will be interesting if and only if there's a topic interesting to each of the invited friends.

(화이트 씨는 파티를 조직해 본 경험이 많기 때문에 초대받은 친구들 각각에게 흥미로운 주제가 있다면, 그리고 있어야만 파티가 재미있을 것이라는 것을 그는 확실히 알고 있다.)

 

You will be given s first and second. The i-th friend of Mr. White is interested in topics first[i] and second[i]. Return the largest number of friends that Mr. White can invite to his party so that the party will be interesting.

(너는first, second가 주어질 것이다. 화이트 씨의 i 번째 친구는first[i]와second[i]에 관심이 있다. 화이트 씨가 파티에 초대할 수 있는 가장 많은 친구들을 돌려보내 파티가 재미있을 것이다.)

 

 

Definition

 

Class: InterestingParty

Method: bestInvitation

Parameters: String[], String[]

Returns: int

Method signature: int bestInvitation(String[] first, String[] second)

(be sure your method is public)

 

 

Constraints

 

- first will contain between 1 and 50 elements, inclusive.

- second will contain the same number of elements as first.

- Each element of first and second will contain between 1 and 15 characters, inclusive.

- Each character in first and second will be a lowercase letter ('a'-'z').

- For each valid i, first[i] will not be the same as second[i].

 

(

-first는1에서 50의 요소를 포함해야 한다.

-second는first와 동일한 수의 원소가 포함될 것이다.

-first와second의 각 요소는 1에서 15자 사이의 문자를 포함한다.

-first와second문자는 소문자('a'-'z')가 된다.

- 각 유효 i에 대해first는second[i]와 같지 않다.

)

 

 

Examples

 

0)

{"fishing", "gardening", "swimming", "fishing"}

{"hunting", "fishing", "fishing", "biting"}

Returns: 4

This is a very easy case since everybody is interested in "fishing".

 

1)

{"variety", "diversity", "loquacity", "courtesy"}

{"talking", "speaking", "discussion", "meeting"}

Returns: 1

Despite being interested in "talking", "speaking", "meeting" and so on, these people have nothing to talk about with each other.

 

2)

{"snakes", "programming", "cobra", "monty"}

{"python", "python", "anaconda", "python"}

Returns: 3

Mr. White can invite friends 0, 1, 3 (0-based) and they will have an interesting evening talking about "python" (or at least Mr. White thinks so).

 

3)

{"t", "o", "p", "c", "o", "d", "e", "r", "s", "i", "n", "g", "l", "e", "r", "o", "u", "n", "d", "m", "a", "t", "c", "h", "f", "o", "u", "r", "n", "i"}

{"n", "e", "f", "o", "u", "r", "j", "a", "n", "u", "a", "r", "y", "t", "w", "e", "n", "t", "y", "t", "w", "o", "s", "a", "t", "u", "r", "d", "a", "y"}

Returns: 6

 

 

문제 분석

 

1. 상황 이해하기( first, second 배열의 역할 이해)

초대할 대상의 취미 두 가지를 각각 first, second 배열로 입력을 받습니다.

(제시 조건에 따라 first, second의 요소 내용은 다르나, 개수는 같습니다.)

 

파티를 주최할 때 가능한 많은 사람을 초대하기 위해서 많은 사람들이 관심 있어 하는 주제를 찾아내고, 그때의 인원수를 출력해야 합니다.

 

2. 발생할 상황 분기 예측

각각의 관심사를 비교하기 위해 제시 조건의 '각 유효 i에 대해first는second[i]와 같지 않다.'를 이용하겠습니다.

위의 제시 조건의 말을 다시 말하면 'first[i]와 second[i]의 일치 여부는 확인할 필요가 없다.'입니다.

전반적인 접근 아이디어는 다음과 같습니다.

 

반복문을 이용해서 각각의 값을 비교하여 일치하면 count 값을 증가시키는 방식으로 설계합니다.

모든 과정을 거쳐서 count 값을 가장 큰 값 외 되도록 하면 됩니다.

(정확한 작동 방식은 소스코드 참고하세요.)

 

그러나 이렇게 비교하는 방식으로 접근하면 second 값을 다른 값과 비교해야 하는 경우가 생깁니다.

저는 vector 클래스를 이용하여 해결하였습니다.

 

vector 클래스를 사용하면 '배열 이름. size()'는 배열의 크기를 리턴합니다.

vector 클래스의 사용법은 아래 링크를 이용해 주세요.

[C++] vector container 정리 및 사용법

for 문을 2개 사용하여 비교 구문과 count를 통해 최댓값을 찾으면 됩니다.

 

 

 

3. 조건에 맞추어 클래스를 작성

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
class InterestingParty {
public:
    vector <string> first;
    vector <string> second;
    int bestInvitation(vector <string> first, vector<string> second);
};
int InterestingParty::bestInvitation(vector <string> first, vector<string> second) {
    int max=0;
    int count = 0;
    for (int i = 0; i < first.size(); i++) {
        for (int j = i + 1; j < first.size(); j++) {
            if (first[i] == first[j] || first[i] == second[j])
                count++;
        }
        if (max < count)
            max = count;
        count = 0;
    }
    for (int i = 0; i < second.size(); i++) {
        for (int j = i + 1; j < first.size(); j++) {
            if (second[i] == second[j] || second[i] == first[j])
                count++;
        }
        if (max < count)
            max = count;
    }
    return max;
}

 

아래 링크를 통해 지금까지 가장 정확한 코드와 자신이 작성한 코드를 비교하며

어떤 부분이 다른지 공부하시면 좋을 듯합니다.

C++ 말고 다른 언어도 있으니 참고하시길 바랍니다. 영어 해석은 오역이 많으므로 댓글로 피드백 부탁드립니다.

 

 

https://community.topcoder.com/stat?c=problem_solution&cr=22878522&rd=14423&pm=11312

불러오는 중입니다...