하반기 공채 대비 실전 모의고사 1회

1번. 팰린드롬

n이상 m이하 숫자들에 대해서 팰린드롬 수의 개수를 구하는 문제다.

n<=m<=500000 이고 단순하게 팰린드롬의 길이를 구하는 시간복잡도는 O(length_m/2)이므로 최대 O(1500000)이면 해결된다.

int p[6] = { 1,10,100,1000,10000,100000 };
 
int solution(int n, int m) {
    int ans = 0;
    while (n <= m) {
        int len = 0, temp = n, flag = true;
        while (temp) 
            len++, temp /= 10;
        for (int i = 0; i < len / 2; ++i)
            if ((n / p[i]) % 10 != (n / p[len - 1 - i]) % 10) {
                flag = false;
                break;
            }
        ans += flag;
    }
    return ans;
}

2번. 배상비용 최소화

선박 m개에 대해서 남은 작업량이 주어지고 작업할 수 있는 양 n이 주어지며 배상비용은 작업량의 제곱일 때

이 작업량을 최소화하고 그 값을 출력하는 문제다.

배상비용이 작업량의 제곱이므로 직관적으로 작업량이 더 큰 작업을 조금이라도 해결하는게 유리하다는 걸 알 수 있다.

방법 1.

작업량의 최대값은 1000이므로 작업량을 c[i]에 카운팅한 다음 1000부터 내려오면서 n값과 비교한 후 감소시켜나가면 된다.

방법 2.

마찬가지로 카운팅한 후 1000부터 내려오면서 누적합으로 계산해나가다가 n을 넘어가는 순간을 기점으로 계산하면 된다.

사실 방법 1과 동일하다.

소스코드는 방법 1이다.

int solution(int n, vector<int> arr) {
    int ans = 0;
    int c[1001] = { 0, };
    for (auto i : arr)
        c[i]++;
    for (int i = 1000; i; --i) {
        if (n > c[i]) {
            n -= c[i];
            c[i - 1] += c[i];
            c[i] = 0;
        }
        else {
            c[i - 1] += n;
            c[i] -= n;
            break;
        }
    }
    for (int i = 1; i <= 1000; ++i)
        ans += c[i] * i*i;
    return ans;
}

3번. 버스여행

1~n까지의 정류장에서 갈 수 있는지 여부를 인접행렬 형태로 줄 때 그래프를 1번 이상 타고 갔을 때

다른 노드로 갈 수 있는지 여부를 모두 표시하고 그걸 출력하는 문제다.

1번 이상 타고 들어가야하기 때문에 자기 자신으로 갈 수 있는지는 initial state에서는 0으로 표시해야 한다.

방법 1.

bfs

방법 2.

문제의 조건을 보면 1번에서 2번 정류장으로 갈 수 있을 경우 1번에서는 2번 정류장 및 2번 정류장에서 갈 수 있는 모든 곳을 갈 수 있다.

따라서 갱신이 최대 n번 걸리므로 3중 for문으로 구할 수 있다.

소스코드는 방법 1이다.

vector<vector<int>> solution(int n, vector<vector<int>> arr) {
    // pair<root, from>
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) q.push({ i,i });
    while (q.size()) {
        int from = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < n; ++i) {
            if (arr[from][i] || !arr[x][i]) continue;
            arr[from][i] = 1;
            q.push({ from,i });
        }
    }
    return arr;
}