인프런 커뮤니티 질문&답변

안녕하세요 개발님 ㅎㅎ

코드 깔끔한데요?

잘 짜셨습니다. ㅎㅎ

먼저 4ms의 수준의 속도차이는 사실 미묘한 거라 신경을 쓰지 않아도 됩니다만

제 생각에는 unordered_set으로 효율적으로 하려고 했지만 사실 범위자체가 1 ~ 100까지 작은 범위라 이범위를 효율적으로 하려고 했지만 unordered_set이라는 자료구조를 생성하는 비용이 오히려 더 든 것 같습니다.

나머지 부분은 다 좋습니다.

제가 실제로 개발님 코드 기반으로 함수호출도 없애보고 unordered_set은 최악의 시간복잡도가 O(N)이기 때문에 O(logN) 인 set으로도 바꿔보고 한 코드를 첨부합니다. (이렇게 해도 20ms입니다. ㅎㅎ)

#include <bits/stdc++.h>

using namespace std;

const int maxDistance = 100;
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

int inputDistance;
int field[maxDistance][maxDistance];
bool visited[maxDistance][maxDistance];
int maxHeight = 0;
set<int> uniqueHeights;

void CalcSafeCount(int x, int y, int waterHeight)
{
    visited[y][x] = true;

    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0)
            continue;

        if (nx >= inputDistance || ny >= inputDistance)
            continue;

        if (visited[ny][nx])
            continue;

        if (field[ny][nx] <= waterHeight)
            continue;

        CalcSafeCount(nx, ny, waterHeight);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> inputDistance;

    for (int y = 0; y < inputDistance; ++y)
    {
        for (int x = 0; x < inputDistance; ++x)
        {
            int height;
            cin >> height;

            field[y][x] = height;
            uniqueHeights.insert(height);
            maxHeight = max(maxHeight, height);
        }
    }

    int maxSafeCount = 1;
    for (int waterHeight : uniqueHeights)
    {
        if (waterHeight == maxHeight)
            continue;

        fill(&visited[0][0], &visited[0][0] + maxDistance * maxDistance, false);

        int safeCount = 0;
        for (int y = 0; y < inputDistance; ++y)
        {
            for (int x = 0; x < inputDistance; ++x)
            {
                if (visited[y][x])
                    continue;

                if (field[y][x] <= waterHeight)
                    continue;

                CalcSafeCount(x, y, waterHeight);
                safeCount += 1;
            }
        }

        maxSafeCount = max(maxSafeCount, safeCount);
    }

    cout << maxSafeCount;
    return 0;
}
 

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 개발님, 질문 주셔서 감사합니다.

코드의 실행 시간 차이에 대해 궁금해 하시는데, 각기 다른 접근 방식을 사용했을 때 실행 시간 차이가 발생하는 것은 자연스러운 현상입니다. 우선, 두 가지 방법의 주요 차이점을 하나씩 확인해 볼 필요가 있습니다.

1. unordered_set 사용: unordered_set은 평균적으로 상수 시간 복잡도를 가지지만, 해시 충돌이 발생할 경우 성능이 급격히 저하될 수 있습니다. 이로 인해 특정 테스트 케이스에서는 예상보다 시간이 더 소요될 수 있습니다.

2. 모두 잠기는 경우 제외: maxHeight를 통해 모두 잠기는 경우를 제외하려고 하셨지만, 실제로 코드를 실행하는 시스템에서는 모든 조건을 만족하는지 여부를 실시간으로 검증해야 하고, 이런 경우가 여러 번 발생하면 오히려 계산에 소요되는 시간이 늘어나게 됩니다.

다른 알고리즘이나 자료구조의 미세한 차이가키파이 성능에 큰 영향을 미칠 수 있으니, 다양한 경우의 수에 대해 실행해 보고, 발생할 수 있는 성능 차이를 분석하는 것이 중요합니다.

질문을 해결하는 데 도움이 될 만한 다른 학생의 답변으로는 다음과 같은 사례를 참고하실 수 있습니다:
- 문제를 풀었다고 생각했는데 75%에서 틀립니다. 뭐가 문제일까요 ㅜㅜ

질문의 구체적 사례와 관련된 토론이 이 답변에 이루어졌습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.