Murra Blog

프로그래머스 탑 문제

배열의 끝부터 봅니다. 배열의 끝부터 하나씩 자기보다 왼쪽에 있는 것중에 값이 보다 큰 곳의 인덱스를 저장하면 됩니다. 만약 자기보다 큰게 없다면 0을 저장하면 됩니다.

탑.cpp

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    int heights_size = heights.size();
    vector<int> answer(heights_size, 0);

    for(int i=heights_size-1 ; i>=0; --i)
    {
        int iter = i;
        while(iter--) 
        {
            if(heights[iter] > heights[i])
            {
                answer[i] = iter+1;
                break;
            }
        }
    }
    return answer;
}

프로그래머스 문자열 압축 문제

1 ~ i번째의 문자열씩 끊어가면서 모든 문자를 확인한다. 같은 문자열일 경우 반복 횟수(count)를 1씩 증가시키고, 다른 문자열일 경우 여태 반복된 문자열 정보를 추가한 뒤(반복 횟수 + 문자열) 반복 횟수를 1로 초기화한 후 다시 같은 작업을 반복한다.

문자열 압축.cpp

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

int solution(string s) {
    int answer = s.length();
    int len = s.size();

    // i는 부분 문자열의 길이
    // 문자열 길이의 절반까지 반복
    for(int i=1; i <= len / 2; ++i)
    {
        int count = 1; // 반복 횟수, 초기화를 1회로
        string temp_answer = "";
        string pre_sub = s.substr(0, i); // i번째 글자까지

        for(int j=i; j<len; j+=i)
        {
            string now_sub = s.substr(j, i);
            if(pre_sub == now_sub) // 반복되는 경우
            {
                count++;
            }
            else // 반복되지 않을 경우
            {
                if(count == 1)
                {
                    temp_answer = temp_answer + pre_sub;
                }
                else
                {
                    temp_answer = temp_answer + to_string(count) + pre_sub;
                    count = 1; // 다시 반복횟수 1로
                }
                pre_sub = now_sub; // 새로운 문자열이 반복되는지 체크하기 위해
            }
            if(j+i >= len)
            {
                if(count == 1)
                {
                    temp_answer = temp_answer + s.substr(j);
                }
                else
                {
                    temp_answer = temp_answer + to_string(count) + pre_sub + s.substr(j);
                }
                break;
            }
        }
        answer = (answer < temp_answer.length()) ? answer : temp_answer.length();
    }
    return answer;
}

프로그래머스 완주하지 못한 선수 문제

두 가지 방법이 생각났습니다. 하나는 participant, completion을 각각 sort하고 위에서부터 하나씩 비교하는 것과 map을 이용하는 것이였는데 map을 사용하여 풀었습니다.

이름(key)이 들어오면 1씩 증가시키고, 완주했을 경우 1씩 감소시킨 뒤 0이 아닌 값을 출력하는 간단한 방법입니다.

완주하지 못한 선수.cpp

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string, int> m;

    for(auto name : participant)
    {
        m[name]++;
    }

    for(auto name : completion)
    {
        m[name]--;
    }

    for(auto kv : m)
    {
        if(kv.second != 0)
        {
            answer = kv.first;
            break;
        }
    }

    return answer;
}