[프로그래머스] 기능개발 C++

programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

문제를 봤을 때 Queue, Stack, For & While 중 어느 자료 구조를 활용해야 할 지 감을 잡아야 문제를 빨리 풀 수 있을 것 같은데

별로 감이 안온다. 그냥 PseudoCode 쓰면서 결정하는 편인데, 문제만 읽고 자료 구조를 선택할 수 있는 수준이 되고 싶다.

---

풀이 1. (진행상황 + 진행속도 * 일자)를 계산하여 100이 넘었을 때 답 넘기기

vector<int> solution(vector<int> pro, vector<int> speeds) {
    vector<int> answer;
    int days=0;
    int idx = 0;
    
    while(1){
        days++;
        int begin = idx;
        
        while(idx<pro.size() && pro[idx]+speeds[idx]*days>=100)
            idx++;
        
        if(idx>begin) answer.push_back(idx-begin);
        
        if(idx==pro.size()) break;
    }
    return answer;
}

 

(진행상황 + 진행속도 * 일자)를 계산하여 100이 넘었을 때 답을 넘기려고 했다.

이 때 Idx로는 몇 개를 넘겼는지 계산할 수 없어 매 Loop 마다 Begin으로 저장하여 두었다.

---

풀이 2. 하루 지날 때마다 진행 정도를 업데이트

    vector<int> solution(vector<int> progresses, vector<int> speeds) {
        vector<int> answer;
        int days = 0;
        int idx=0;
        int total_idx = progresses.size();
        while(1){
            int count = 0;
            while(idx<progresses.size() && progresses[idx] >= 100){
                count++;
                idx++;
            }
            
            if(count>0) answer.push_back(count);
            if(idx==progresses.size()) break;
            
            days++;
            for(int i=0; i<progresses.size(); ++i){
                progresses[i]+=speeds[i];
            }
            
        }
        return answer;
    }

 

날짜가 하루 지날 때 마다 진행 정도를 업데이트 하는 방법도 있는데 while loop 안에서 for loop를 계속해서 업데이트를 하니 비효율적이다.

---

풀이 3. 남은 개발일을 계산하여 Vector로 만들고, 기준점까지 진행된 일 개수 반환

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {   // day = {7, 3, 9}
        day = (99 - progresses[i]) / speeds[i] + 1; // 1. 필요한 개발 일자 계산 // 2.

        if (answer.empty() || max_day < day) // 1. 비었으니 처음 1을 넣는다
            answer.push_back(1);
        else
            ++answer.back(); // 2.진행된 개발일자 < 필요한 개발일자

        if (max_day < day) // 1. 필요한 개발일자가 크면 업데이트
            max_day = day;
    }

    return answer;
}

 

다른 문제 풀이 대부분이 남은 개발 일자를 먼저 계산하여 vector로 저장해두었다. 문제를 처음 봤을 때 이런 생각을 하기가 쉽지 않을 것 같다..

ㅎㅇㅌ!

진행된 개발일을 기준으로 이전 값들을 검사하기 때문에

진행된 개발일이 업데이트 되었을 때는 1을 넣고

아닐 때는 1을 더하면 된다.

Vector에 들어가 있는 순서대로 일이 진행되기 때문에 위와 같은 논리를 적용할 수 있다.

 

++answer.back()을 처음 접해봤다. 신기함.

 

---

풀이 4. 남은 개발일을 계산하여 Queue에 넣고, 기준점까지 진행된 일 개수 반환

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;


    for(int i=0; i<progresses.size(); i++){
        int day = (99 - progresses[i]) / speeds[i] + 1;
        q.push(day);
    }

    while(!q.empty()) {
        int count = 1;
        int curr = q.front();
        q.pop();

        while(curr >= q.front() && !q.empty()) {
            q.pop();
            count++;
        }

        answer.push_back(count);
    }
    return answer;
}

Queue문제 카테고리에 속해있었는데 생각보다 Queue를 쓰지 않은 사람이 많았다. 나도 Queue를 어떻게 써야할지 전혀 감을 찾지 못했다. Queue를 활용한 코드를 찾아봤다.

 

1. Queue에 필요한 개발일자를 모두 계산하여 넣어준다.

2. 처음 deque한 개발일자가 기준이 된다. loop를 돈다. deque 할 개발일자를 기준과 비교

처음 deque한 개발일자를 기준으로 얼마나 많은 일을 완성할 수 있었는지 세고 정답을 넘긴다.

---

T/X의 나머지가 0이 아닐 경우 나눈 값을 하나 더하는 방법

int는 소수점을 계산하지 않기 때문에 나머지는 버린다. 이 문제에서는 나머지가 생길 경우 나눈 값을 하나 증가시켜야 한다.

따라서 if문을 쓰면 쉽게 해결할 수 있지만 코드 한 줄로 if문을 짧게 줄일 수 있다.

1) if문 사용
day = 100-progresses[i])/speeds[i];
if( (100-progresses[i])%speeds[i] !=0 )
  day++;

2) 고수?
 (99 - progresses[i]) / speeds[i] + 1

T / 3을 예로 들자. T/3의 나머지는 {0,1,2} 이다. 3으로 나누었으로 나머지는 2을 넘을 수 없다.

 

T/3의 나머지가 2일때 하나를 더 세어야한다.

(T-1)/3은 나머지가 1이다 나눈 값은 (T/3)과 동일하다

T/3의 나머지가 1일때 하나를 더 세어야한다.

(T-1)/3은 나머지가 0이다. 나눈 값은 (T/3)과 동일하다

T/3의 나머지가 0일때 하나를 더 세지 않아도 된다.

(T-1)/3은 나머지가 2이다. 나눈 값은 (T/3) 보다 하나 부족하다.

 

따라서 모든 경우에 하나를 더 세어야 조건을 만족한다. (T-1)/3 +1을 하면 항상 옳은 값이 나온다.

 

그리고 이는 3이 아니라 0이 아닌 모든 정수 X에 적용가능하므로

T/X의 값이 나머지가 생길 경우 나눈값 +1을 반환하는 문제를 다음과 같이 치환하여 해결할 수 있다.

 

(T-1)/X + 1

 

일단 이해는 했는데 이게 Time complexity나 Space Complexity를 개선하는 건 아닌 것 같고.

흠.. 이렇게 까지 해야하나 싶다.