22.08.14. 풀었던 문제들

프로그래머스 코딩테스트 실전 대비 모의고사 2회

1번

 3중포문으로 간단하게 풀면 되는 문제

int solution(vector<int> number) {
    int answer = 0;

    int n = number.size();
    for(int i = 0; i<n; i++){
        for(int j = i + 1; j<n; j++){
            for(int k = j + 1; k<n; k++){
                if(number[i] + number[j] + number[k] == 0) answer++;
            }
        }
    }

    return answer;
}

 

2번

 map으로 숫자 세면 되는 문제. 가운데 기준으로 2개의 window를 두고, middle point를 하나씩 오른쪽으로 옮겨가면서 right map에 있는 leftmost toppoing을 left map으로 옮기고, map의 크기 비교를 하면 된다.

int solution(vector<int> toppings) {
    map<int, int> left, right; // left : 왼쪽 조각의 토핑, right : 오른쪽 조각의 토핑
    // 초기 상태 : 안 자른 상태, right에 다 넣음
    for(int topping : toppings){
        if(right.find(topping) == right.end()){
            right[topping] = 1;
        } else{
            right[topping]++;
        }
    }

    int answer = 0;
    // middle pointer를 옮겨가면서 right 중 leftmost topping을 1개씩 left로 옮길 것.
    for(int topping : toppings){
		if (right[topping] == 1){ // right 중 leftmost 삭제
			right.erase(topping);
		}
		else{
			right[topping]--;
		}

		if (left.find(topping) == left.end()){ // 그것을 left에 삽입
			left[topping] = 1;
		}
		else{
			left[topping]++;
		}

		if(left.size() == right.size()) answer++;
    }

    return answer;
}

 

3번

 문제는 조금 꼬아져서 나와 있지만, destination으로부터 dijkstra를 취하면 되는 문제.

// weight가 작은 것을 pq의 탑으로
struct cmp{
    bool operator()(pii &a, pii &b){
        if(a.second == b.second) return a.first < b.first;
        else return a.second > b.second;
    }
};

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<vector<int>> edges(n+1); // edges[i] : vertex i의 edge들
    for(vector<int>& edge : roads){
        int from = edge[0], to = edge[1];
        edges[from].push_back(to);
        edges[to].push_back(from);
    }

    int INF = 99999999;
    vector<int> dist(n+1, INF);
    dist[destination] = 0;

    priority_queue<pii, vector<pii>, cmp> pq; // .first : vertex, .second : weight
    pq.push({destination, 0});
    while(!pq.empty()){
        pii cur = pq.top(); pq.pop();
        for(int adj : edges[cur.first]){
            if(dist[adj] > dist[cur.first] + 1){
                dist[adj] = dist[cur.first] + 1;
                pq.push({adj, dist[adj]});
            }
        }
    }

    vector<int> answer;
    for(int source : sources){
        answer.push_back(dist[source] == INF ? -1 : dist[source]);
    }
    return answer;
}

// destination으로부터 모든 점까지 dijkstra 쓰면 될 것 같은데?