23.02.20. 풀었던 문제들

리트코드 daily challenge - 35. Search Insert Position

binary search(또는 lower bound)를 구현하는 문제. 내 포스팅에 작성되어 있다.

 

프로그래머스 lv.2 연속 부분 수열 합의 개수

환형 array라는 것에 착안해서 크기를 2배로 늘리면 쉽게 풀리는 3중for문 문제. 또는 조금 최적화해서 2중 for문으로 풀 수 있다.

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

int solution(vector<int> elements) {
    int size = elements.size();
    elements.insert(elements.end(), elements.begin(), elements.end());

    set<int> s;

    // 시작 index
    for(int startidx = 0; startidx < size; startidx++){
        int sum = 0;
        // 길이가 1인 것부터 size까지 배열의 합
        for(int idx = startidx; idx < size + startidx; idx++){
            sum += elements[idx];
            s.insert(sum);
        }
    }

    return s.size();
}

 

프로그래머스 lv.1 기사단원의 무기

 이게 lv.1..? input이 10만이라 nlogn보다 짧은 시간으로 풀어야한다. 즉 2중for문으로 풀면 안되고 소수의 특성을 이용해서 풀어야 하는 문제라는 것이다.

 에라토스테네스의 체와 같은 알고리즘으로 풀되, x의 모든 배수는 x가 약수이므로 약수 개수를 ++해주면 된다.

#include <string>
#include <vector>
#include <set>
#include <iostream>
#include <cmath>

using namespace std;

int solution(int number, int limit, int power) {
    vector<int> count(number+1, 1); // 모든 수의 공통약수 : 1
    
    // 에라토스테네스의 체 변형
    for(int i = 2; i<=number; i++){
        for(int j = i; j<=number; j+=i){
            count[j]++;
        }
    }
    
    int answer = 0;
    for(int i = 1; i<=number; i++){
        answer += count[i] > limit ? power : count[i];
    }
    return answer;
}

 

프로그래머스 lv.2 할인 행사

 크기가 고정되어 있는 sliding window 문제이다. sliding window 문제들이 그렇지만 window를 sliding할 때 indexing을 주의해야 한다. 나도 i + windowSize - 1을 해야 하는데 i + windowSize를 해서 디버깅을 했다. 주의하자.

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

using namespace std;

int isMatch(map<string, int>&m){
    for(auto& [key, value] : m){
        if(value > 0) return 0;
    }
    return 1;
}

int solution(vector<string> want, vector<int> number, vector<string> discount) {
    map<string, int> m;
    
    int wantSize = want.size();
    for(int i = 0; i<wantSize; i++){
        m[want[i]] = number[i];
    }   
    
    int answer = 0;
    int windowSize = 10;
    
    for(int i = 0; i<windowSize; i++){
        if(m.find(discount[i]) != m.end()){
            m[discount[i]]--;
        }
    }
    answer += isMatch(m);
    
    int discountSize = discount.size();
    for(int i = 1; i<discountSize - windowSize + 1; i++){
        // slide 이동, 첫 부분 뺌
        if(m.find(discount[i-1]) != m.end()){
            m[discount[i-1]]++;
        }
        // 끝 부분 추가함
        if(m.find(discount[i + windowSize - 1]) != m.end()){
            m[discount[i + windowSize - 1]]--;
        }
        answer += isMatch(m);
    }
    
    return answer;
}

 

프로그래머스 lv.1 옹알이 (2)

 귀찮고 귀찮은 string 처리 문제. 좀 많이 복잡하게 푼 것 같다. 모범 답안을 보니 너무 깔끔했다...

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<string> babbling) {
    vector<string> ables = {"aya", "ye", "woo", "ma"};
    
    int answer = 0;
    
    for(string str : babbling){
        /*
        I'll replace all [ables] word to number
        */
        string replacedString = "";
        for(int i = 0; i<str.length(); i++){
            bool isReplaced = false;
            for(int ableIdx = 0; ableIdx < ables.size(); ableIdx++){
                if(str.substr(i, ables[ableIdx].length()) == ables[ableIdx]){
                    replacedString += to_string(ableIdx);   
                    isReplaced = true;
                    i += ables[ableIdx].length() - 1; // mistake : for문이기 떄문에 -1 해주어야 함
                    break;
                }
            }
            if(!isReplaced) replacedString += str[i];
        }

        bool canPronounce = true;
        for(int i = 0; i< replacedString.size(); i++){
            if('a' <= replacedString[i] && replacedString[i] <= 'z'){
                canPronounce = false;
                break;
            }
        }
        
        for(int i = 1; i< replacedString.size(); i++){
            if(replacedString[i-1] == replacedString[i]){
                canPronounce = false;
                break;
            }
        }
        if(canPronounce) answer++;
    }
    
    return answer;
}

 

 아래는 모범 답안. [직전에 나온 단어 type]을 비교한다는 점, substr로 해당 문자열이 있는지 검사한다는 점은 똑같은데... 코드를 이렇게까지 줄일 수 있다.

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<string> babbling) {
    int answer = 0;
    
    
    for(string str : babbling){
        int prevWordIdx = -1;
        bool canPronounce = true;
        for(int i = 0; i<str.length(); i++){
            if(str.substr(i, 3) == "aya" && prevWordIdx != 1) {prevWordIdx = 1; i+= 2;}
            else if(str.substr(i, 2) == "ye" && prevWordIdx != 2) {prevWordIdx = 2; i+= 1;}
            else if(str.substr(i, 3) == "woo" && prevWordIdx != 3) {prevWordIdx = 3; i+= 2;}
            else if(str.substr(i, 2) == "ma" && prevWordIdx != 4) {prevWordIdx = 4; i+= 1;}
            else canPronounce = false;
        }
        if(canPronounce) answer++;
    }
    
    return answer;
}

 

프로그래머스 lv.2 롤케이크 자르기

 sliding window? two pointer? 아무튼 map을 이용해서 [토핑 종류, 해당 토핑 개수]를 저장하고, 왼쪽에서 오른쪽으로 pointer를 움직이면서 [왼쪽의 토핑 개수]와 [오른쪽의 토핑 개수]가 같아질 때를 찾으면 된다.

 

프로그래머스 lv.1 카드 뭉치

 merge sort에서 merge하는 단계처럼, array 2개로 결과 array를 만들 수 있는지 검사하는 문제. 그냥 for loop 써서 직관으로 풀린다.

 

프로그래머스 lv.2 뒤에 있는 큰 수 찾기

 백준의 오큰수와 동일한 문제. stack을 이용하고, stack이 비었을 때 예외처리를 해주어야 한다.

 

프로그래머스 lv.2 숫자 변환하기

 백준의 bottom-up dp를 풀어봤다면 쉽게 풀 수 있는 문제.