[Topcoder] SRM348 ~ 360 연습

SRM348 DIV2

class OptimalList
{
public:

    string optimize(string str)
    {   
        int n = 0, s= 0, e= 0, w= 0;
        REP(i, str.size())
        {
            if(str[i] == 'N') n++;
            if(str[i] == 'S') s++;
            if(str[i] == 'E') e++;
            if(str[i] == 'W') w++;
        }

        string ret;
        if(e - w > 0) ret += string(e-w, 'E');
        else ret += string(w-e, 'W');
        if(n-s > 0) ret += string(n-s, 'N');
        else ret += string(s-n, 'S');

        sort(ALL(ret));
        return ret;
    }
};

SRM349 DIV2

class DocumentSearch
{
public:

    int nonIntersecting(vector <string> d, string s)
    {   
        string s1;
        REP(i, d.size()) s1 += d[i];

        int n = s.size();
        int ret = 0;
        REP(i, s1.size())
        {
            string s2 = s1.substr(i, n);
            if( s2 == s)
            {
                ret++;
                i += (n-1);
            }
        }

        return ret;
    }
};

SRM350 DIV2
: 대소문자를 같이 취급한다는 문구를 못봤음. 문제를 잘 볼 것.

class DistanceBetweenStrings
{
public:

    int getDistance(string a, string b, string l)
    {   
        int ret = 0;
        REP(i, l.size())
        {
            int a_c = count(ALL(a), l[i]) + count(ALL(a), toupper(l[i]));
            int b_c = count(ALL(b), l[i]) + count(ALL(b), toupper(l[i]));
            ret += (a_c - b_c) * (a_c - b_c);           
        }
        return ret;
    }
};

SRM351 DIV2

class RoomNumber
{
public:

    string toStr(int num)
    {
        stringstream s;
        s << num;
        return s.str();
    }

    int numberOfSets(int r)
    {           
        VI d;
        string s = toStr(r);
        for(char i= '0'; i<='9'; i++)
        {
            if( i != '6' && i != '9')
                d.pb(count(ALL(s), i));
            else
                d.pb( (count(ALL(s),'6')+count(ALL(s),'9')+1)/2 );
        }
        sort(d.rbegin(), d.rend());
        return d[0];
    }
};

SRM352 DIV2
: if(a/b < 0.75) 로 if문을 짜기보다는 if(4a < 3b) 로 짜는 습관을 들이자.

class AttendanceShort
{
public:

    vector <string> shortList(vector <string> name, vector <string> a)
    {           
        vector<string> ret;
        REP(i, name.size())
        {
            string s = a[i];
            double tot = count(ALL(s), 'P') + count(ALL(s), 'A');
            if( count(ALL(s), 'P')/tot < 0.75)
                ret.pb(name[i]);
        }
        return ret;
    }
};

SRM353 DIV2
: red들은 하나같이 거리 d에서 1e-9를 뺀 수로 비교를 했다. float연산으로 반올림 될 경우를 고려해 준 듯함.

class EllipseCoverage
{
public:

    int calculateCoverage(int x1, int y1, int x2, int y2, int d)
    {       
        int x = d - abs(x1-x2);
        int y = d - abs(y1-y2);
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);

        int ret = 0;
        for(int i=x1-x; i<= x2+x; i++)
        {
            for(int j=y1-y; j<= y2+y; j++)
            {
                if( d > (sqrt(1.0*(i-x1)*(i-x1) + 1.0*(j-y1)*(j-y1)) + sqrt(1.0*(i-x2)*(i-x2) + 1.0*(j-y2)*(j-y2))))
                    ret++;
            }
        }

        return ret;
    }
};

SRM354 DIV2

class Thimbles
{
public:

    int thimbleWithBall(vector <string> s)
    {       
        int ret = 1;
        REP(i, s.size())
        {
            int a = s[i][0]-'0';
            int b = s[i][2]-'0';
            if( ret == a) ret = b;
            else if(ret == b) ret = a;
        }
        return ret;
    }
};

SRM355 DIV2

class ValueAddedTax
{
public:

    double calculateFinalPrice(string p, int price, vector <string> f)
    {       
        double ret = 0;
        if( find(ALL(f), p) != f.end())
            ret = price + price * 0.1;       
        else
            ret = price + price * 0.18;       

        return ret;
    }
};

SRM356 DIV2
:string.find는 size_t형식의 int값을 반환하고, algorithm의 find는 iterator를 반환한다.
저걸 헷갈려서 좀 삽질했음. string.replace용법도 익혀두자. 나중에 다시 풀어볼 것.

class SMSLanguage
{
public:

    string translate(string t)
    {               
        string s;
        REP(i, t.size())
            if(t[i] != '.' && t[i] != ',' && t[i] != '?' && t[i] != '!') s += t[i];

        REP(i, s.size()) s[i] = tolower(s[i]);

        while(s.find("and") != string::npos || s.find("ate") != string::npos || s.find("at") != string::npos
            ||  s.find("you") != string::npos)
        {
            if( s.find("and") != string::npos )
            {
                s.insert(s.find("and"), "&");
                s.erase(s.find("and"), 3);
            }
            else if( s.find("ate") != string::npos )
            {
                s.insert(s.find("ate"), "8");
                s.erase(s.find("ate"), 3);
            }
            else if( s.find("at") != string::npos )
            {
                s.insert(s.find("at"), "@");
                s.erase(s.find("at"), 2);
            }
            else if( s.find("you") != string::npos )
            {
                s.insert(s.find("you"), "U");
                s.erase(s.find("you"), 3);
            }
        }

        return s;
    }
};

다시 짜본 소스
class SMSLanguage
{
public:

    string translate(string t)
    {   
        string s;
        REP(i, t.size())
            if( t[i] != '.' && t[i] != ',' && t[i] != '?' && t[i] != '!')
                s += t[i];
        REP(i, s.size()) s[i] = tolower(s[i]);

        int p = 0;
        while( s.find("and") != string::npos)
            s.replace(s.find("and"), 3, "&");

        while( s.find("ate") != string::npos)
            s.replace(s.find("ate"), 3, "8");

        while( s.find("at") != string::npos)
            s.replace(s.find("at"), 2, "@");

        while( s.find("you") != string::npos)
            s.replace(s.find("you"), 3, "U");

        return s;
    }
};

SRM357 DIV2

class MnemonicMemory
{
public:

    string getPhrase(string num, vector <string> d)
    {   
        sort(ALL(d));
        string ret;
        REP(i, num.size())
        {
            int c = num[i]-'0';
            REP(j, d.size())
            {
                if(d[j].size() == c)
                {
                    ret += d[j] + " ";
                    d[j] = "";
                    break;
                }
            }
        }
        ret.erase(ret.size()-1, 1);
        return ret;
    }
};

SRM358 DIV2

class CyclicWords
{
public:

    int differentCW(vector <string> w)
    {   
        vector<string> d;

        REP(i, w.size())
        {
            string s = w[i];
            int isok = 1;
            REP(j, s.size())
            {
                string temp = s.substr(j)+ s.substr(0, j);
                if( find(ALL(d), temp) != d.end() )
                {
                    isok = 0;
                    break;
                }
            }
            if(isok == 1) d.pb(s);
        }

        return d.size();
    }
};

SRM359 DIV2
: 1은 0으로 0은 1으로 변경을 (pos+1)%2 로 써봤는데, 그것보다 1-pos가 더 간결하다..
또는 !pos 로 쓰는 방법도 있음.


class CricketScores
{
public:

    vector <int> totalRuns(vector <int> r)
    {   
        VI ret(2,0);
        int pos = 0;
        REP(i, r.size())
        {
            ret[pos] += r[i];
            if((i+1)%6 == 0)
            {
                if(r[i] % 2 == 0)
                    pos = (pos+1)%2;
            }
            else if( r[i] % 2 == 1)
            {
                pos = (pos+1)%2;
            }
        }

        return ret;
    }
};

SRM360 DIV2
: 예제가 없었으면 오류가 날 뻔 했음. ( %로 나머지를 구해도 음수가 발생할 수 있다)

class AzimuthMonitoring
{
public:

    int getAzimuth(vector <string> ins)
    {   
        int ret = 0;

        REP(i, ins.size())
        {
            string s = ins[i];
            string t1;
            int r;
            if( s == "HALT") break;
            if( s == "LEFT") ret -= 90;
            if( s == "RIGHT") ret += 90;
            if( s == "TURN AROUND") ret += 180;
            if( s.size() > 4 && s.substr(0, 4) == "LEFT")
            {
                istringstream in(s);
                in >> t1 >> r;
                ret -= r;
            }
            if( s.size() > 5 && s.substr(0, 5) == "RIGHT")
            {
                istringstream in(s);
                in >> t1 >> r;
                ret += r;
            }
        }

        ret %= 360;
        if(ret < 0) ret+= 360;

        return ret;
    }
};