22.08.13. 풀었던 문제들

Codeforces #805 Div. 3 Upsolving

G번 빼고 했다.(아직 배우지 않은 lca)

 

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

1번

 두 수에서 각 숫자의 개수를 xcnt, ycnt에 기록한 후 xcnt[i], ycnt[i] 중 작은 값 만큼 정답에 붙여넣으면 된다. 0은 special case기 때문에 따로 예외처리 해 주면 된다.

#include <string>
#include <vector>
 
using namespace std;
 
string solution(string X, string Y) {
    vector<int> xcnt(10, 0), ycnt(10, 0);
    for(char c : X){
        xcnt[c-'0']++;
    }
    for(char c : Y){
        ycnt[c-'0']++;
    }
    string answer = "";
    for(int i = 9; i>=0; i--){
        int value = min(xcnt[i], ycnt[i]);
        if(i == 0 && answer == ""){
            if(value >= 1) answer += to_string(0);
        }
        else{
            for(int v = 0; v<value; v++){
                answer += to_string(i);
            }
        }
    }
    return answer == "" ? "-1" : answer;
}

 

2번

 sliding window로 쉽게 풀 수 있는 문제. string의 비교에 O(10)만큼 걸릴 것이라 예측했기 때문에 string 비교 대신 mapper를 사용해서 만들었다. sliding window의 size는 10이다.

#include <string>
#include <map>
#include <vector>
 
using namespace std;
 
bool allsale(vector<int>&number, vector<int>&want_numbers){
    for(int i = 0; i<number.size(); i++){
        if(number[i] <= want_numbers[i]) continue;
        else return false;
    }
    return true;
}
 
int solution(vector<string> want, vector<int> number, vector<string> discount) {
    vector<int> want_numbers(number.size(), 0); // want_number[i] : idx에 해당하는 제품 재고
    map<string, int> m; // m[str] : string에 해당하는 제품의 idx
    for(int i = 0; i<want.size(); i++){
        m[want[i]] = i;
    }
 
    // two-pointer 초기값 설정
    for(int i = 0; i<10; i++){
        if(m.find(discount[i]) == m.end()) continue;
        want_numbers[m[discount[i]]]++;
    }
 
    int answer = 0;
    if(allsale(number, want_numbers)) answer++;
    for(int i = 10; i<discount.size(); i++){
        if(m.find(discount[i-10]) != m.end()){ // 10일 전 것은 현재 장바구니에서 뺌
            want_numbers[m[discount[i-10]]]--;
        }
        if(m.find(discount[i]) != m.end()){ // 추가할 것 추가
            want_numbers[m[discount[i]]]++;
        }
        if(allsale(number, want_numbers)) answer++; // 조건 맞으면 ++
    }
 
    return answer;
}

 

3번

 까다로웠던 simulation 문제. order의 index와 현재 컨베이어 벨트 제일 앞에 나와 있는 target 이렇게 2개의 index를 사용할 것이다.

• 만약 target(현재 제일 앞에 있는 번호)와 order[i]가 동일하다면 바로 넣을 수 있다. i++, target++을 해 준다.
• 만약 target < orders[i]라면 target보다 더 큰 것을 올려야 하므로, target이 orders[i]가 될 때 까지 stack에 target을 넣고, target++을 해 준다.
• 만약 target > orders[i]라면 target보다 더 작은 것을 올려야 하므로, sub container belt, stack을 봐야 한다. 그런데 여기서, stack이 비었거나 stack의 top이 orders[i]와 다르다면 더 이상 순서를 맞춰줄 수 없다. 바로 종료. 그렇지 않다면 stack pop하고 i++, answer++을 해 준다.

#include <string>
#include <stack>
#include <vector>
 
using namespace std;
 
 
int solution(vector<int> orders) {
    int answer = 0, n = orders.size();
    int target, i;
    stack<int> stk;
    for(target = 1, i = 0; i<orders.size();){
        // target : 현재 제일 앞에 있는 것
        if(target == orders[i]){ // 순서가 맞으면 바로 넣음
            answer++;
            i++;
            target++;
        }
        else if(target < orders[i]){ // target보다 더 큰걸 올려야 하면 sub에 넣음
            while(target <= n && target < orders[i]){
                stk.push(target);
                target++;
            }
        }
		else{ // target보다 더 작은 걸 올려야 하면 stack에서 빼내야 함
			if (!stk.empty() && stk.top() == orders[i])
			{
				stk.pop();
				i++;
				answer++;
			} else{ // stack에서 못 뺀다면, 더 이상 순서를 맞출 수 없음
				break;
			}
		} 
	}
 
    return answer;
}

 

4번

 n by n matrix a, b가 주어졌을 때 a에서 최소의 operation으로 b를 만들 때, n을 구하는 문제. 각 operation은 row를 모두 뒤집거나 col을 모두 뒤집거나 이다.

 그래서 나는 a - b를 diff라는 matrix로 정의하고 [어차피 row-col로 하나 col-row로 하나 결과는 동일하니까] row부터 모두 처리하고, col을 다음으로 처리했다. 그런데 무슨 반례가 있나 보다. 75점 나온다. 근데 무슨 반롄지 모르겠다......

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int n;
 
// vector v의 값을 reverse해서 vector return
vector<int> rev(vector<int> v){
	for(int &i : v){
		i = 1 - i;
	}
	return v;
}
 
// vector a, vector b의 elem이 모두 같으면 true, 다르면 false
bool cmp(vector<int> &a, vector<int>& b){ 
	for(int i = 0; i<a.size(); i++){
		if(a[i] != b[i]) return false;
	}
	return true;
}
 
int solve(vector<vector<int>> diff, vector<int>&standard, vector<int>& rev_standard){
	int answer = 0;
	for(int r = 1;r<n; r++){
		if(cmp(standard, diff[r])) continue; // stan과 같으면 pass
		else if(cmp(rev_standard, diff[r])){ // stan과 다른 경우 - rev_stan과 같으면 뒤집고 ans++
			diff[r] = rev(diff[r]);
			answer++;
		}
		else return -1; // stan과도 다르고 rev_stan과도 다르면 만들 수 없다.
	}
    for(int i : standard) if(i == 1) answer++; // 모든 행이 stan과 같아졌음. stan에 있는 1 숫자만큼 ans++
	return answer;
}
 
int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
	n = beginning.size();
	vector<vector<int>> diff(n, vector<int>(n, 0));
	for(int r= 0; r<n; r++){
		for(int c= 0 ; c<n; c++){
			if(beginning[r][c] != target[r][c]){
				diff[r][c] = 1; // 다르면 1, 같으면 0
			}
		}
	}
 
	vector<int> standard(diff[0].begin(), diff[0].end()); // 기준 행
	vector<int> rev_standard = rev(standard); // 기준 행 뒤집은 것
   	int a = solve(diff, standard, rev_standard);
	int b = solve(diff, rev_standard, standard) + 1;
    //cout<<a<<' '<<b<<endl;
   
    return min(a, b);
}

 

백준 단계별 25 그래프와 순회

7576 토마토

7569 토마토

16929 뱀과 사다리 게임

2206 벽 부수고 이동하기

벽을 부순 상태, 벽을 부수지 않은 상태 2가지 상태에 대한 state가 필요하기 때문에 dist를 3차원 배열로 선언한다.

그러면 BFS 할 때, 조건은 다음과 같이 된다. 이런 state에 따른 BFS/DFS 문제는 프로그래머스에서 풀었었다.

dist[r][c][0]은 벽을 부수지 않은 상태에서 [0, 0]에서 [r, c]까지 최단거리

dist[r][c][1]은 벽을 부순 상태에서 [0, 0]에서 [r, c]까지 이동한 최단거리

로 두고 풀면 쉽게 풀릴 것이다.

• 지금까지 벽을 부순 경우
  • 다음 칸이 무조건 벽이 없어야 함
• 지금까지 벽을 부수지 않은 경우
  • 다음 칸이 벽인 경우 해당 칸으로 넘어가고, didBroke를 true로 바꿈, BFS 계속 함
  • 다음 칸이 벽이 아닌 경우 그대로 넘어 감

 

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
 
void solve(){
	int INF = 100000000;
	int N, M; cin>>N>>M;
	vector<string> grid(N);
	vector<vector<vector<int>>> dist(N, vector<vector<int>>(M, vector<int>(2, INF)));
	dist[0][0][0] = dist[0][0][1] = 1;
	// dist[r][c][0] : dist from [0, 0] to [r, c], 벽 부수지 않음
	// dist[r][c][1] : dist from [0, 0] to [r, c], 벽 부숨
	for(string &str : grid) cin>>str;
 
	queue<pair<pii, bool>> q; q.push({{0, 0}, false}); // .first : 좌표. second :부순 여부
	while(!q.empty()){
		pii cur = q.front().first;
		bool didBroke = q.front().second;
		int cr = cur.first;
		int cc = cur.second;
		q.pop();
		for(int d = 0; d<4; d++){
			int nr = cr + dr[d];
			int nc = cc + dc[d];
			if(0 <= nr && nr < N && 0 <= nc && nc < M){
				if(grid[nr][nc] == '0' && dist[nr][nc][didBroke] == INF){
					q.push({{nr, nc}, didBroke}); // 안부수고 진행
					dist[nr][nc][didBroke] = dist[cr][cc][didBroke] + 1;
				}
				if(!didBroke && grid[nr][nc] == '1' && dist[nr][nc][1] == INF){
					q.push({{nr, nc}, true}); // 안부셨다면 부실 수 있음
					dist[nr][nc][1] = dist[cr][cc][didBroke] + 1;
				}
			}
		}
	}
	int answer = min(dist[N-1][M-1][0], dist[N-1][M-1][1]);
	answer = (answer == INF ? -1 : answer);
	cout<<answer;
}

1707 이분 그래프