코딩생존기

문제 설명을 잘 읽어야한다.

m: 기억한 멜로디 music: 방송된 곡 정보 정답 : 일치하는 음악

핵심은 방송된 곡 정보가 기억하고있는 멜로디패턴에 있는지를 확인해야한다. 

1단계로 #붙은것도 1초로 인식하니 1글자 영단어로 바꿔준다.

2단계로 곡이 재생된 방송시간과 곡의 길이를 가져온다.

재생된 방송시간보다 곡의 길이가 길 경우는 중간에 자르고 짧을 경우는 반복한다. 

그렇게 만들어진 음악에 기억한 멜로디 패턴이 있다면 answer로 지정해준다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
//m: 기억한 멜로디 music: 방송된 곡 정보 정답 : 일치하는 음악 
//핵심 : 방송된 곡 정보가 기억하고있는 멜로디패턴에 있는지
string change(string& m, map<string, char>& s) {               //#붙은 음들 바꿔주기
    string out = "";
    for (int i = 0; i < m.size(); i++) {
        if (m[i + 1] == '#') {
            out += s[m.substr(i, 2)];
            i++;
        }
        else {
            out += m[i];
        }
    }
    return out;
}

string solution(string m, vector<string> musicinfos) {
    string answer = "(None)";
    int aHour = 0, bHour = 0, aMin = 0, bMin = 0, time = 0, btime = 0;
    string melody = "", title = "";
    map<string, char> s;

    s["C#"] = 'c';
    s["D#"] = 'd';
    s["F#"] = 'f';
    s["G#"] = 'g';
    s["A#"] = 'a';

    melody = change(m, s);

    for (int i = 0; i < musicinfos.size(); i++) {
        string tmp = "", music = "";

        aHour = stoi(musicinfos[i].substr(0, 2)) * 60;
        aMin = stoi(musicinfos[i].substr(3, 2));
        bHour = stoi(musicinfos[i].substr(6, 2)) * 60;
        bMin = stoi(musicinfos[i].substr(9, 2));
        time = (bHour + bMin) - (aHour + aMin);     //나중시간- 전 시간

        for (int j = 12; j < musicinfos[i].size(); j++) { //곡 제목부터
            if (musicinfos[i][j] == ',') {
                title = musicinfos[i].substr(12, j - 12);
                tmp = musicinfos[i].substr(j + 1);             //곡의 음 패턴
                break;
            }
        }
        music = change(tmp, s);
        if (music.size() < time)            //재생시간이 곡 시간보다 클경우 반복
        {
            tmp = music;

            for (int j = 1; j < time / tmp.size(); j++)
                music += tmp;
            for (int j = 0; j < time % tmp.size(); j++)
                music += tmp[j];
        }
        else                //곡시간보다 재생시간이 짧으면 자르기
            music = music.substr(0, time);

        if (music.find(melody) != string::npos) {
            if (btime < time) {
                answer = title;
                btime = time;
            }
        }
    }
    return answer;
}

반시계 방향으로 달팽이 채우기를 진행한 결과를 1차원 벡터로 반환해줘야한다.

반시계 방향으로 진행할때 총 3단계를 거친다

1. 아래로 이동

2. 오른쪽으로 이동

3. 위로 이동

일단 2차원벡터를 0으로 초기화시켜둔 다음 진행한다.

1단계 : 아래로 이동

아래로 이동에서 고려해야할 점은 단계가 진행될 수록 열과 끝나는 부분이 달라야한다는 점이다

열은 증가해야하고 끝나는 부분을 줄어들어야한다.

그리고 다 이동하고 나서는 오른쪽으로 이동할 위치를 지정해주기 위해 

2단계 : 오른쪽으로 이동

2단계에서 고려해야할 점은 행과 끝나는 범위의 열이다.

열은 전에 했던 부분에서 1 증가값에서 시작해서  채워진부분 전까지 진행하고

행은 단계별로 감소해야한다.

3단계 : 위쪽으로 이동

3단계에서 고려해야할 점은  끝나는 범위의 행과 열이다.

행은 이전값의 하나 전 인덱스에서 채워진 인덱스앞까지이고

열은 단계별로 감소해야한다.

구현을 잘 해야하는 문제인데 이해하기가 정말 어려웠다. 쓰고나서도 어려운 문제라 여러번 다시 봐야겠다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> triangle;
    
    if(n==1){
        answer.push_back(1);
        return answer;
    }
    
    for(int i=1;i<=n;i++){              //트라이앵글 모양 잡아주기
        vector<int>tmp;
        for(int j=0;j<i;j++) tmp.push_back(0);
        triangle.push_back(tmp);
    }
    
    int col=0,row=0;
    int num=1;
    int turn=0;                 //turn 한단계가 끝날수록 증가 -> 값이 들어갈 수 있는 곳 범위, 전체-turn 반복횟수
    while(true) {
        if (triangle[col][row] > 0) break;          //만약 채워져있는 칸이라면 끝
        
        for(int i=col;i<n-turn;i++){            //아래로 이동 
            if(triangle[i][turn]==0){
                triangle[i][turn]=num++;
                col=i; row=turn;
            }else break;
        }
        row+=1; turn+=1;        //채워져있는 거 다음 부분부터 
        
        for(int j=row;j<=n-turn;j++){            //오른쪽으로 이동 
            if(triangle[n-turn][j]==0){             //
                triangle[n-turn][j]=num++;
                col=n-turn; row=j;
            }else break;
        }
        col-=1;         //채워져있는거 이전 부터
        
        for(int k=col;k>=turn;k--){         //끝~채워진거 앞까지 위로
            if(triangle[k][k-turn+1]==0){              //k~1번째 까지
                triangle[k][k-turn+1]=num++;
                col=k; row=k-turn+1;
            }else break;
        }
        col+=1;
    }
    
    for(int i=0;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++) answer.push_back(triangle[i][j]);
    }
    return answer;
}

1로 구성된 가장 큰 정사각형을 찾는 문제이다. 

정사각형의 넓이가 2이상일때 자신의 왼쪽, 위, 왼쪽 대각선위가 모두 1이상이여야하며 이때 하나라도 0이라면 정사각형이 될 수 없다. 

2*2 정사각형을 보자면 오른쪽 아래를 기준으로 보자면 자신의 왼쪽, 위, 왼쪽 대각선위가 모두 1이여야 한다. 그렇게 생각해보자면 오른쪽 아래의 값이 2가 될 수 있다.

3*3을 보자면 자신의 왼쪽, 위, 왼쪽 대각선위가 모두 2여야 한다. 이때 오른쪽 아래의 값은 선분의 길이인 3이 된다.

이론을 이해하기 어려웠지만 익숙해지면 쉽게 풀 수 있을 것같다.

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

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    for (int i = 1; i < board.size(); i++) {
        for (int j = 1; j < board[i].size(); j++) {
            if (board[i][j] == 1) {
                board[i][j] = 1 + min({ board[i - 1][j],board[i][j - 1],board[i - 1][j - 1] });         //왼쪽,위,왼쪽 대각선 위
                answer = max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}

겹치는 선분의 길이

겹치는 선분의 길이를 구하는 문제이다. 

선분의 수가 많이 않기때문에 전체를 순회하며 횟수를 카운트하면 될 것 같다. 

쉽게 생각해보자면 선분 벡터를 순회하면서 시작점에서 부터 끝점까지 순회하면서 만약 선분에 걸쳐져있는 점이라면 횟수를 증가시켜 2개이상의 선분이 걸쳐진 점이라면 answer을 증가시켜준다. 

#include <string>
#include <vector>

using namespace std;
int line[200];
int solution(vector<vector<int>> lines) {
    int answer = 0;
    for (int i = 0; i < lines.size(); i++) {
        for (int j = lines[i][0]; j < lines[i][1]; j++) {               //시작점 ~ 도착점-1 까지에 있는 선분있다면 ++
            line[j + 100]++;                  //음수값도 양수값범위안에 들도록
        }
    }
    for (int i = 0; i < 200; i++) {
        if (line[i] >= 2) {
            answer++;
        }
    }
    return answer;
}

안전지대

지역을 순회하면서 만약 지뢰가 있다면 지역의 범위에서 벗어나지 않는 선에서 상하좌우 대각선의 지역을 안전지대를 표시하는 0과 지뢰가 있는 지역인 1인 수를 제외하고 할당해주고 안전지대를 체크하면된다.

#include <string>
#include <vector>

using namespace std;

int dx[8] = { -1,1,0,0,-1,-1,1,1 };     //상하좌우 대각선
int dy[8] = { 0,0,-1,1,-1,1,-1,1 };     //상하좌우 대각선
int solution(vector<vector<int>> board) {
    int answer = 0;
    for (int i = 0; i < board.size(); i++) {            //순회하면서 
        for (int j = 0; j < board[0].size(); j++) {         //위,아래,좌,우,대각선에 지뢰가 있다면 위험지역
            if (board[i][j] == 1) {
                for (int k = 0; k < 8; k++) {
                    int curx = i + dx[k];
                    int cury = j + dy[k];
                    if (curx >= 0 && curx < board.size() && cury >= 0 && cury < board.size()) {
                        if (board[curx][cury] != 1) board[curx][cury] = 2;                   //안전지대가 아니라고 지뢰가 있는건 아니라서 1과는 다른값으로 할당
                    }
                }
            }
        }
    }

    for (int i = 0; i < board.size(); i++) {            //순회하면서 
        for (int j = 0; j < board[0].size(); j++) {         //위,아래,좌,우,대각선에 지뢰가 있다면 위험지역
            if (board[i][j] == 0) answer++;
        }
    }
    return answer;
}

무게에 따른 사람의 수를 모두 저장해준다음 그 벡터를 순회하면서

같은 무게가 있으면 어디에 앉든 균형을 이루기 때문에 조합으로 수를 구해주고

2 3 4 m 자리가 있어서 나올 수 있는 비율은 2:3 2:4=1:2 3:4 가 있기 때문에

이 에 맞는 값이 있다면 경우의 수 를 추가해주면 된다.

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    vector<long long> cnt(1001, 0);      //몸무게 별 사람수
    for (int i = 0; i < weights.size(); i++) {
        cnt[weights[i]]++;
    }
    //나올수 있는 비율 2:3 2:4=1:2 3:4
    for (int i = 0; i < weights.size(); i++) {
        if (weights[i] % 2 == 0) {                //2:3
            long long base = (weights[i] / 2) * 3;
            if (base <= 1000) answer += cnt[base];
        }
        if (weights[i] % 3 == 0) {                //3:4
            long long base = (weights[i] / 3) * 4;
            if (base <= 1000) answer += cnt[base];
        }
        long long base = weights[i] * 2;
        if (base <= 1000) answer += cnt[base];
    }

    for (int i = 100; i <= 1000; i++) {
        if (cnt[i] >= 2)
            answer += (long long)(cnt[i] * (cnt[i] - 1)) / 2;           //같을 때
    }

    return answer;
}

ext의 값이 val_ext보다 낮은 것을 저장하고 sort_by값에 따라 오름차순 정렬하는 문제이다. 처음에는 switch 문을 통해 idx1, idx2를 정해서 저장 및 정렬을 하려고 했는데 switch 문에는 문자열을 그냥 쓸 수 가 없는 것 같아서 map 자료형을 통해 idx 값을 정해서 저장 및 분류를  해주었다. 또한 compare 함수로 기준 값에 따라 오름차순 정렬되도록 만들었다.

코드

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

using namespace std;
map<string,int> m1={{"code",0},{"date",1},{"maximum",2},{"remain",3}};
int idx;
bool compare(const vector<int> &data1,const vector<int> &data2){
    return data1[idx]<data2[idx];
}
vector<vector<int>> solution(vector<vector<int>> data, string ext, int val_ext, string sort_by) {
    vector<vector<int>> answer;
    idx=m1[sort_by];
    for(auto d: data){
        if(d[m1[ext]]<=val_ext){
            answer.push_back(d);
        }
    }
    sort(answer.begin(),answer.end(),compare);
    return answer;
}

의사코드가 잘나와있는 문제라 그대로 구현만 해주면 쉽게 풀리는 문제이다. 중요한 건 위 아래 왼쪽 오른쪽을 탐색하고 그 탐색한 값이 표의 크기 안에서 존재하는 지 확인해주면 된다.

#include <string>
#include <vector>

using namespace std;

int dh[4]= {0,1,-1,0};
int dw[4]= {1,0,0,-1};
int solution(vector<vector<string>> board, int h, int w) {
    int answer = 0;
    int size=board.size();
    int wsize=board[1].size();
    for(int i=0;i<4;i++){
        int h_check=h+dh[i];
        int w_check=w+dw[i];
        if(h_check>=0&&h_check<size&&w_check>=0&&w_check<wsize){
            if(board[h][w]==board[h_check][w_check]){
                answer++;
            }
        }
    }
    return answer;
}

참가자 이름과 완주자이름을 비교하여 완주하지못한 사람을 찾으면 된다. 

나는 map 자료형을 사용해서 참여자 벡터를 순회하면서 해당 이름의 값을 증가시켜주고 그 뒤에 완주자 벡터를 순회하면서 해당 이름의 값을 줄여준다. 이때 해당 이름의 값이 1보다 크거나 같을 경우 통과하지 못하였다는 것이므로 answer에 추가해준다. 

동명이인이 있을 수 도 있어서 answer에 넣은 뒤 해당 이름의 값을 줄여준다. 

#include <string>
#include <vector>
#include <map>
using namespace std;
map<string,int> m1;
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    for(int i=0;i<participant.size();i++){
        m1[participant[i]]++;
    }
    for(int i=0;i<completion.size();i++){
        m1[completion[i]]--;
    }
    for(int i=0;i<participant.size();i++){
        if(m1[participant[i]]>=1){
            answer+=participant[i];
            m1[participant[i]]--;
        }
    }
    return answer;
}

처음에는 전체를 1로 만들고 체육복을 도난당한 사람을 0으로 여분의 체육복이 있는 사람을 2로 한 뒤 앞의 사람을 먼저 체크하고 뒤를 체크하는 방식으로 풀려고 했는데 여분의 체육복이 있는 사람도 도난 당할 수 있다는 점을 제대로 못 봐서 틀렸다. 어떻게 하면 좋을까 생각해봤을 때 전체를 1로 만들고 여분이 있는 사람은 2로 만든 다음에 도난 당한 사람은 해당 값을 --로 빼주면 될 것 같다고 생각했다. 

#include <string>
#include <vector>
#include <map>
using namespace std;
map<int, int> m1;
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        m1[i] = 1;					//전체를 1로 
    }

    for (int i = 0; i < reserve.size(); i++) {
        m1[reserve[i]] = 2;				//여분이 있는 사람은 2로
    }
    for (int i = 0; i < lost.size(); i++) {
        m1[lost[i]]--;					//도난당한 사람은 개수 빼주기
    }
    for (int i = 1; i <= n; i++) {
        if (m1[i] == 0) {				//만약 도난당해서 없는 사람이 있다면
            if (m1[i - 1] == 2) {		//앞사람을 먼저 체크
                m1[i - 1]--;
                m1[i]++;
            }
            else if (m1[i + 1] == 2) {
                m1[i + 1]--;
                m1[i]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (m1[i] >= 1) {			//1개 이상이 있다면 수업을 들을 수 있다.
            answer++;
        }
    }
    return answer;
}

문제가 길지만 요약하자면

숫자- 점수를 받고

영어- 점수를 계산

* / # - 보너스 점수

이여서 string을 순회하면서 이 점을 체크해주면 된다. 

*일때는 해당 점수와 바로 전의 점수를 2배 해주면 되고 #일 때는 마이너스로 만들어 주면 되는데 이 것은 영어가 나올 때 * #이 있는 지 확인해서 있다면 적용해주는 방식으로 하면 된다.

#include <string>
#include <cmath>
using namespace std;

int solution(string dartResult) {
    int answer = 0;
    int prev=0,score=0;
    
    
    for(int i=0;i<dartResult.size();i++)
    {
        //숫자 분리
        if(dartResult[i]>='0' && dartResult[i]<='9')
        {
            prev=score;         //보너스 계산을 위해 
            
            if(dartResult[i+1]=='0')
            {
                score=10;
                i++;
            }else{
                score=dartResult[i]-'0';
            }
        }else if(dartResult[i]=='S' || dartResult[i]=='D' || dartResult[i]=='T')
        {
            if(dartResult[i]=='D'){
                score=pow(score,2);
            }else if(dartResult[i]=='T'){
                score=pow(score,3);
            }
            
            if(dartResult[i+1]=='*')
            {           //보너스 점수 계산
                answer-=prev;
                prev*=2;
                score*=2;
                i++;
                answer+=prev;
            }else if(dartResult[i+1]=='#'){
                score*=-1;
                i++;
            }
            answer+=score;
        }
        
    }
    return answer;
}