경우없는 개발 블로그

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

#문제 해결 방법

친절하게도 가장자리에는 치즈가 놓이지 않는다고 했으니

외곽부터 외부공기를 탐색하고 난 후 남은 공기는

내부 공기로 취급하면 된다.

나는 외부 공기를 그냥 bool 배열을 사용해서 따로 표시했다.

기존의 맵이랑 같이 표시하는 방법이 더 효율이 좋을 듯 한데 

그냥 더 직관적인 방법을 사용했다.

1.외부공기를 확인한 후에

2. 외부공기 2개가 맞닿은 치즈 확인 -> 지우기

        findOx(0, 0);
        cheeseCheck();

를 반복하고 

치즈가 0이 될때 까지 반복된 순서를 출력 하면 된다.

#전체 코드

#include <iostream>
#include <vector>
using namespace std;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int cheeseCount;
int n, m;
vector<vector<int>> world;
vector<vector<bool>> check;

bool boundary(int x, int y) {
    if (0 <= x && x < n && 0 <= y && y < m) return true;

    return false;
}

void findOx(int x, int y) {

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (boundary(nx, ny)) {
            if (world[nx][ny] == 0 && check[nx][ny] == false) {
                check[nx][ny] = true;
                findOx(nx, ny);
            }
        }

    }

}
void cheeseCheck() {
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < m; b++) {
            if (world[a][b] == 1) {
                int oxCount = 0;
                for (int i = 0; i < 4; i++) {
                    int nx = a + dx[i];
                    int ny = b + dy[i];
                    if (boundary(nx, ny)) {
                        if (check[nx][ny] == true) {
                            oxCount++;
                        }
                    }

                }
                if (oxCount >= 2) {
                    world[a][b] = 0;
                    cheeseCount--;
                }
            }
        }
    }
}






int main() {
    //1. 일단 공기를 돌면서 치즈에 갖혀있는지 아닌지 판별한다
    // ->가장자리 공기를 탐색하고 외부 탐색이 안 되었다면 내부 공기
    //2.치즈를 녹이고 시간을 보낸후 치즈가 0개라면 시간 출력



    cin >> n >> m;
    world.resize(n, vector<int>(m, 0));


    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> world[i][j];
            if (world[i][j] == 1) cheeseCount++;
        }
    }

    int phase = 0;
    while (cheeseCount > 0) {
        check.assign(n, vector<bool>(m, false));
        //외부 공기 확인
        check[0][0] = true;
        findOx(0, 0);
        //접촉 치즈 확인
        cheeseCheck();

        phase++;
    }

    cout << phase << '\n';

    return 0;
}

https://school.programmers.co.kr/learn/courses/30/lessons/81303

#문제 간단 정리

각 삭제된 상태를 기록하고 인덱스 조회하는 문제

#문제 해결 방법

가장 쉽게 생각할만 한 것은

삭제됫는지 안 삭제됫는지 표기하기 위해서

배열로 표시하는 것이다.

이전에 삭제된 항목은 스택에 기록해두는것.

그런데 이렇게 풀게되면 삭제된 항목을 넘어서 그 다음항목을 검색해야 되기 때문에

효율성 테스트에서 실패가 뜨게 된다.

때문에 삭제된 항목을 건너 뛸 수 있게

다른 자료구조를 사용해야 되는데

연결 리스트를 사용하면 된다.

나는 배열로 풀엇다가 

틀려서 연결리스트로 제출했다

#전체 코드

배열 코드 (실패)

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

 
vector<int> stack;
vector<bool> check;

string solution(int n, int k, vector<string> cmd) {

    check.assign(n, false);
    
    int cur = k;
    
    for(string s : cmd){
        
        char input1 = s[0];
        int input2 = 0;
        if(input1 == 'U' || input1 == 'D')  input2 = stoi(s.substr(2));

        
        if(input1 == 'U'){
            int count = 0;
            while(count != input2){
                if(check[--cur] == false){
                    count++;
                }
            }
        }
        else if(input1 == 'D'){
            int count = 0;
            while(count != input2){
                if(check[++cur] == false){
                    count++;
                }
            }
        }
        else if(input1 == 'C'){
            check[cur] = true;
            stack.push_back(cur);
            
            int temp = cur;
            bool found = false;
            while(temp < n - 1){
                temp++;
                if(!check[temp]){
                    cur = temp;
                    found = true;
                    break;
                }
            }
            if(!found){
                temp = cur;
                while(temp >= 0){
                    temp--;
                    if(!check[temp]){
                        cur = temp;
                        break;
                    }
                }
            }
        }if(input1 == 'Z'){
            check[stack.back()] = false;
            stack.pop_back();
        }
        
    }
    
    
    string answer(n, 'O');
    for (int i = 0; i < n; ++i) {
        if (check[i]) {
            answer[i] = 'X';
        }
    }

    return answer;
}

연결리스트 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    vector<int> prev(n), next(n);
    stack<int> removed;
    
    // 초기 링크드 리스트 설정
    for (int i = 0; i < n; ++i) {
        prev[i] = i - 1;
        next[i] = i + 1;
    }
    next[n - 1] = -1;

    int cur = k;
    
    for (const string& s : cmd) {
        char command = s[0];
        int value = 0;
        if (s.size() > 1) value = stoi(s.substr(2));
        
        if (command == 'U') {
            while (value--) {
                cur = prev[cur];
            }
        } else if (command == 'D') {
            while (value--) {
                cur = next[cur];
            }
        } else if (command == 'C') {
            removed.push(cur);
            if (prev[cur] != -1) next[prev[cur]] = next[cur];
            if (next[cur] != -1) prev[next[cur]] = prev[cur];
            
            cur = (next[cur] != -1) ? next[cur] : prev[cur];
        } else if (command == 'Z') {
            int restore = removed.top();
            removed.pop();
            if (prev[restore] != -1) next[prev[restore]] = restore;
            if (next[restore] != -1) prev[next[restore]] = restore;
        }
    }
    
    string answer(n, 'O');
    while (!removed.empty()) {
        answer[removed.top()] = 'X';
        removed.pop();
    }
    
    return answer;
}

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

#문제 간단 정리

   //만약 가장 낮은 위치에 있는 유성과
   //그 열에 가장 낮은 위치의 유성 - 가장 높은 위치에 있는 땅
   //그 값들의 최소값 만큼 내려 올 수 있다.

#문제 해결 방법

전반적으로 구현 문제기 때문에 위와 같이 해결 할 수 있는데

반례를 잘 찾아야 될 것 같다.

일단 주어진 테스트케이스에서는 무조건 땅이 존재 하는것 같다.

그래서 땅이 없는 경우에는 테스트케이스가 존재  하지 않는 것 같고

땅이 있는부분과 없는 부분이 나눠진 테스트케이스가 존재하는 것 같은데

이 경우에는 땅이 있는 곳의 유성과의 차이만큼 내려주도록 구현을 해야 된다.

만약 전부 땅이 없는 경우에는 내 코드는 오류가나는데

이는 상정 안된 부분인듯하지만 딱히 명시는 안되있다.

#전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#include <climits>

using namespace std;

int main() {
    
    int r, s;
    cin >> r >> s;

    //만약 가장 낮은 위치에 있는 유성과
    //그 열에 가장 낮은 위치의 유성 - 가장 높은 위치에 있는 땅
    //그 값들의 최소값 만큼 내려 올 수 있다.
    
    vector<vector<char>> board(r,vector<char>(s));
    for (int i = 0; i < r; i++) {
        string input;
        cin >> input;

        //board 에 입력
        for (int j = 0; j < s; j++) {
            board[i][j] = input[j];
        }
    }

    int minDiff = INT_MAX;

    //열을 순회하면서 가장 작은 차이를 고른다
    for (int i = 0; i < s; i++) {
        int maxMeteor = -1;
        int maxGround = INT_MAX;
        for (int j = 0; j < r; j++) {
            if (board[j][i] == 'X') {
                maxMeteor = j;
            }
            if (board[j][i] == '#' && maxGround == INT_MAX) {
                maxGround = j;
            }
        }
        // 유성이 있고, 그 아래에 땅이 있는 경우만 계산
        if (maxMeteor != -1 && maxGround != INT_MAX) {
            minDiff = min(maxGround - maxMeteor , minDiff);
        }
    }


    //minDiff 만큼 유성을 아래로 내린다.
    //아래부터 탐색해서 중복을 없앤다
    for (int i = r - 1; i >= 0; i--) {
        for (int j = 0; j < s; j++) {
            if (board[i][j] == 'X') {
                board[i][j] = '.';
                board[i + minDiff-1][j] = 'X';
            }
        }
    }


    //복원 후 출력
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) {
            cout << board[i][j];
        }
        cout << '\n';
    }

    return 0;
}

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

#문제 해결 방법

우선 문제를 살펴 봤을 때

소수를 에라토스테네스의 체로 구한다는 생각은 쉽게 할 수 있다.

그리고 거의 소수를 (소수의 n제곱) 을 구하는건

딱히 추가적으로 빠른 방법이 없다 생각이 되어서

브루트 포스로 풀어야 겠다는 생각이 먼저 든다.

그래서 에라토스테네스로

루트 b 까지의 소수를 구하는데

이유는

거의 소수는 소수의 n 제곱이라

루트 b 이상의 소수는 필요 없기 때문이다

    ll limit = sqrt(b) + 1;
    vector<bool> is_prime(limit + 1, true);
    vector<ll> primes;

그리고 구한 소수들을 계속 제곱해 가면서 b를 넘지 않고

a 보다 크다면 거의소수를 찾은 것이다.

    int count = 0;
    for (ll i : primes) {
        ll temp = i*i;

        while (temp <= b) {
            if (temp >= a) {
                count++;
            }
            if (temp > b /i) break; // 오버플로우 방지
            temp *= i;
        }

    }

여기서 주의 할 것은 오버플로우 방지를 하지 않는다면 

틀리니까 오버플로우 방지를 주의하자 

#전체 코드

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

typedef long long ll;

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

    ll a, b;
    cin >> a >> b;


    ll limit = sqrt(b) + 1;
    vector<bool> is_prime(limit + 1, true);
    vector<ll> primes;

    // 에라토스테네스의 체로 sqrt(b)까지의 소수를 구함
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int count = 0;
    for (ll i : primes) {
        ll temp = i*i;

        while (temp <= b) {
            if (temp >= a) {
                count++;
            }
            if (temp > b /i) break; // 오버플로우 방지
            temp *= i;
        }

    }

    cout << count << '\n';

    return 0;
}

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

#해결 방법

일단 그냥 구현 그자체인데

소수점 처리에서 아주 귀찮다.

입력값의 소수점을 지우기 위해서 

            long long combo_bonus = 100 + combo * C;
            long long skill_bonus = 100 + skill[idx] * s[idx];

각각 100을 곱해준 상태로 처리하고

10'000을 나눠주고

소수점 내림을해서 처리하도록하자

즉 소수가 나올거같을때는 곱해서 소수점을 없애고 나중에 나눠서 

오차를 줄이도록하자

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int N, K, C, R;
    cin >> N >> K >> C >> R;

    vector<int> base(K);
    vector<int> s(K);
    vector<int> p(K);

    for (int i = 0; i < K; i++) {
        cin >> base[i];
    }
    for (int i = 0; i < K; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < K; i++) {
        cin >> p[i];
    }

    vector<int> skill(K, 0);
    int combo = 0;
    int stress = 0;
    long long total_stardust = 0;  

    for (int i = 0; i < N; i++) {
        int act;
        cin >> act;

        if (act == 0) {
            stress -= R;
            if (stress < 0) stress = 0;
            combo = 0;
        }
        else {
            int idx = act - 1;
            stress += p[idx];
            if (stress > 100) {
                cout << -1 << '\n';
                return 0;
            }
            long long combo_bonus = 100 + combo * C;
            long long skill_bonus = 100 + skill[idx] * s[idx];
            long long delta_stardust = floor((base[idx] * combo_bonus * skill_bonus) / 10000.0);
            total_stardust += delta_stardust;
            combo++;
            skill[idx]++;
        }
    }

    cout << total_stardust << '\n';

    return 0;
}

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

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int alpha[26];

int main() {
    string s;
    cin >> s;
    int odd = 0;
    char oddChar;

    // 알파벳 개수 세기
    for (char c : s) {
        alpha[c - 'A']++;
    }

    // 홀수 개수 세기
    for (int i = 0; i < 26; i++) {
        if (alpha[i] % 2 != 0) {
            odd++;
            oddChar = i + 'A';
        }
    }

    // 홀수 개수가 1개 이상일 경우 팰린드롬을 만들 수 없음
    if (odd > 1) {
        cout << "I'm Sorry Hansoo" << endl;
        return 0;
    }

    string firstHalf = "";
    string secondHalf = "";

    // 팰린드롬의 첫 번째 절반 생성
    for (int i = 0; i < 26; i++) {
        firstHalf += string(alpha[i] / 2, i + 'A');
    }

    secondHalf = firstHalf;
    reverse(secondHalf.begin(), secondHalf.end());

    // 팰린드롬 만들기
    if (odd == 1) {
        firstHalf += oddChar;
    }

    cout << firstHalf + secondHalf << endl;

    return 0;
}

#문제 해결 방법

우선, 이름의 배열 크기가 8이기 때문에 

각자 이름끼리 맞는지 확인까지 해도

완전탐색으로 풀 수 있다는 걸 쉽게 알 수 있다.

때문에 설계를 하자면

1. 이름끼리 비교하는 함수를 만든다

2. 이걸 전체 순회하는 dfs 함수를 만든다

라는 설계가 가능하다 

우선 이름이 맞는지 확인하는 함수는 

bool nameCmp(string user, string banned){
    
    if(user.length() != banned.length()){
        return false;
    }else{
        for(int i=0; i<user.length(); ++i){
            if(banned[i] != '*' && user[i] != banned[i]){
                return false;
            }
        }
    }
    
    return true;
}

로 쉽게 만들 수가 있다.

길이가 다르거나

*이 아닌다 문자가 다른경우에 false 를 리턴한다

이제 dfs 함수를 만들어야 되는데 이부분이 조금 고민이 된다

여기서 탐색 포커싱을

banned_id에 맞춰야 된다

각 banned_id에 매칭되는 id를 찾았다면 다음 banned id 로 넘어가면 된다

그리고 여기서 까다로운 부분이 하나 더 있는데.

각각의 정답으로 고른 정답에서 

중복되는 답이 있을 수 있기 때문이다.

같은 아이디가 순서만 다른 정답이 있을 수 있다.

이 부분은 set을 사용해서 해결할 수 있는데

다른 분들 같은경우에는 set에서 find 해서 없는경우에만 insert 하도록 하는 경우가 일반적인 것 같다.

나는 set<set<string>> result  // 이중 셋을 사용해서 중복을 제거했다.

이중 셋을 사용하면 중복을 편하게 제거할수 있으니 유용한 팁이라고 할 수 있다.

#전체 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

//dfs 로 모든 조합을 살펴보고
//이름을 비교하는 함수도 만들어야함


bool nameCmp(string user, string banned){
    
    if(user.length() != banned.length()){
        return false;
    }else{
        for(int i=0; i<user.length(); ++i){
            if(banned[i] != '*' && user[i] != banned[i]){
                return false;
            }
        }
    }
    
    return true;
}

void dfs(vector<string>& user_id, vector<string>& banned_id, vector<bool>& visited, set<set<string>>& result, set<string>& currentSet, int index) {
    if (index == banned_id.size()) {
        result.insert(currentSet);
        return;
    }
    for (int i = 0; i < user_id.size(); ++i) {
        if (!visited[i] && nameCmp(user_id[i], banned_id[index])) {
            visited[i] = true;
            currentSet.insert(user_id[i]);
            dfs(user_id, banned_id, visited, result, currentSet, index + 1);
            currentSet.erase(user_id[i]);
            visited[i] = false;
        }
    }
}


int solution(vector<string> user_id, vector<string> banned_id) {
    
    set<set<string>> result;
    set<string> currentSet;
    vector<bool> visited(user_id.size(), false);
    
     dfs(user_id, banned_id, visited, result, currentSet, 0);

    return result.size();
}

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

#문제 해결 방법

2를 곱해서 같은수가 된다는거는

2로 계속해서 나눳을때

같은 값이 된다는 소리니..

2로 계속 나눠서 같은 값인지 확인해서 개수를 세어주면 된다

#전체 코드

#include <iostream>
#include <string>
#include <algorithm> 
#include <map>


typedef long long ll;

using namespace std;

int divide(int factor) {
    if (factor % 2 == 1) {
        return factor;
    }
    else {
        return divide(factor / 2);
    }
}

int main() {
    
    int n;
    cin >> n;
    map<int, int> map;
    int freq = 0;
    while (n--) {
        int input;
        cin >> input;
        

        int odd = divide(input);

        if (map.find(odd) == map.end()) {
            map[odd] = 1;
        }
        else {
            map[odd]++;
        }

        freq = max(freq, map[odd]);

    }

    cout << freq<<'\n';

    return 0;
}

#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

long long calculate(long long a, long long b, char op) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    return 0;
}

long long evaluate_expression(vector<long long> numbers, vector<char> operators, vector<char> precedence) {
    for (char op : precedence) {
        for (int i = 0; i < operators.size(); ++i) {
            if (operators[i] == op) {
                numbers[i] = calculate(numbers[i], numbers[i + 1], op);
                numbers.erase(numbers.begin() + i + 1);
                operators.erase(operators.begin() + i);
                --i;
            }
        }
    }
    return numbers[0];
}

long long solution(string expression) {
    vector<long long> numbers;
    vector<char> operators;
    string num = "";
    
    for (char c : expression) {
        if (isdigit(c)) {
            num += c;
        } else {
            numbers.push_back(stoll(num));
            num = "";
            operators.push_back(c);
        }
    }
    numbers.push_back(stoll(num));

    vector<vector<char>> precedence_permutations = {
        {'+', '-', '*'}, {'+', '*', '-'},
        {'-', '+', '*'}, {'-', '*', '+'},
        {'*', '+', '-'}, {'*', '-', '+'}
    };

    long long max_value = 0;
    for (auto precedence : precedence_permutations) {
        long long result = evaluate_expression(numbers, operators, precedence);
        if (result < 0) result = -result;
        if (result > max_value) max_value = result;
    }

    return max_value;
}

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

#문제 간단 정리

투 포인터 /슬라이딩 윈도우 문제

계속해서 조약돌을 줍다가 검은 조약돌이 초과하게 되면

슬라이딩 윈도우를 줄여주면 된다.

#문제 해결 방법

슬라이딩 윈도우를 사용한다고 생각하고

우선 기본적으로 ㅣ , r 두가지의 포인터를 설정하고

오른쪽으로 계속 조약돌을 r++ 하면서 주워주되

    while (r < n) {
        bw[color_map[s[r]]]++;
        r++;

 
        while (bw[0] > b ) {
            bw[color_map[s[l]]]--;
            l++;
        }

        if (bw[0] <= b && bw[1] >= w) {
            maxlength = max(maxlength, r - l);
        }
    }

만약 검은 조약돌의 개수가 원하는 개수보다 늘어나개 된다면

검은 조약돌이 원하는 개수 이하가 되도록 왼쪽포인터를 l++ 해서

        while (bw[0] > b ) {
            bw[color_map[s[l]]]--;
            l++;
        }

윈도우 사이즈를 줄여주도록 하자

#전체 코드

#include <iostream>
#include <string>
#include <algorithm> 
#include <map>

using namespace std;


int main() {
    int n;
    cin >> n;

    int b, w;
    cin >> b >> w;


    string s;
    cin >> s;


    int bw[2] = { 0,0 }; //0은 검정 1은 흰색
    map<char, int>color_map;
    color_map['W'] = 1;
    color_map['B'] = 0;
    int l = 0, r = 0;
    int maxlength = 0;

    while (r < n) {
        bw[color_map[s[r]]]++;
        r++;

 
        while (bw[0] > b ) {
            bw[color_map[s[l]]]--;
            l++;
        }

        if (bw[0] <= b && bw[1] >= w) {
            maxlength = max(maxlength, r - l);
        }
    }

    cout << maxlength << '\n';
    

    return 0;
}