[programmers] 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

map이나 array를 이용해 전체에서 각 토핑의 개수를 저장하고,

왼쪽의 인덱스를 1씩 증가시켜 가면서

왼쪽과 오른쪽의 가짓수가 같아질 때 answer++ 해준다.

 

---------------------------------------------------풀이----------------------------------------------------

 

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

using namespace std;

int right_nums[10'001] = {0, };
int left_nums[10'001] = {0, };

int get_total_nums(vector<int> topping){
    int n = 0;
    for(int i = 0; i < topping.size(); i++){
        if(right_nums[topping[i]] == 0){
            n++;
        }
        right_nums[topping[i]]++;
    }
    return n;
}

// 롤케이크를 양쪽에 동일한 가짓수의 토핑이 올라가도록 나누는 방법의 수=?
int solution(vector<int> topping) {
    int answer = 0;
    int cut = -1;    // 왼쪽이 가지는 가장 큰 인덱스
    int left_num = 0;   // 왼쪽의 가짓수
    int right_num = get_total_nums(topping);  // 오른쪽의 가짓수
    
    // 왼쪽을 늘려가며 양쪽 가짓수를 비교.
    while(cut < (int)topping.size() && left_num <= right_num){
        cut++;  // 왼쪽에 하나 더 포함시킴.
        // 왼쪽에 새로 포함되는 가짓수이면 왼쪽 가짓수 증가
        if(left_nums[topping[cut]] == 0){
            left_num++;
        }
        left_nums[topping[cut]]++;
        // 오른쪽에서 제외
        right_nums[topping[cut]]--;
        // 오른쪽에서 이 가짓수가 아예 포함되지 않으면 오른쪽 가짓수 감소
        if(right_nums[topping[cut]] == 0){
            right_num--;
        }
        
        // 두 가짓수가 같으면 answer 증가
        if(left_num == right_num){
            answer++;
        }
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

while문 안으로 들어가지 않는 현상이 발견되었다.

이상해서 모든 값을 찍어봤다.

cut의 값은 -1이고 topping.size()의 값은 8인데, 조건이 cut < topping.size()인 while문 안으로 들어가질 않는다.

그래서 각 조건을 true/false로 찍어보니, cut < topping.size()가 false라고 한다...

vector size()를 (int)로 타입캐스팅 해주니 해결되었다.

이상해서 typeid로 타입을 출력해보니, cut은 int이지만 topping.size()는 unsigned long이었다.

cut이 음수라서 발생한 문제인가..?싶어

cut을 0으로 두고 cut < topping.size()를 출력해보니 정상적으로 1(true)가 뜬다.

 

음수와 함께 비교하며 vector.size()를 사용할 경우에는 int로 타입변환하여 사용하는 것이 안전할 것 같다!!**주의하자!