라비린스6_개발 블로그

백준 13022번 - 늑대와 올바른 단어(실버 2)

https://www.acmicpc.net/problem/13022

풀이

입력된 문자열이 규칙 1, 2를 충족시키는지 검사해야 한다.

규칙1: w, o, l, f 가 n 번 나온 단어는 올바른 단어(순서는 w, o, l, f 로 나와야함)

규칙2: 올바른 단어 2개를 이은 단어도 올바른 단어

규칙 1 을 만족시킬수 있는 단어는 wolf, wwoollff.. 등이 있다.

우선 문자가 반복된 횟수를 구한다. (wcnt 에 저장)

문자가 바뀐 지점 인덱스 +1 을 저장해서 구했다.

    for (int i = 0; i < str.size(); i++)
    {
        // 문자가 변한 구간
        if (i>=1 && str[i]!= str[i-1])
        {
            wcnt = i;
            break;
        }
    }

이제 각 문자별로 등장횟수를 카운트한다.

저는 'f' 를 기준으로 f다음에 f를 제외한 다른 문자가 나오면

각 문자별 등장 횟수가 wcnt 와 일치 하는지 검사했습니다.

여기서 1번 조건을 충족시키려면 현재까지 구간의 문자열은

w x (wcnt 횟수 반복) + o x (wcnt 횟수 반복)  +  l x (wcnt 횟수 반복)  + f x (wcnt 횟수 반복) 입니다.

만약 현재 구간까지 문자열이 1번 조건을 충족시킨다면, 다음 구간도 검사해야겠죠.

남은 구간만 다시 문자열을 동일하게 검사하면 됩니다.

저는 replace 로 현재검사한 구간을 제거하고

아직 문자가 남아있다면 재귀시켜서 다시 검사했습니다.

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

bool isWolf(string str)
{
    int wcnt = 0;

    // 각각 문자열 카운트
    int w = 0;
    int o = 0;
    int l = 0;
    int f = 0;

    for (int i = 0; i < str.size(); i++)
    {
        // 문자가 변한 구간
        if (i>=1 && str[i]!= str[i-1])
        {
            wcnt = i;
            break;
        }
    }

    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'w')
        {
            w++;
        }
        if (str[i] == 'o')
        {
            o++;
        }
        if (str[i] == 'l')
        {
            l++;
        }
        if (str[i] == 'f')
        {
            f++;

            // f 연속 끝나면 발동
            // 문자열 인덱스에러 방지
            if (i == str.size() - 1 || (i < str.size() - 1 && str[i] != str[i + 1]))
            {
                // 모든 글자의 수가 같으면 
                if (wcnt == w && wcnt == o && wcnt == l && wcnt == f)
                {
                    string wolfstr = "wolf";
                    string findstr = "";

                    for (int j = 0; j < wolfstr.size(); j++)
                    {
                        for (int k = 0; k < wcnt; k++)
                        {
                            findstr += wolfstr[j];
                        }
                    }

                    // findstr 이 있는지 확인
                    int pos = str.find(findstr);
                    // 없으면 리턴시킴
                    if (pos== string::npos)
                    {
                        return false;
                    }
                    // 문자 제거
                    str = str.replace(str.find(findstr), findstr.length(), "");

                    if (str.size() == 0)
                    {
                        return true;
                    }
                    else
                    {
                        // 다시 문자 검사
                        return isWolf(str);
                    }
                }
                else
                {
                    return false;
                }
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int result = 0;

    string str;
    cin >> str;

    cout << isWolf(str);
    return 0;
}

골드 달성이긴 한데 정작 골드 문제는 못풀겠네요...

티어 자체보단 문제푸는 능력 키우는게 중요한것 같습니다.

단계별로 풀어보기로 순서대로 풀다가 심심하면 키워드 아무거나 검색하거나 solved.ac 클래스에 있는 문제중 난이도 낮은 걸로 풀어봤습니다

단계별로 풀어보기도 재귀 부터는 너무 어렵네요

그리디는 직관적이여서 이해하기 괜찮았고

dp는 저의 머리로는 정말로 이해가 안되었습니다. 브론즈문제도 참고 안하면 못풀겠더라고요

점화식 세우는것부터 어렵고 그리고 dp 테이블에 어떤식으로 값을 채우도록 설계할지 생각하는 것도 어렵습니다

아무튼 일단 쉬운것부터 풀면서 dp 테이블 설계하는데 익숙해져야 할 것 같습니다

사실 대학생때 재미로 hello world 나 사칙연산 풀어본거 외에는 작년~ 올해에 c++ 익숙해지려고 많이 풀었는데

실력 향상에 많이 도움이 된 것 같습니다

c# 은 요즘 안써서 까먹으려 하는데,  간단한 문제 위주로 몇개 풀어볼까 합니다

빠른 처리에 별로 용이하지 않아서 그런지 원래 우리나라에선 마이너라 그런지 백준에선 쓰는사람이 별로없네요...

일단 실버단계 dp 문제풀이에 익숙해지고  그 다음으로는 티어나 난이도 높은 문제보단 아직 풀어보지 않은 다양한 문제를 풀어보려 합니다

c#은 일단 브론즈 문제 몇개 풀어보고 괜찮으면 좀 더 해봐야겠습니다

https://www.acmicpc.net/problem/2108

백준 2108번 - 통계학(실버 3)

풀이

다른건 크게 어려울 것이 없는데 최빈값을 어떻게 처리할지 잘 생각해야 한다

unordered_map 에 <입력받은수, 등장횟수> 로 저장해서 최빈값을 찾는 식으로 구현했다.

그리고 밑에 조건에 평균에 -0 이 나오면 안된다고 되어 있다. 이 부분도 고려해서 출력해야 한다.

전체코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <unordered_map>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> num(n,-4001);
    vector<int> numcnt(n);

    // 등장횟수
    unordered_map<int, int> mapcnt;


    int intsum = 0;
    int intmin = 4000;
    int intmax = -4000;
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        // 숫자 저장
        // 위의 인덱스별로 나온 개수 저장
        mapcnt[k]++;

        num[i] = k;
        intsum+= num[i];
        if (intmin > num[i])
        {
            intmin = num[i];
        }
        if (intmax < num[i])
        {
            intmax = num[i];
        }
       
    }

    // n은 홀수
    int midindex = (n +1) / 2;

    vector<int> sortnum(n);
    sortnum  = num;
    sort(sortnum.begin(), sortnum.end());

    // 최빈값 구하기
    // 카운트 중에 최대 구하기
    vector<int> sortcnt(n);
    sortcnt = numcnt;
    sort(sortcnt.begin(), sortcnt.end(), greater<int>());
    int maxcntidx = sortcnt[0];
    // 최대 등장 횟수
    int freqnum = 0;
    // 최빈 값
    int intmostfreq;

    vector<int> freqno;
    for (auto it:mapcnt)
    {
        // num , 등장횟수
        if (freqnum < it.second)
        {
            freqnum = it.second;
        }
    }
   

    for (auto it : mapcnt)
    {
        if (freqnum == it.second)
        {
            freqno.push_back(it.first);
        }
    }

    if (freqno.size() > 1)
    {
        sort(freqno.begin(), freqno.end());
        intmostfreq = freqno[1];
    }
    else
    {
        intmostfreq = freqno[0];
    }

    // 평균
    if (round(static_cast<float>(intsum) / static_cast<float>(n)) == 0)
    {
        cout << 0 << "\n";
    }
    else
    {
        cout << round(static_cast<float>(intsum) / static_cast<float>(n)) << "\n";
    }

    // 중앙값
    cout << sortnum[midindex-1] << "\n";

    // 최빈값
    cout << intmostfreq << "\n";
    
    // 범위
    cout << intmax - intmin;
}

https://www.acmicpc.net/problem/4134

입력수 n에 대해 n보다 같거나 큰 가장큰 소수를 찾으면 된다. 

1. 소수 판별

int isprime(long long int num)
{
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;

    for (long long int i = 3; i <= sqrt(num); i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

2. 소수를 찾을 때 까지 반복

long long int findMinPrime(long long int n)
{
    while (!isprime(n))
    {
        n++;
    }
    return n;
}

입력값 n에 대해 소수인지 확인한 후 소수가 아닌 경우 n 증가 수행

소수를 찾을 때 까지 반복한다. 

입력의 개수는 안주어지고, 입력 값은 최대 크기가 커서

에라스토테네스의 체를 사용하기보단 각각의 케이스별로 소수판별을 해야 하는 같다.

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int isprime(long long int num)
{
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;

    for (long long int i = 3; i <= sqrt(num); i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

long long int findMinPrime(long long int n)
{
    while (!isprime(n))
    {
        n++;
    }
    return n;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
    {
        long long int n;
        cin >> n;

       cout << findMinPrime(n) <<"\n";
    }

}

나는야 포켓몬 마스터 이다솜 (실버 4)

https://www.acmicpc.net/problem/1620

 문제가 너무 길어서 링크에서 참조해주세요

입력받는 포켓몬 개수 N, 맞춰야하는 문제 M 이 주어집니다.

포켓몬은 1번부터 번호 순서대로 입력됩니다.

풀이

입력받고 {번호, 포켓몬이름} 의 구조체로 저장한 뒤, 

번호를 입력받으면 이름을, 이름을 입력받으면 번호를 찾아서 출력하면 되는 문제입니다.

논리적으로는 간단하지만, 제한 시간이 짧아서 

반복문을 통한 비교를 하면 바로 시간제한이 뜹니다.

map 등의 자료구조를 통한 탐색을 해야 합니다.

여기서 vector 또는 배열 사용 후 for 문으로 탐색 시 시간복잡도는 

O(n)

map 의 시간 복잡도는

O(logN)

unordered_map 의 시간복잡도는 

O(1) 

이 문제의 경우 정렬을 따로 쓰지 않으니, unordered_map을 사용하면 성능이 더 빨라집니다.

같은 코드로 map 과 unordered_map 사용을 비교해보니 백준 채점 기준

각각 200ms / 120ms 정도로 상당히 차이가 많이 나는것을 확인가능합니다.

map/ unordered_map  구조체의 경우 키 값을 string 으로도 설정할 수 있어서,

key 가 번호인 구조체랑 key 가 포켓몬 이름인 구조체 2개를 선언했습니다.

unordered_map<int, string> pkmon;
unordered_map<string, int> pkmonByName;

번호를 입력받은 경우  와   포켓몬 이름을 입력받은 경우 를 구분해서 처리해야 하는데,

포켓몬 이름은 알파벳으로 구성되었다고 언급되므로 입력은 string 으로 받은 후 isalpha()를 통해 첫번째 글자가 알파벳인지 확인했습니다.

        string str;
        cin >> str;

        // 이름을 받은경우
        if (isalpha(str[0]))
        {
            int num = findPocketMonNum(str);
            cout << num +1 << "\n";
        }

번호 = 인덱스 + 1 이므로 번호를 입력받은 경우 는 바로 출력하면 되고,

포켓몬 이름을 입력받은 경우 는 find() 함수를 통해 탐색해야합니다.

int findPocketMonNum(string pkname)
{
    if (pkmonByName.find(pkname)!= pkmonByName.end())
    {
        return pkmonByName[pkname];
    }
}

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
using namespace std;
using std::cin;

unordered_map<int, string> pkmon;
unordered_map<string, int> pkmonByName;

int findPocketMonNum(string pkname)
{
    if (pkmonByName.find(pkname)!= pkmonByName.end())
    {
        return pkmonByName[pkname];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int k;

    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        string name;
        cin >> name;

        pkmon.insert(make_pair(i, name));
        pkmonByName.insert(make_pair(name, i));
    }

    // 출력시작
    for (int i = 0; i < k; i++)
    {
        string str;
        cin >> str;

        // 이름을 받은경우
        if (isalpha(str[0]))
        {
            int num = findPocketMonNum(str);
            cout << num +1 << "\n";
        }
        // 번호를 받은 경우
        else
        {
            int intnum = stoi(str);
            cout << pkmon[intnum -1] << "\n";
        }
    }
}