99코딩

1. 길이가 짧은 수열을 구하기 위한 minLen, 합을 구하기 위한 sum, 시작 인덱스를 구하기 위한 startIdx를 선언

2. startIdx부터 시작해서 i까지 sequence[i], sequence[i -1]...을 더하므로 i가 endIdx의 역할을 함

3. 계속해서 더해가다 sum이 k보다 커지면 부분 수열의 시작 인덱스부터 뺌 <= 이에 따라 startIdx가 증가

4. 만약 sum == k이고 i - startIdx의 값이 minLen 보다 작다면 minLen의 값을 갱신하고 startIdx와 i를 answer에 담음

5. 모든 반복이 끝난 뒤 answer 리턴

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer(2, 0);
    int minLen = 1000001, sum = 0, startIdx = 0;
    
    for(int i = 0; i < sequence.size(); i++) {
        sum += sequence[i];
        
        while(sum > k) {
            sum -= sequence[startIdx++];
        }
        
        if(sum == k && i - startIdx < minLen) {
            minLen = i - startIdx;
            
            answer[0] = startIdx;
            answer[1] = i;
        }
    }
    
    return answer;
}

처음 접근할 때 이상하게 접근해서 시간이 걸린 문제였다.

1. 보조 컨테이너 벨트 역할을 할 스택을 생성

2. 컨테이너 벨트에 있는 i번째 상자를 보조 컨테이너 벨트에 넣음

3. 이후 subConveyer의 크기가 0이 아니고 subConveyer의 top과 order[answer]가 같을 때 answer를 증가시키고 subConveyer에 pop을 수행

4. 위를 order의 크기만큼 반복

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    
    stack<int> subConveyer;
    
    for(int i = 1; i <= order.size(); i++) {
        subConveyer.push(i);
        
        while (subConveyer.size() != 0 && subConveyer.top() == order[answer]){
            answer++;
            subConveyer.pop();
        }
    }
    
    return answer;
}

이름을 인덱스로 매핑하기 위한 Map

서로 주고 받은 선물 개수를 저장하는 2차원 배열

각자 선물 지수를 저장하는 1차원 배열

위 3가지를 이용해서 문제를 해결

#include <string>
#include <vector>
#include <map>
#include <sstream>

using namespace std;

int giftArray[50][50]; 		//주고 받은 선물 배열
int indexToGiftFactor[50];	//선물 지수 배열

map<string, int> nameToIndex;	//이름을 인덱스로 매핑

int solution(vector<string> friends, vector<string> gifts) {
    int answer = 0;
    
    for(int i = 0; i < friends.size(); i++) //우선 friends의 이름들을 순서대로 인덱스와 매핑
        nameToIndex[friends[i]] = i;
    
    for(int i = 0; i < gifts.size(); i++){
        istringstream iss(gifts[i]);
        string name1, name2;
        iss >> name1 >> name2;		
        
        int idx1 = nameToIndex[name1]; //idx1 = 주는 사람
        int idx2 = nameToIndex[name2]; //idx2 = 받는 사람
        
        indexToGiftFactor[idx1]++;	//주는 사람의 선물 지수 증가
        indexToGiftFactor[idx2]--;	//받는 사람의 선물 지수 감소
        giftArray[idx1][idx2]++;	//idx1이 idx2한테 준 선물 갯수 증가
    }
    
    for(int i = 0; i < friends.size(); i++){
        int giftCount = 0;
        string name1 = friends[i];
        int idx1 = nameToIndex[name1];	//idx1 = 주는 사람
        
        for(int j = 0; j < friends.size(); j++){
            if(i == j) continue;
                
            string name2 = friends[j];
            int idx2 = nameToIndex[name2];	//idx2 = 받는 사람
            
            if(giftArray[idx1][idx2] > giftArray[idx2][idx1] || 
               (giftArray[idx1][idx2] == giftArray[idx2][idx1] && indexToGiftFactor[idx1] > indexToGiftFactor[idx2]))
               giftCount++;	//idx1이 idx2에게 준 선물의 개수가 많거나 같으면서 선물지수가 높으면 받는 선물의 개수 증가 
        }
        
        if(giftCount > answer) answer = giftCount; //받는 선물 개수가 answer보다 크면 갱신
    }
    
    return answer;
}

1. 일단 모든 공격이 끝난 직후의 체력을 리턴하기 때문에 마지막 공격의 시전 시간을 구함

2. lastAttackTime까지 1초 단위로 반복한다고 가정하고 공격이 들어온다면 체력을 감소시키고 붕대 감는 시간을 초기화 시킴

3. 그리고 매 초 붕대를 감으며 현재 체력이 최대 체력이 넘어서면 현재 체력을 최대 체력으로 변경 시키고 붕대 감는 시간을 1씩 증가

4. 붕대를 완전히 감는데 성공했다면 bandage[2]만큼 체력을 회복하고 위 3번과 마찬가지로 현재 체력이 최대 체력을 넘어서지 않도록 함

5. 마지막 공격이 끝난 직후의 체력을 리턴

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> bandage, int health, vector<vector<int>> attacks) {
    int completeTime = 0;
    int curHealth = health;
    
    int lastAttackTime = attacks[attacks.size() - 1][0];
    
    for(int i = 0, idx = 0; i <= lastAttackTime; i++){
        if(attacks[idx][0] == i){
            curHealth -= attacks[idx++][1];
            
            if(curHealth <= 0) return -1;
            
            completeTime = 0;
            
            continue;
        }
        
        curHealth = min(curHealth + bandage[1], health);
        
        completeTime++;
        
        if(completeTime == bandage[0]){
            curHealth = min(curHealth + bandage[2], health);
            
            completeTime = 0;
        }
    }
    
    return curHealth;
}

2차원 배열에 저장된 값을 이용하는 간단한 문제

1. 2차원 보드판의 길이를 구함(board와 board[n]의 길이는 동일)

2. 주어진 h, w에 있는 값을 구함

3. [h][w]를 기준으로 상하좌우로 1칸씩 이동 가능한지 확인하고 가능하다면

  해당 위치에 있는 값을 2번에서 구한 값과 비교 후 같으면 answer++

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<string>> board, int h, int w) {
    int answer = 0;
    int maxLength = board.size() - 1;
    
    string color = board[h][w];
    
    
    if(h > 0)
        if(color == board[h-1][w]) answer++;
    
    if(w > 0)
        if(color == board[h][w-1]) answer++;
    
    if(h < maxLength)
        if(color == board[h+1][w]) answer++;
    
    if(w < maxLength)
        if(color == board[h][w+1]) answer++;
    
    return answer;
}

오랜만에 1레벨쪽을 보니까 4 문제가 추가되어 있어서 풀어보았습니다.

1. Map을 이용해 각 컬럼 명을 Key, 인덱스를 Value로 하여 매핑

2. 범위 기반 for문을 이용해 조건(ext 컬럼의 값이 val_ext보다 작은)에 맞는 데이터를 answer 벡터에 추가

3. sort_by 컬럼에 해당하는 인덱스의 값을 기준으로 answer 벡터를 오름차순으로 정렬

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

map<string, int> m = {{"code", 0}, {"date", 1}, {"maximum", 2}, {"remain", 3}};

int idx;

bool cmp(const vector<int> &a, const vector<int> &b) {
    return a[idx] < b[idx];
}

vector<vector<int>> solution(vector<vector<int>> data, string ext, int val_ext, string sort_by) {
    vector<vector<int>> answer;
    
    for(auto d : data) {
        if(data[m[ext]] < val_ext)
            answer.push_back(d);
    }
    
    idx = m[sort_by];
    
    sort(answer.begin(), answer.end(), cmp);
    
    return answer;
}

풀이 방법

1. 각 큐의 합을 구한다

2. 각 큐의 합을 더했을 때 값이 홀수라면 두 큐의 값을 같게 만들 수 없으므로 -1을 리턴

3. 큐의 사이즈를 qSize 변수에 담고 while문의 조건에 이동 횟수가 qSized * 4를 넘어가지 않도록 한다

4. 각 큐의 합이 같다면 count를 리턴하고 그렇지 않다면 각각 pop과 insert를 수행해준다.

5. 만약 while문이 끝날 때까지 각 큐의 합이 같아지지 않았다면 -1을 리턴

#include <string>
#include <vector>

using namespace std;

long count, sum1, sum2, goal, idx1, idx2;

int solution(vector<int> queue1, vector<int> queue2) {
    for(int i = 0; i < queue1.size(); i++)
        sum1 += queue1[i];
    
    for(int j = 0; j < queue2.size(); j++)
        sum2 += queue2[j];
    
    goal = sum1 + sum2;
    
    if(goal % 2 == 1)
        return -1;
    
    int qSize = queue1.size();
    
    while(count < qSize * 3) {
        if(sum1 == sum2) return count;
        else if(sum1 < sum2) {
            queue1.push_back(queue2[idx2]);
            sum1 += queue2[idx2];
            sum2 -= queue2[idx2];
            queue2[idx2++] = 0;
        }
        else {
            queue2.push_back(queue1[idx1]);
            sum1 -= queue1[idx1];
            sum2 += queue1[idx1];
            queue1[idx1++] = 0;
        }
        count++;
    }
    
    return -1;
}

• 각 칸의 숫자는 해당 칸에서 최대 며칠 머물 수 있는지 나타냄
• 이어진 땅들은 하나의 무인도
• 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;
}