씅의 기록하는 개발노트

문제 출처

https://programmers.co.kr/learn/courses/30/lessons/12987

문제 풀이

정렬한뒤 풀이하는게 핵심이다. A, B벡터 모두 가장 큰수부터 비교를 해 B가 더 크다면 승점 확보와 index를 감소시킨다.

A의 가장 큰수 vs B의 가장 큰수가 붙었을때 A가 더 크다면 B에서 이길 수 있는 수가 없으므로 A의 index를 하나 감소시켜 재 비교해주면 된다.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%88%AB%EC%9E%90%20%EA%B2%8C%EC%9E%84.cpp

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int aIdx = A.size()-1;
    int bIdx = B.size()-1;
    while (1) {
        if (aIdx < 0) break;
        if (A[aIdx] < B[bIdx]) {
            bIdx--;
            answer++;
        }
        aIdx--;
    }
    
    return answer;
}

문제 출처

programmers.co.kr/learn/courses/30/lessons/60059

문제 풀이

전체탐색과 2차원 배열을 다룰 수 있는지 묻는 문제 입니다.

자물쇠에 키를 대조할때 겹치면 안되나 키가 자물쇠의 범위를 벗어나도 된다는 것이 핵심입니다. 
즉 키의 (0,0) 부분이 map의 (0,0) ~ (n+m-1, n+m-1)까지 이동하며 탐색하면 됩니다.

아래 그림은 자물쇠와 키의 예시입니다.

map을 확장한뒤 map[n+2m-2][n+2m-2]의 정 중앙에 자물쇠를 두어 겹치게 한다면 전체탐색이 가능합니다.

즉 탐색을 좌측상단 열쇠위치에서 시작하고 마지막 탐색은 우측하단 열쇠 위치까지 진행하여 열쇠와 자물쇠가 적합한지 판단하는 문제입니다.

탐색한 뒤 키와 자물쇠가 중복되지 않은 것을 판별하기 위해 map에서 자물쇠 위치를 탐색할때 배열에 있는 값이 1이 아니면 false를 return합니다.

소스 코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80%20%EC%97%B4%EC%87%A0.cpp

#include <string>
#include <vector>
using namespace std;

void rotateKey(vector<vector<int>> &key) {
    int keySize = key.size();
    vector<vector<int>> temp = key;
    for (int y=0; y<keySize; y++) {
        for (int x=0; x<keySize; x++) {
            key[y][x] = temp[keySize-x-1][y];
        }
    }
}

bool isUnlock(int sy, int sx, vector<vector<int>> key, vector<vector<int>> map) {
    int keySize = key.size();
    int mapSize = map.size();
    
    for (int y=sy; y<sy+keySize; y++) {
        for (int x=sx; x<sx+keySize; x++) {
            map[y][x] += key[y-sy][x-sx];
        }
    }

    for (int y=keySize-1; y<mapSize-keySize+1; y++) {
        for (int x=keySize-1; x<mapSize-keySize+1; x++) {
            if (map[y][x] == 1) continue;
            return false;
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int keySize = key.size();  
    int lockSize = lock.size(); 
    int mapSize = lockSize + (keySize-1)*2; 

    // 작업할 map생성
    vector<vector<int>> map(mapSize, vector<int>(mapSize, 0));
    for (int y=0; y<lockSize; y++) {
        for (int x=0; x<lockSize; x++) {
            map[y+keySize-1][x+keySize-1] = lock[y][x];
        }
    }
    
    // 90도씩 4번 회전
    for (int i=0; i<4; i++) {
        // key를 전체 map에 대해 탐색
        for (int y=0; y<mapSize-keySize+1; y++) {
            for (int x=0; x<mapSize-keySize+1; x++) {
                if (isUnlock(y, x, key, map)) {
                    return true;
                }
            }
        }
        rotateKey(key);
    }
    
    return false;
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/60058

문제풀이

문제에서 주어진대로 구현해주면 된다. 올바른 괄호를 체크할때 스택을 사용했다. 딱히 어려운 부분은 없고 문제를 정확히 읽고 구현해주면 되는 문제인데 u를 구할때 약간 생각이 필요했다. 문자열을 탐색하면서 '('의 개수와 ')'의 개수가 같아질 때가 u이고 나머지 문자열이 v가 된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp

#include <string>
#include <vector>
#include <stack>
using namespace std;

// 올바른 괄호 문자열 체크
bool isCorrectBracket(string bracket) {
    stack<char> st;
    for (int i=0; i<bracket.size(); i++) {
        if (bracket[i] == '(') {
            st.push(bracket[i]);
        } else if (bracket[i] == ')') {
            if (st.empty()) {
                return false;
            } else {
                st.pop();
            }
        }
    }
    
    if (st.empty()) return true;
    else return false;
}

// 재귀
string go(string p) {
    // 1번
    if (p == "") {
        return p;
    }
    
    // 2번
    string u = "", v = "";
    int left = 0, right = 0;
    for (int i=0; i<p.size(); i++) {
        if (p[i] == '(') left++;
        else if (p[i] == ')') right++;
        if (left == right) {
            u = p.substr(0, i + 1);
            v = p.substr(i + 1);
            break;
        }
    }
    
    // 3번
    if (isCorrectBracket(u)) {
        return u + go(v);
    } else {    // 4번
        string ret = "(" + go(v) + ")";
        u = u.substr(1, u.size() - 2);
        for (int i=0; i<u.size(); i++) {
            if (u[i] == '(') u[i] = ')';
            else if (u[i] == ')') u[i] = '(';
        }
        return ret + u;
    }
}

string solution(string p) {
    string answer = "";
    if (isCorrectBracket(p)) return p;
    answer = go(p);
    return answer;
}