99코딩

• i점에서 라이언이 어피치보다 1발 더 맞춰야 라이언이 득점
• 2발 더 맞춰도 얻는 점수는 같기에 어피치보다 2발 이상 맞추는건 낭비
• 가장 큰 점수 차로 이기는게 여러가지면, 가장 낮은 점수를 더 많이 맞춘 경우를 리턴 > 각 점수마다 위를 반복한 후 남은 화살을 전부 0점에서 소모
• 위를 조건으로 화살 명중 조합을 만들고 각 조합마다 점수를 계산해서 점수차가 가장 큰 경우와 해당 경우가 2개 이상일 시 0점에서 소모된 화살이 더 많은 경우를 리턴
• 점수가 어피치보다 낮으면 -1 리턴

#include <string>
#include <vector>

using namespace std;

// 완전탐색 필요 > dfs 사용

int bestDiff = -1, RyanScore = 0, ApeachScore = 0;
vector<int> score, ryan, apeach, ryanBest;

void checkCondition() {
    int diff = RyanScore - ApeachScore;
    
    // ryan의 점수에서 apeach의 점수를 뺀 값이 0이하면 ryan이 이긴 것이 아님
    if(diff <= 0) return;
    // ryan이 이겼다면
    else {
        // 현재 최고점하고 diff가 같다면
        if(bestDiff == diff) {
            // 가장 낮은 점수를 더 많이 맞힌 경우 구하기
            // 가장 낮은 점수를 맞춘 수가 동일하다면 그 다음으로 낮은 점수로 넘어가야함
            for(int i = 10; i >= 0; i--) {
                // ryan이 0이 아니고 ryanBest가 0인 경우
                if(ryan[i] != 0 && ryanBest[i] == 0) {
                    ryanBest = ryan;
                    break;
                }
                // ryan이 0이고 ryanBest는 0이 아닌 경우
                else if(ryan[i] == 0 && ryanBest[i] != 0)
                    break;
                // 둘의 값이 0이 아니면 비교 필요
                else if(ryan[i] != 0 && ryanBest[i] != 0) {
                    // 둘의 값이 다르면
                    if(ryan[i] != ryanBest[i]) {
                        // ryan이 ryanResult보다 크면
                        if(ryan[i] > ryanBest[i]) {
                            // 점수차는 같으나 배열 갱신 필요
                            ryanBest = ryan;
                            break;
                        }
                    }
                }
            }
        }
        // 현재 최고점보다 ryanScore가 크거나 갱신된 적이 없다면
        else if(diff > bestDiff || bestDiff == -1) {
            // 갱신
            bestDiff = diff;
            ryanBest = ryan;
        }
    }
}

// 점수 계산
void calcScore() {
    int ryanScore = 0;
    int apeachScore = 0;
    
    for(int i = 0; i < 11; i++) {
        // i 배점에서 ryan과 apeach가 맞힌 개수가 동일하면
        if(ryan[i] == apeach[i]) {
            // ryan과 apeach 둘 다 i 점을 맞추지 않았을 때
            if(ryan[i] == 0 && apeach[i] == 0)
                continue;
            else
                apeachScore += 10 - i;
        }
        // 맞힌 개수가 동일하지 않을 때
        else {
            // 라이언이 어피치보다 많이 맞췄으면 라이언 점수 증가 
            if(ryan[i] > apeach[i])
                ryanScore += 10 - i;
            // 아니면 어피치 점수 증가
            else
                apeachScore += 10 - i;
        }
    }
    
    // 라이언 점수
    RyanScore = ryanScore;
    
    // 어피치 점수
    ApeachScore = apeachScore;
}

void dfs(int cnt, int i, int n) {
    // 화살을 전부 사용했으면
    if(cnt == n) {
        // 계산
        calcScore();
        
        // 조건 체크
        checkCondition();
        return;
    }
    
    int remain = n - cnt;
    
    // 가장 큰 점수 차이로 우승하는 방법이 여러가지면, 가장 낮은 점수를 더 많이 맞춰야함
    // 2번째 조건을 위해 i == 10에서 남은 화살이 있으면 전부 소모해야함
    if(i == 10) {
        ryan[i] = remain;
        dfs(cnt + remain, i + 1, n);
        ryan[i] = 0;
    }
    // i == 10이 아닐 때
    else {
        // 남은 화살 수가 apeach[i]보다 크거나 같으면
        if(apeach[i] + 1 <= remain) {
            // apeach[i] + 1을 ryan[i]에 삽입
            ryan[i] = apeach[i] + 1;
            dfs(cnt + ryan[i], i + 1, n);
            ryan[i] = 0;
        }
        
        dfs(cnt, i + 1, n);
    }
}

vector<int> solution(int n, vector<int> info) {
    score.resize(2, 0);
    ryan.resize(11, 0);
    
    apeach = info;
    
    dfs(0, 0, n);
    
    // bestDiff가 갱신된적 없다면 이기는 경우가 없음 > -1 리턴
    if(bestDiff == -1) ryanBest.push_back(-1);
    
    return ryanBest;
}

• 일단 dfs를 통해 각 이모티콘들의 할인 조합을 만들어주기로 함
• 할인율 4종류에 이모티콘은 최대 7종류라 dfs 자체는 최대 28번 수행이라 시간 초과는 없을거라 예상
• 이후 조합이 다 만들어지면 매출액과 플러스 가입자 수를 구함
• 조건 중 플러스 가입자 수 증가가 1순위, 매출액 최대화가 2순위이므로 플러스 가입자 수가 더 많은 조합의 가입자 수와 매출액을 저장하고 가입자 수가 동일하다면 매출액을 비교해서 저장

나름 간단한 완전탐색 문제였다.

#include <string>
#include <vector>

using namespace std;

// 할인율 배열
int discount[4] = {10, 20, 30, 40};

void dfs(int cnt, int size, vector<vector<int>> users, vector<int> emoticons, 
         vector<int>& answer, vector<pair<int, int>>& prices) {
    // 모든 이모티콘에 할인 적용이 완료되었을 때
    if(cnt == size) {
        // 플러스 가입자 수, 매출액
        int plus = 0, total = 0;
        
        // 각 사용자마다
        for(int i = 0;i < users.size(); i++)
        {
            int tmp = 0;
            
            for(int j = 0;j < size; j++)
                // 할인율이 마음에 들면
                if (users[i][0] <= prices[j].second) tmp += prices[j].first;
            // 소지금보다 구매에 많이 사용한다면 플러스 이용자
            if(tmp >= users[i][1]) plus++;
            else total += tmp;
        }
        
        // 가입자 수가 더 많을 때 << 1번 목표
        if (plus > answer[0])
        {
            answer[0] = plus;
            answer[1] = total;
        }
        // 가입자 수가 동일하다면 판매액이 더 클 때 << 2번 목표
        else if(plus == answer[0] && total >= answer[1]) answer[1] = total;
        
        return ;
    }
    
    // 이모티콘 할인 조합 만들기
    for(int i = 0; i < 4; i++) {
        prices[cnt].first = emoticons[cnt] * (100 - discount[i]) / 100;
        prices[cnt].second = discount[i];
        dfs(cnt + 1, size, users, emoticons, answer, prices);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer(2, 0);
    // {할인가, 할인율} 쌍
    vector<pair<int, int>> prices(7, {0, 0});
    
    dfs(0, emoticons.size(), users, emoticons, answer, prices);
    
    return answer;
}

• 직선 n개 중에서 2개씩 뽑아서 해당 두 직선의 교점을 구해야함
• 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음 
• 모든 직선 쌍은 교점이 유일하게 존재하거나 평행함
• 문제 아래의 참고 사항에서 두 직선이 평행한지와 두 직선의 교점을 구하는 방법이 나와있으므로 참고하면 됨
• 모든 직선쌍의 교점을 구한 뒤 해당 영역을 그리기 위해 가장 작은 x, y 좌표와 가장 큰 x, y 좌표를 구해야함
• 이후 maxX - minX, maxY - minY가 그릴 영역의 가로, 세로가 됨
• 영역을 그린 뒤 그래프의 좌표와 그린 영역의 좌표가 다른 것을 감안해 좌표이동을 하여 '*'을 해당 좌표에 삽입

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

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    vector<pair<int, int>> coor;
    // minX, maxX, minY, maxY 초기화
    int minX = INT32_MAX, maxX = INT32_MIN, minY = INT32_MAX, maxY = INT32_MIN;
    
    for(int i = 0; i < line.size(); i++) {
        for(int j = i + 1; j < line.size(); j++) {
            
            // 이 값이 0이면 두 직선은 평행
            int isParallel = line[i][0] * line[j][1] - line[i][1] * line[j][0];
            
            // 0이 아니면 교점이 존재
            if(isParallel) {
                long long x = (1LL * line[i][1] * line[j][2] - 1LL * line[i][2] * line[j][1]);
                long long y = (1LL * line[i][2] * line[j][0] - 1LL * line[i][0] * line[j][2]);
                
                // 이 중 정수로만 표현되는 좌표를 저장    
                if(x % isParallel == 0 && y % isParallel == 0) coor.push_back({x / isParallel, y / isParallel});
            }
        }
    }
    
    // 정렬 후 중복되는 좌표 제거
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    
    // minX, maxX, minY, maxY를 구함
    for(int i = 0; i < coor.size(); i++) {
        minX = min(minX, coor[i].first);
        maxX = max(maxX, coor[i].first);
        minY = min(minY, coor[i].second);
        maxY = max(maxY, coor[i].second);
    }
    
    // 각각 영역의 가로, 세로
    int x = maxX - minX, y = maxY - minY;
    
    // 해당 영역의 크기만큼 answer를 '.'로 초기화
    for(int i = 0; i <= y; i++) {
        string board(x + 1, '.');
        answer.push_back(board);
    }
    
    // 좌표이동 후 '*'를 삽입
    for(int i = 0; i < coor.size(); i++) 
        answer[maxY - coor[i].second][coor[i].first - minX] = '*';
    
    return answer;
}

각 분마다 몇 개의 객실이 존재해야하는지 구하는 방식으로 접근했다.

1.  room[1450]을 선언하고 0으로 초기화. 청소시간을 고려해서 1440 + 10을 하였다.

2. 각 예약의 대실 시작 시간과 대실 종료 시간 + 청소 시간을 분으로 구함

3. 위의 두 값 사이의 수를 인덱스로 가지는 요소들의 값을 증가

4. room 배열의 최댓값을 리턴

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<string>> book_time) {
    int answer = 0, room[1450] = {0, }; //24*60 + 10 = 1450
    
    for(int i = 0; i < book_time.size(); i++) {
    	//대실 시작 시간을 분으로 전환
        int reserveStart = stoi(book_time[i][0].substr(0, 2)) * 60 + stoi(book_time[i][0].substr(3, 2));
        //대실 종료 시간 + 청소 시간을 분으로 전환
        int reserveEnd = stoi(book_time[i][1].substr(0, 2)) * 60 + stoi(book_time[i][1].substr(3, 2)) + 10;
        
    	//대실 시작 시간부터 종료 시간까지 room배열의 값을 증가
        for(int time = reserveStart; time < reserveEnd; time++) {
            room[time]++;
        }
    }
    
    //room 배열 안의 가장 큰 값이 필요한 최소 객실 수
    for(int num : room)
        if(num > answer) answer = num;
    
    return answer;
}

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;
}