22.04.02. 풀었던 문제들

1. 소수 찾기

어떤 숫자의 list(0, 1, 2, 3, ...)이 주어졌을 때

size가 1인 순열

size가 2인 순열

...

size가 list.size()인 순열

을 모두 구하고, 소수인지 판정하면 되었다.

​

​

2. 조이스틱

greedy라고 나와 있지만.. 이 문제가 진짜 greedy인지 나는 모르겠다. 그래서 brute-force로 풀었다.

어떤 문자열이 있으면, 그 문자열의 제일 앞에 있는 문자를 제일 뒤로 보낸다. 이렇게 만들어진 문자열(temp)의 index 0으로 이동해야 하는 거리를 구하고, 그 temp 문자열에서 왼쪽으로 쭉 갈 때, 오른쪽으로 쭉 갈 때 좌/우 이동의 최솟값을 구한다(A가 아닌 idx를 찾으면 된다). 이 두 값의 합이 기존 문자열에서 이동해야 하는 좌우 이동 거리이다.

모든 temp에 대해 위 연산을 수행한다면 brute-force하게 풀 수 있다.

2번 이상 왕복하는 경우는 1번 왕복하는 것보다 비효율적이므로 고려하지 않는다.(temp에서 일직선 이동만 고려하면 된다)

​

예를 들어

BABAAAAABAB 이런 경우를 보자

2 1 4 3 이게 최선일 것임. 답 11, (가로이동 7)

그러니까

모든 temp 문자열 1번씩 순회하면서(길이 20이니 시간 충분) 양쪽으로 방향만 보면 될 것.

ABAAAAABABB 기본 1 + min(10(오른족), 10)

BAAAAABABBA 기본 2 + min(5(왼쪽), 9)

AAAAABABBAB 기본 3 + min(10(오른쪽, 6)

...

이런 식으로 세 갈것임.

​

그러면 더이상 가지 않아도 되는 건 어떻게 아느냐...

temp 문자열에서 오른쪽으로 가는 경우, idx 0 기준으로 봤을 때 A가 아닌 문자열의 오른쪽 끝을 찾으면 되고

temp 문자열에서 왼쪽으로 가는 경우, idx 0 기준 왼쪽으로 가서 A가 아닌 문자열의 끝을 찾으면 될 것임.

int calDist(char input){
    return min(input - 'A', 'Z' - input + 1);
}
 
int solution(string name) {
    if(name == "") return 0;
    int left, right, answer = 2000000000, length = name.length();
    string temp;
    // string 제일 앞에 있는 걸 뒤로 1개씩 밀면서 min value 탐색
    for(int i = 0; i<length; i++){
        temp = name.substr(i, length - i) + name.substr(0, i);
        // temp : 초기 name으로부터 i개의 문자를 뒤로 민 문자열
 
        left = right = 0;
        // left : temp에서 왼쪽으로 이동시켰을 때 마지막까지 이동시키면 되는 idx
        for(int idx = 1; idx < length; idx++){
            if(temp[idx] != 'A'){
                left = idx;
                break;
            }
        }
        left = length - left;
        // right : temp에서 오른쪽으로 이동시켰을 때 마지막까지 이동시키면 되는 idx
        for(int idx = length-1; idx > 0; idx--){
            if(temp[idx] != 'A'){
                right = idx;
                break;
            }
        }
          
        // min(i, length - i); // 초기 name으로부터 i개의 문자를 민 temp까지 최소 이동 횟수
        answer = min(answer, min(i, length-i) + min(left, right));
    }
    
    int differ = 0;
    for(int i = 0; i<length; i++){
        differ += calDist(name[i]);
    }
    
    return answer + differ;
}

 

 

3.다리를 지나는 트럭

이것도 그냥 간단하게 시간을 계속 1씩 더해가면서 조건에 따른 검사를 하는 방법이 있고, 시간을 때때로 skip해가는 방법이 있다. 나는 문제 제한조건에서 bridge_length가 1만, 입력이 1만이라 1만 * 1만 = 1억이니 안 될 것 같아서 후자의 방식을 택했다. (전자도 패스는 한다. 다만 후자가 훨씬 빠르다.)

알고리즘 간단하다. 먼저 시간이 1이 되는 시점에 첫 waiting queue에 있는 트럭을 넣고 시간 ++ 해준다.

이후 passing queue가 빌 때까지

- 만약 passing queue의 제일 앞에 있는 걸 뺄 수 있다면 빼고 현재 다리 위 트럭 무게 합을 계산한다.

- 이후 새로운 트럭을 올릴 수 있다면 올리고, time ++ 해주고 continue 한다.

- 만약 새로운 트럭을 올리지 못한다면 passing queue의 front()에 있는 트럭이 다음에 바로 빠져나가게 시간을 조정한다.

​

이 때 에러가 하나 있었는데. passing_queue가 empty인 상황에서도 front의 값을 읽어오는(메모리 에러) 오류가 있어서 디버깅한다고 시간을 많이 잡아먹었다.

 

#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int size = truck_weights.size();
    queue<pii> passing_queue;
    queue<int> waiting_queue;
    int time = 1, cur_weight = truck_weights[0]; // 1초 딱 시작하자마자 들어가는 걸로.
    passing_queue.push({truck_weights[0], time}); time++;
    for(int i = 1; i<size; i++){
        waiting_queue.push(truck_weights[i]);
    } // trucks[i].first : 트럭 weight, .second : truck이 다리에 진입한 시간.
    
    while(!passing_queue.empty()){
        if(passing_queue.front().second + bridge_length <= time){
            cur_weight -= passing_queue.front().first;
            passing_queue.pop();
        } // 나가야 할 때 빼 줌.
        
        if(!waiting_queue.empty() && cur_weight + waiting_queue.front() <= weight){
            passing_queue.push({waiting_queue.front(), time});
            cur_weight += waiting_queue.front();
            waiting_queue.pop();
            time++;
        } // 더 올릴 수 있으면 올리고, time++ 해줌.
        else {
            if(!passing_queue.empty()){
                time = passing_queue.front().second + bridge_length;    
            }
        } // 더 올리지 못하는 경우는 시간을 skip해버림.
        // 이 때 에러가 하나 있었는데. passing_queue가 empty인 상황에서도 front의 값을 읽어오는(메모리 에러) 오류가 있었음.
    }
    
    return time;
}
 
// 아래 코드보단 조금 효율적으로 바뀜.
// 무조건 시간을 1씩 더해가는 게 아니라 더 이상 올리지 못할때는 시간을 skip해버리기 때문임.
 
/*
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int clock = 0; // 시간초
    int passing_sum = 0; // 다리를 건너는 트럭의 무게 합
    
    queue<int> q;   // 대기 트럭
    int truck_num = truck_weights.size();
    for(int i = 0; i<truck_num; i++){
        q.push(truck_weights[i]);
    }
    
    queue<pair<int, int>> passing_q;  // first는 진입한 clock(clock+bridge_length가 되면 나가야함), second는 그 차의 무게
    
    while(!q.empty()){
        if(!passing_q.empty() && clock == passing_q.front().first + bridge_length){
            passing_sum -= passing_q.front().second;
            passing_q.pop();
        }
        if(q.front() + passing_sum <= weight){
            passing_sum += q.front();
            passing_q.push({clock, q.front()});
            q.pop();
        }
        clock++;
    }
    clock += bridge_length; // q(대기 queue)가 빈 순간 마지막 차가 다리에 올라왔으므로... clock += bridge_length하는 게 답.
    
    return clock;
}*/
 
// (다리를 건너는 트럭)에 있는 시간이 length만큼임.
// 1초마다 다 계산가면 100,000,000 - 1억

 

4.2개 이하로 다른 비트

짝수인 경우 +1을 하면 되고, 홀수인 경우 뒤에서부터 연속되는 1 중 제일 앞의 것을 idx를 찾아 그 값만큼 더해주면 된다. 예전보다 비트 연산자를 사용할 수 있게 되는 것 같다(늘고 있는 듯!!!)

// 2개 이하로 다른 비트
 
vector<long long> solution(vector<long long> numbers) {
    int size = numbers.size();
    vector<ll> answers(size);
    for(int i = 0; i<size; i++){
        if(numbers[i] & 1){
            ll idx = 1;
            while(numbers[i] & idx){
                idx <<= 1;
            } idx >>= 1;
            answers[i] = numbers[i] + idx;
        } else{
            answers[i] = numbers[i] + 1;
        }
    }
    return answers;
}
 
// 짝수 : +1하면 됨
// 홀수 : 
// 뒤에서부터 연속되는 1중 제일 앞의 것 idx을 찾아서
// idx-1와 idx를 바꾸면 된다