JArchive 프로그래밍 일기

문제

징검다리 건너기 프로그래머스 level3

리뷰

완전 탐색으로 푸니까 정확도100점, 효율성0점이 나왔다.

1씩 돌의 숫자를 감소시키다보면, 돌 최대 개수가 20만개니까 시간초과가 날 수 밖에 없다. 어려웠다..

다른 분들 풀이를 보니 이분탐색이라는 힌트가 있었다.

다리 건너는 사람 수를 돌에 써있는 숫자의 최소값과 최대값을 가지고 탐색하는 것이다.

// 다리를 건너는 사람 수를 탐색 
int front = 1;
int back = *max_element(stones.begin(), stones.end()); // 범위 내의 최대값 #include <algorithm> 

// 이분탐색 
while (front <= back) {

    int mid = (front + back) / 2;

    if (limit_check(stones, mid, k)) {
        back = mid - 1;
    }
    else {
        front = mid + 1;
    }
}

limit_check()

모든 돌을 순회하면서 mid 숫자를 빼본다.

limit가 충족된다면, true를 리턴한다.

// 연속적으로 0 이 limit개 만큼 있는지 참/거짓 확인한다. 

bool limit_check(vector<int> s, int mid, int limit) {

    int cnt = 0; // 연속으로 0 이 있는 개수

    for (auto i : s) { // 돌의 숫자에서 mid를 뺀다 

        if (i - mid <= 0) {
            cnt++;
            if (cnt == limit) // mid 명이 건널 수 있다고 판단. 
                return true;
        }
        else {
            cnt = 0;
        }
    }
    return false;
}

정답 뜬 코드

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

// 연속적으로 0 이 limit개 만큼 있는지 참/거짓 확인 
bool limit_check(vector<int> s, int mid, int limit) {
    int cnt = 0; // 연속으로 0 이 있는 개수

    for (auto i : s) { // 돌에서 mid를 뺀다 

        if (i - mid <= 0) {
            cnt++;
            if (cnt == limit)
                return true;
        }
        else {
            cnt = 0;
        }
    }
    return false;
}

int solution(vector<int> stones, int k) {

    // 다리를 건너는 사람 수를 탐색 
    int front = 1;
    int back = *max_element(stones.begin(), stones.end()); // 최대값 

    // 이분탐색 
    while (front <= back) {

        int mid = (front + back) / 2;

        if (limit_check(stones, mid, k)) { // mid 숫자로 limit가 충족된다면, 
            back = mid - 1; // 숫자를 줄여본다. 
        }
        else {
            front = mid + 1;
        }
    }
    return front;
}

코드 [ 효율성 0점 정확도 100점 완전탐색 ]

이렇게 짜지 말아야지 하는 마음으로 기록해둔다.

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

int solution(vector<int> stones, int k) {

    int answer = 0; // 사람 수 
    bool flag = true;

    while (flag) {

        int limit_cnt = 0;
        // 0 이 연속되는지 확인 
        for (auto it = stones.begin(); it != stones.end(); ++it)
        {
            if (*it == 0) {
                limit_cnt++;
                if (limit_cnt >= k) return answer; // 제한 숫자 초과 시 종료 
            }
            else {
                limit_cnt = 0;
            }
        }

        // 1 감소 
        for (auto it = stones.begin(); it != stones.end(); ++it)
        {
            if(*it > 0) *it = *it - 1;
        }

        if (limit_cnt >= k) flag = false;
        else {
            answer++;
        }
    }

    return answer;
}