99코딩

이름을 인덱스로 매핑하기 위한 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. routes를 순회하며 각 방향으로 지정된 횟수만큼 {curX, curY}를 이동하며 범위를 벗어나는지, 도중에 X가 있는지 체크한다.

3. 순회가 끝난 후 { nowCoordinate.first, nowCoordinate.second }를 리턴한다.

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

using namespace std;

map<char, int> m = {{'E', 0}, {'W', 1}, {'S', 2}, {'N', 3}};
int dirX[4] = {0, 0, 1, -1};
int dirY[4] = {1, -1, 0, 0};

vector<int> solution(vector<string> park, vector<string> routes) {
    pair<int, int> nowCoordinate;
    
    int height = park.size();
    int width = park[0].size();
    
    for(int i = 0; i < height; i++)
        for(int j = 0; j < width; j++)
            if(park[i][j] == 'S') {
                nowCoordinate = {i, j};
                break;
            }
    
    for(int i = 0; i < routes.size(); i++) {
        int dir = m[routes[i][0]];
        int dis = routes[i][2] - 48;
        
        int curX = nowCoordinate.first;
        int curY = nowCoordinate.second;
        
        for(;dis > 0; dis--) {
            curX += dirX[dir];
            curY += dirY[dir];
            
            if(curX >= height || curX < 0 || curY >= width || curY < 0 || park[curX][curY] == 'X') break;
        }
        
        if(dis <= 0) nowCoordinate = {curX, curY};
    }
    
    return { nowCoordinate.first, nowCoordinate.second };
}

문제 이해

• 최소한의 이동 거리로 모든 파일을 드래그
• '.'은 빈칸, '#'은 문서

문제 풀이

• string 벡터를 돌며 해당 인덱스의 원소가 '#'인 경우에 해당 위치의 좌표를 각각 비교해서 조건에 맞다면 삽입
• 반복문이 끝난 후 출력

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper) {
    int luX = 51, luY = 51;
    int rdX = 0, rdY = 0;
    int colLength = wallpaper.size();
    int rowLength = wallpaper[0].size();
    
    for(int i = 0; i < colLength; i++) {
        for(int j = 0; j < rowLength; j++) {
            if(wallpaper[i][j] == '#') {
                if(i < luX) luX = i;
                if(j < luY) luY = j;
                if(i + 1 > rdX) rdX = i + 1;
                if(j + 1 > rdY) rdY = j + 1;
            }
        }
    }
    
    return {luX, luY, rdX, rdY};
}

문제 조건

• 이름을 불린 선수는 앞의 선수를 추월
• 1등인 선수의 이름은 불리지 않음

문제 풀이

1. map에 각 선수의 등수를 저장하고 선수의 이름이 불릴 때마다 pos에 삽입
2. 두 선수의 순서를 바꿔주고 map에 저장된 각 선수의 등수를 조정
3. callings.size()만큼 반복 후 players 배열 리턴

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

using namespace std;

map<string, int> m;

vector<string> solution(vector<string> players, vector<string> callings) {
    for(int i = 0; i < players.size(); i++)
        m[players[i]] = i;
    
    for(int i = 0; i < callings.size(); i++) {
        string temp = "";
        int pos = m[callings[i]];
      
        m[players[pos]]--;
        
        temp = players[pos];
        players[pos] = players[pos - 1];
        players[pos - 1] = temp;
        
        m[players[pos]]++;
    }
    
    return players;
}

문제 조건

• 벽의 길이는 n미터, 롤러의 길이는 m미터
• 롤러는 벽을 벗어날 수 없음
• section 배열 안에 들어있는 번호들이 최소의 횟수로 전부 칠해져야함
• 이미 칠해진 부분은 또 칠해질 수 있음

문제 풀이

어차피 이미 칠해진 부분은 또 칠할 수 있기 때문에 n은 무시하였다.

1. 어디까지 칠해졌는지 확인하기 위해 paintedArea라는 변수를 선언
2. paintedArea에는 칠해지지않은 section[i]에 롤러의 길이 - 1을 더함으로써 몇 번째 벽까지 칠했는지 저장 후 answer++
3. paintedArea가 그 다음 section[i]보다 크거나 같다면 이미 해당 구역까지는 칠해졌으므로 continue
4. paintedArea가 section[i]의 마지막 원소보다 크거나 같다면 다시 칠해야하는 구역을 전부 칠한 것이므로 break
5. answer 리턴

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    int sectionLength = section.size();
    int paintedArea = 0;
    
    for(int i = 0;;i++) {
        if(paintedArea >= section[sectionLength - 1]) break;
        if(paintedArea >= section[i]) continue;
        
        paintedArea = section[i] + m - 1;
        answer++;
    }
    
    return answer;
}