99코딩

• 각 칸의 숫자는 해당 칸에서 최대 며칠 머물 수 있는지 나타냄
• 이어진 땅들은 하나의 무인도
• X는 갈 수 없음

> bfs를 이용한 풀이

#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> answer;

char board[101][101] = {'0'};
bool check[101][101] = {false};

int dx[4] = {1, 0 , -1, 0};
int dy[4] = {0, -1, 0 , 1};

void bfs(int posX, int posY, int width, int height) {
    queue<pair<int, int>> q;
    q.push({posX, posY});
    check[posX][posY] = true;
    
    int sum = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        sum += board[x][y] - '0';
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int curX = x + dx[i];
            int curY = y + dy[i];
            
            if(curX < 0 || curX >= width || curY < 0 || curY >= height || check[curX][curY] || board[curX][curY] == 'X') continue;
            
            check[curX][curY] = true;
            q.push({curX,curY});
        }
    }
    
    answer.push_back(sum);
}

vector<int> solution(vector<string> maps) {
    int width = maps.size();
    int height = maps[0].size();
    
    for(int i = 0; i < width; i++)
        for(int j = 0; j < height; j++)
            board[i][j] = maps[i][j];
    
    for(int i = 0; i < width; i++) {
        for(int j = 0; j < height; j++) {
            if(!check[i][j] && maps[i][j] != 'X')
                bfs(i, j , width, height);
        }
    }
    
    sort(answer.begin(), answer.end());
    
    if(answer.empty()) {
        answer.push_back(-1);
        return answer;
    }
    else
        return answer;
}

풀이방법

문자열 s의 각 알파벳에 index만큼 뒤에 있는 알파벳을 구하되 문자열 skip에 있는 알파벳은 카운트하지 않아야한다.

이를 구현하기 위해 문자열 s의 각 알파벳에 index번 만큼 1을 더하였을 때 해당 알파벳이 skip에 들어있는 알파벳일 경우 반복 횟수를 한 번씩 늘려주도록 했다. 또한 s와 skip은 알파벳 소문자로만 이루어져 있으므로 s[i]에 1을 더하였을 시 아스키 코드 값이 122를 초과한다면 a가 되도록 하였다.

1. 알파벳의 검사를 위해 int형 변수 cur을 선언

2. s[i]에 ++해준다.

3. s[i]가 z보다 커지면 a로 변환하고 find함수로 s[i]가 skip안에 있는지 찾고 있다면 반복 횟수를 늘려주고 없다면 계속해서 수행한다.

4. 이를 index번만큼 반복 후 변환된 문자열 s를 리턴

#include <string>
#include <vector>

using namespace std;

string solution(string s, string skip, int index) {
    int cur = 0;
    
    for(int i = 0; i < s.size(); i++) {
        for(int j = 0; j < index; j++) {
            s[i]++;
            if(s[i] > 'z') s[i] = 'a';
            
            cur = skip.find(s[i]);
            if(cur == -1)
                continue;
            else j--;
        }
    }
    
    return s;
}

풀이 방법

10진수인 n을 k진수 문자열로 변환하고 해당 문자열을 조건에 맞춰 파싱 후 소수의 개수를 리턴하면 된다.

1. n을 k진수 문자열로 변환하여 문자열 arithmetic에 담는다.

2. 문자열을 조건에 맞춰 파싱하여 tmp에 담고 숫자로 변환 후 소수인지 판별하고 소수면 answer++

3. 반복문이 끝난 후 tmp가 비어있지 않다면 한 번 더 소수인지 판별하고 소수면 answer++

4. answer 리턴

#include <string>
#include <vector>

using namespace std;

bool isPrime(long long n) {
    if(n < 2) return false;
    for(long long i=2; i*i<=n; i++)
        if(!(n % i)) return false;
    
    return true;
}

int solution(int n, int k) {
    int answer = 0;
    string arithmetic = "";
    string tmp = "";
    
    while(n) {
        arithmetic += to_string(n % k);
        n /= k;
    }
    
    arithmetic = string(arithmetic.rbegin(), arithmetic.rend());
    
    for(int i = 0; i < arithmetic.length(); i++) {
        if(arithmetic[i] == '0' && !tmp.empty()) {
            long long num = stoll(tmp);
            if(isPrime(num)) answer++;
            tmp = "";
        }
        else tmp += arithmetic[i];
    }
    
    if(!tmp.empty()) {
        long long  n = stoll(tmp);
        if(isPrime(n)) answer++;
    }
    
    return answer;
}

가로의 길이가 n일 때 타일을 배치할 수 있는 방법의 수는 아래와 같이 변화한다.

n = 1		1가지
n = 2		2가지
n = 3		3가지
n = 4	문제 설명 참조	5가지
n = i		DP[i-1] + DP[i-2]

즉 이 문제도 동적 계획법을 이용해 풀 수 있다.

식을 세워보면 DP[i] = DP[i-1] + DP[i-2]가 되므로 이를 가지고 길이가 n인 직사각형에 타일을 배치하는 방법의 수를 구하면 된다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int DP[60001];
    
    DP[1] = 1;
    DP[2] = 2;
    
    for(int i = 3; i <= n; i++) 
        DP[i] = (DP[i-1] + DP[i-2]) % 1000000007; 
    
    return DP[n];
}

LRU(Least Recently Used) 알고리즘

가장 오랫동안 참조되지 않은 페이지를 교체하는 방식

기억 공간에 동일한 데이터가 존재하면 해당 데이터를 삭제한 뒤 top에 넣는다.

동일한 데이터가 존재하지 않을 때 기억 공간이 가득 찼다면 가장 오래된 데이터를 삭제한 뒤 새로운 데이터를 넣고

아니라면 바로 데이터를 넣는다. 

풀이 방법

데이터를 앞/뒤에서 삭제하기 용이한 덱(Deque)을 사용하였다.

1. cacheSize가 0이라면 캐시가 없기 때문에 항상 miss이므로 5*cities.size()를 리턴한다.

2. string형 덱 cache를 선언한다.

3. 대소문자 구분을 하지 않으므로 cities[i]를 소문자로 변환시켜준다.

4. miss를 판단할 bool형 cacheMiss를 true로 선언해주고 캐시 내부를 순회하며 cities[i]와 동일한 데이터가 있다면 캐시에서 해당 데이터를 지우고 answer++, cacheMiss = false를 한 다음 break한다.

5. cities[i]를 캐시에 넣는다.

6-1. cacheMiss가 true면 answer에 5를 더해준다.

6-2. cacheMiss가 true고 cache.size()가 cacheSize보다 크면 가장 오래된 데이터를 삭제하고 answer에 5를 더해준다.

7. 반복문이 끝난 후 answer 리턴 

#include <string>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    if(cacheSize < 1) return 5 * cities.size();
    
    deque<string> cache;
    
    for(int i = 0; i < cities.size(); i++) {
        transform(cities[i].begin(), cities[i].end(), cities[i].begin(), ::tolower);
        
        bool cacheMiss = true;
        
        for(int j = 0; j < cache.size(); j++) {
            if(cache[j] == cities[i]) {
                cache.erase(cache.begin() + j);
                answer++;
                cacheMiss = false;
                break;
            }
        }
            
        cache.push_back(cities[i]);
        
        if(cacheMiss) {
            if(cache.size() > cacheSize) 
                cache.pop_front();
            answer += 5;
        }
    }
    
    return answer;
}

점프와 순간 이동 - 프로그래머스

점프는 한 칸씩 이동하며 칸당 1만큼 건전지를 사용하고 순간 이동은 건전지를 사용하지 않고 현재까지 온 거리 x 2만큼 이동한다. n만큼 이동할 때 건전지 사용량이 최소가 되는 값 return이므로 n을 2로 나누며 나머지가 1이 될 때마다 answer++해주면 된다.

핵심은 순간이동의 x2이다.

예시를 들면 표와 같이 된다.(점프는 J, 순간이동은 T)

풀이 방법

1. n을 2로 나눈 나머지가 1이면 answer++

2. n /= 2를 한 뒤 반복

3. 반복이 끝나면 answer 리턴

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    
    while(n) {
        if(n % 2) ans++;
        n /= 2;
    }

    return ans;
}

프로그래머스 - 카펫

1. 모든 격자의 수의 합은 brown + red, 카펫의 가로, 세로 길이는 최소 3이상이다.

2. 반복문을 돌리며 width에 sum을 height로 나눈 몫을 대입한다.

3. sum이 height로 나누어 떨어지고 (width -2)*(height-2) 즉 테두리를 1줄을 제외한 부분의 값이 yellow와 같으면 answer에 width와 height를 담고 break한다.

4. answer 리턴

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown + yellow;
    
    for(int height = 3;;height++){
        int width = sum / height;
        if(!(sum % height) && (width - 2)*(height - 2) == yellow) {
            answer.push_back(width);
            answer.push_back(height);
            break;
        }
    }
    
    return answer;
}

프로그래머스 - 올바른 괄호

풀이 방법

1. 괄호가 짝지어진 것을 판단하기 위해 int형 countBracket을 선언

2. s[0]가 ')'면 괄호가 제대로 짝이 지어질 수 없으므로 false를 리턴하고 아니면 countBracket++을 해준다.

3. s[i]가 '('면 countBracket++을 해주고 ')'면 countBracket--를 해준다.

4. 이를 반복하며 도중에 countBracket이 음수가 되면 제대로 짝이 지어지지 않으므로 false를 리턴

5. 반복문이 끝난 뒤 countBracket이 0이면 괄호가 올바르게 짝지어졌으므로 true 리턴

6. 아니라면 false 리턴

#include <string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int countBracket = 0;
    
    if(s[0] == ')') return false;
    else countBracket++;
    
    for(int i = 1; i < s.length(); i++){
        if(s[i] == '(') countBracket++;
        else if(s[i] == ')') countBracket--;
        
        if(countBracket < 0) return false;
    }
    
    if(countBracket == 0) return true;
    else return false;
}