풀이

function solution(strings, n) {
    strings.sort((a,b) =>{
        if(a[n] > b[n]){
            return 1;
        } else if(a[n] < b[n]){
            return -1;
        }else{
            if(a > b){
                return 1;
            }else{
                return -1;
            }
        }
    });

    return strings;
}

풀이를 진행하기 위해서 처음으로 sort매소드를 사용하여 n번째의 문자열을 비교하고 만약 같다면 사전식으로 비교해 주었다.

더 나은 풀이

function solution(strings, n) {
    // strings 배열
    // n 번째 문자열 비교
    return strings.sort((s1, s2) => s1[n] === s2[n] ? s1.localeCompare(s2) : s1[n].localeCompare(s2[n]));
}

한 문 장으로 간결하게 정렬하여 가져왔다.
3항 연산자를 사용하여 같을 때를 비교하고 같다면
localeCompare라는 매소드를 사용하여 문자열을 비교한다.
다르면 n번째를 localeCompare를 사용하여 비교한다.

localeCompare

이 메소드는 인자로 string을 받는다

// 같을 때는 0을 반환
'a'.localeCompare('a') // 0

// 사전 순으로 앞에 있을 때 -1을 반환
'a'.localeCompare('b') // -1

// 사전 순으로 뒤에 있을 때 1을 반환
'b'.localeCompare('a') // 1

문제

문제 분류 : dp

코드

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

int dp[1001] = { 0 };

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    int num;
    int max = 0;
    int max_dp = 1;
    int temp = 0;
    vector<int> vec;
    fill_n(dp, 1001, 1);
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> temp;
        vec.push_back(temp);
    }
    for (int i = 1; i < num; i++) {
        max = 0;
        for (int j = 0; j < i; j++) {
            if (vec[i] > vec[j]) {
                if (dp[j] > max)
                    max = dp[j];
            }
        }
        dp[i] += max;
        if (dp[i] > max_dp)
            max_dp = dp[i];
    }    
    cout << max_dp;
}

설명

이 문제를 DP로 풀기위해서 다음과 같이 접근 하였다.

1. 모든 dp 값을 1로 초기화 한다.

   • 왜냐하면 모두가 자기 자신을 수열로 가지기 때문이다.

2. 기준 dp 값의 이전값들을 모두 탐색하여 기준 값보다 작을 경우 max라는 변수에 작은 부분의 dp의 값과 기준 dp의 값을 더한다 (n + 1)

3. 반복하여 만약 max 값이 새로운 값보다 작다면 max 값을 변경하고 새로운 값으로 교체한다.

예시

예제문제로 {10, 20 , 10, 30 , 20 , 50} 배열이 있을 경우

1. dp[1]일 때

   1. dp[1] > dp [0] 이므로 dp[1] += dp[0] 이다.

2. dp[2]일 때

   1. dp[2] == dp[0] 이므로 넘어간다.
   2. dp[2] < dp[1] 이므로 넘어간다.

3. dp[3]일 때

   1. dp[3] > dp[0] 이므로 dp[3] += dp[0] 이다.
   2. dp[3] > dp[1] 이므로 dp[3] += dp[1] 이다.
   3. dp[3] > dp[2] 이므로 dp[3] += dp[2] 이다.

이렇게 반복해서 dp의 값중 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이가 된다.

문제

문제의 종류는 DP 이다. 문제를 풀기위해서 타일의 개수를 세어보았다.

N = 1 일때는 1 이므로 1개이다.

N = 2 일때는 00, 11 이므로 2개이다.

N = 3 일떄는 111, 100, 001 이므로 3개이다.

N = 4 일때는 1111, 1100 , 1001, 0011 , 0000 이므로 총 5개이다.

N = 5 일때는 11111, 11100, 11001, 10011, 00111, 10000, 00100, 00001 이므로 총 8개이다.

N = 6 일때는 111111, 111100, 111001, 110011, 100111, 001111, 110000, 100100, 100001, 001100, 001001, 000011, 000000 총 13개이다.

N = 7 일때는 1111111, 0011111, 1001111, 1100111, 1110011, 1111001, 1111100, 1110000, 1100100, 1001100, 0011100, 1100001, 1000011, 0000111, 1000000, 0010000, 0000100, 0000001, 1001001, 0011001, 0011001 으로 총 13개이다.

이러한 반복을 통해 특정한 점화식을 이 식을 가진다는 것을 알 수 있다.

Dp[i] = Dp[i-1] + Dp[i-2]

이를 통해 구현 한 코드는 다음과 같다.

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

int dp[1000001] = { 0,1,2,3 };

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    int num;
    for (int i = 4; i <= 1000000; i++) {
        dp[i] += (dp[i - 1] + dp[i - 2]) % 15746;
    }
    cin >> num;
    cout << dp[num];
}

문제

[1차] 비밀지도

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

using namespace std;

string convert(int a, int n) {
    string str;
    for (int i = 0; i < n; i++) {
        if (a % 2 == 0){
            str += ' ';   
        }
        else{
            str += '#';   
        }
        a /= 2;
    }
    reverse(str.begin(), str.end());
    return str;
}

string add(string str1, string str2) {
    string str;
    for (int i = 0; i < str1.size();i++)
    {
        if (str1[i] == ' ' && str2[i] == ' '){
            str += ' ';   
        }
        else {
            str += '#';
        }
    }
    return str;
}
vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    for (int i = 0; i < n; i++) {
        answer.push_back(add(convert(arr1[i], n), convert(arr2[i], n)));
    }
    return answer;
}

해설

1. Convert 함수

• 2진수 변환
  arr[i]의 값을 계속 2로 나누어서 나머지가 1일 때는 #을 저장 " "을 저장하고 <algorithm>헤더에 있는 convert로 거꾸로 출력해준다.

  2. Add 함수

• arr1과 arr2를 2진수로 변환 한 값들 더해준다. 둘다 " "이면 " "을 입력해주고 둘 중 하나라도 #라면 #을 입력해준다.

[1차 다트게임]

#include <string>
#include <vector>

using namespace std;

int solution(string dartResult) {
    int answer = 0;
    int count = -1;
    vector<int> vec;
    for(int i = 0 ; i < dartResult.length() ; i++){

        if(dartResult[i] == 'S'){
            vec[count] = vec[count];        
        }
        else if(dartResult[i] == 'D'){
            vec[count] = vec[count] * vec[count];  
        }
        else if(dartResult[i] == 'T'){
           vec[count] = vec[count] * vec[count] * vec[count];  
        }

        if(dartResult[i] == '*'){
            if(count == 0){
                vec[count] = vec[count] *2;
            }
            else{
                vec[count-1] *= 2;
                vec[count] *= 2;
            }
        }
        else if(dartResult[i] == '#'){
            vec[count] *= -1;
        }

        if(dartResult[i] == '1'){
            if(dartResult[i+1] == '0'){
                vec.push_back(10);
                i += 1;
            }
            else{
                vec.push_back(1);
            }
            count++;
        }
        else if(dartResult[i] > 46 && dartResult[i] < 58){
            vec.push_back(dartResult[i] - 48);
            count++;
        }

    }

    for(int i = 0 ; i < vec.size(); i++){
        answer += vec[i];
    }
    return answer;
}

해설

점수계산을 하나의 백터(vec)에 담아서 계산을 하였다.

String 형에서 10을 판별할때는 맨처음이 숫자 1이면 그 다음 값이 0인지 다른것지 확인하고 if-else 문을 돌려서 확인했다.

또한 String 값에서 0을 int형으로 변환시키면 48 이었기 때문에 나머지 값들은 모두 String 값에서 48을 뺴주었다.

마지막으로 *인 아차상의 경우 count라는 변수를 활용하여 지금까지 숫자가 몇번 나온지를 확인하여 한번 나왔을 경우에는 그 점수에만 2배를 시키도록 예외처리를 하였다.

[실패율]

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

using namespace std;

bool cmp(const pair<float,int>& a , const pair<float, int>& b){
    if(a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int number = stages.size();
    pair<float, int> p;
    vector<pair<float,int>> vec;
    int index;
    float failure;
    int cnt;
    for (int i = 0; i < N; i++) {
        index = i + 1;
        cnt = count(stages.begin(), stages.end(), i + 1);
        if(cnt == 0)
            failure = 0;
        else{
             failure = cnt / (float)number;
            number -= cnt;
        }
        vec.push_back(make_pair(failure,index));
    }

    sort(vec.begin(), vec.end(), cmp);

    for (int i = 0; i < vec.size(); i++) {
         answer.push_back(vec[i].second);
    }

    return answer;
}

해설

Pair 로 실패율과 index번호를 결합한 vector를 생성하였다.

Algorithm 에 있는 Count 를 사용하여 벡터안에 같은 숫자가 몇개있는지 1stage 부터 판별하였다.

또한 count가 0일때는 stage에 도달한 사람이 없다는 것 이므로 그 때는 실패율을 0으로 예외처리해주었다.

Algorithm 에 있는 Sort 를 사용하고 cmp라는 bool형의 함수를 만들어 만약 실패율이 같을 경우는 스테이지가 낮은쪽이 먼저 정렬되도록 만들었다.

문제

예산

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> d, int budget) {
    int max = 0;
    int sum = 0;
    sort(d.begin(), d.end());
    for(int i = 0 ; i < d.size(); i++){
        sum += d[i];
        if(sum <= budget)
            max++;
    }

    return max;
}

해설

첫 번째로 백터들을 Sort 로 정렬시킨 후 하나씩 더해서 합이 budget 의 숫자보다 작거나 같으면 max 변수를 1씩 더해준다

문제의 해석이 중요한 문제이다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다.

라는 말이 예를들어 예산이 9원이면 9원을 남김없이 써야하는것 같지만 그렇지 않다.

예를들어 {1,2,3,4,5} 라는 부서에 예산이 9원이면 1원 2원 3원을 주어서 총 6원을 주어도 상관없다.

하지만 {1,2,3,3,5} 인 부서인 경우에는
1원 2원 3원만 줄 수 없다.

왜냐하면 1원 2원 3원에서 나머지 3원을 더 주면 총 9원 이기 떄문이다.

2016년

#include <string>
#include <vector>

using namespace std;

string solution(int a, int b) {
    string answer;
    int sum = 0;
    for(int i = 1 ; i < a ; i++){
        if(i == 2){
        sum += 29;
    } 
    else if(i == 1 || i==3 || i==5 || i==7 || i== 8 || i == 10 || i==12){
        sum += 31;
    }
    else{
        sum+= 30;
    }
    }
    sum += b;
    switch(sum % 7)
    {
        case 1: answer = "FRI";
            break;
        case 2: answer = "SAT";
            break;
        case 3: answer = "SUN";
            break;
        case 4: answer = "MON";
            break;
        case 5: answer = "TUE";
            break;
        case 6: answer = "WED";
            break;
        case 0: answer = "THU";
            break;
    }

    return answer;
}

해설

1. 윤년이란

• 연수가 4로 나누어 떨어지는 해
• 연수가 100으로 나누어 떨어지는 해
• 연수가 400으로 나누어 떨어지는 해

2016년은 윤년이므로 1년이 총 366 일이다.

2. 해설

일수의 총 합을 구한뒤 % 7로 나머지를 구하여 날짜를 출력한다.