경우없는 개발 블로그

https://school.programmers.co.kr/learn/courses/30/lessons/81303

#문제 간단 정리

각 삭제된 상태를 기록하고 인덱스 조회하는 문제

#문제 해결 방법

가장 쉽게 생각할만 한 것은

삭제됫는지 안 삭제됫는지 표기하기 위해서

배열로 표시하는 것이다.

이전에 삭제된 항목은 스택에 기록해두는것.

그런데 이렇게 풀게되면 삭제된 항목을 넘어서 그 다음항목을 검색해야 되기 때문에

효율성 테스트에서 실패가 뜨게 된다.

때문에 삭제된 항목을 건너 뛸 수 있게

다른 자료구조를 사용해야 되는데

연결 리스트를 사용하면 된다.

나는 배열로 풀엇다가 

틀려서 연결리스트로 제출했다

#전체 코드

배열 코드 (실패)

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

 
vector<int> stack;
vector<bool> check;

string solution(int n, int k, vector<string> cmd) {

    check.assign(n, false);
    
    int cur = k;
    
    for(string s : cmd){
        
        char input1 = s[0];
        int input2 = 0;
        if(input1 == 'U' || input1 == 'D')  input2 = stoi(s.substr(2));

        
        if(input1 == 'U'){
            int count = 0;
            while(count != input2){
                if(check[--cur] == false){
                    count++;
                }
            }
        }
        else if(input1 == 'D'){
            int count = 0;
            while(count != input2){
                if(check[++cur] == false){
                    count++;
                }
            }
        }
        else if(input1 == 'C'){
            check[cur] = true;
            stack.push_back(cur);
            
            int temp = cur;
            bool found = false;
            while(temp < n - 1){
                temp++;
                if(!check[temp]){
                    cur = temp;
                    found = true;
                    break;
                }
            }
            if(!found){
                temp = cur;
                while(temp >= 0){
                    temp--;
                    if(!check[temp]){
                        cur = temp;
                        break;
                    }
                }
            }
        }if(input1 == 'Z'){
            check[stack.back()] = false;
            stack.pop_back();
        }
        
    }
    
    
    string answer(n, 'O');
    for (int i = 0; i < n; ++i) {
        if (check[i]) {
            answer[i] = 'X';
        }
    }

    return answer;
}

연결리스트 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

string solution(int n, int k, vector<string> cmd) {
    vector<int> prev(n), next(n);
    stack<int> removed;
    
    // 초기 링크드 리스트 설정
    for (int i = 0; i < n; ++i) {
        prev[i] = i - 1;
        next[i] = i + 1;
    }
    next[n - 1] = -1;

    int cur = k;
    
    for (const string& s : cmd) {
        char command = s[0];
        int value = 0;
        if (s.size() > 1) value = stoi(s.substr(2));
        
        if (command == 'U') {
            while (value--) {
                cur = prev[cur];
            }
        } else if (command == 'D') {
            while (value--) {
                cur = next[cur];
            }
        } else if (command == 'C') {
            removed.push(cur);
            if (prev[cur] != -1) next[prev[cur]] = next[cur];
            if (next[cur] != -1) prev[next[cur]] = prev[cur];
            
            cur = (next[cur] != -1) ? next[cur] : prev[cur];
        } else if (command == 'Z') {
            int restore = removed.top();
            removed.pop();
            if (prev[restore] != -1) next[prev[restore]] = restore;
            if (next[restore] != -1) prev[next[restore]] = restore;
        }
    }
    
    string answer(n, 'O');
    while (!removed.empty()) {
        answer[removed.top()] = 'X';
        removed.pop();
    }
    
    return answer;
}

#문제 해결 방법

우선, 이름의 배열 크기가 8이기 때문에 

각자 이름끼리 맞는지 확인까지 해도

완전탐색으로 풀 수 있다는 걸 쉽게 알 수 있다.

때문에 설계를 하자면

1. 이름끼리 비교하는 함수를 만든다

2. 이걸 전체 순회하는 dfs 함수를 만든다

라는 설계가 가능하다 

우선 이름이 맞는지 확인하는 함수는 

bool nameCmp(string user, string banned){
    
    if(user.length() != banned.length()){
        return false;
    }else{
        for(int i=0; i<user.length(); ++i){
            if(banned[i] != '*' && user[i] != banned[i]){
                return false;
            }
        }
    }
    
    return true;
}

로 쉽게 만들 수가 있다.

길이가 다르거나

*이 아닌다 문자가 다른경우에 false 를 리턴한다

이제 dfs 함수를 만들어야 되는데 이부분이 조금 고민이 된다

여기서 탐색 포커싱을

banned_id에 맞춰야 된다

각 banned_id에 매칭되는 id를 찾았다면 다음 banned id 로 넘어가면 된다

그리고 여기서 까다로운 부분이 하나 더 있는데.

각각의 정답으로 고른 정답에서 

중복되는 답이 있을 수 있기 때문이다.

같은 아이디가 순서만 다른 정답이 있을 수 있다.

이 부분은 set을 사용해서 해결할 수 있는데

다른 분들 같은경우에는 set에서 find 해서 없는경우에만 insert 하도록 하는 경우가 일반적인 것 같다.

나는 set<set<string>> result  // 이중 셋을 사용해서 중복을 제거했다.

이중 셋을 사용하면 중복을 편하게 제거할수 있으니 유용한 팁이라고 할 수 있다.

#전체 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

//dfs 로 모든 조합을 살펴보고
//이름을 비교하는 함수도 만들어야함


bool nameCmp(string user, string banned){
    
    if(user.length() != banned.length()){
        return false;
    }else{
        for(int i=0; i<user.length(); ++i){
            if(banned[i] != '*' && user[i] != banned[i]){
                return false;
            }
        }
    }
    
    return true;
}

void dfs(vector<string>& user_id, vector<string>& banned_id, vector<bool>& visited, set<set<string>>& result, set<string>& currentSet, int index) {
    if (index == banned_id.size()) {
        result.insert(currentSet);
        return;
    }
    for (int i = 0; i < user_id.size(); ++i) {
        if (!visited[i] && nameCmp(user_id[i], banned_id[index])) {
            visited[i] = true;
            currentSet.insert(user_id[i]);
            dfs(user_id, banned_id, visited, result, currentSet, index + 1);
            currentSet.erase(user_id[i]);
            visited[i] = false;
        }
    }
}


int solution(vector<string> user_id, vector<string> banned_id) {
    
    set<set<string>> result;
    set<string> currentSet;
    vector<bool> visited(user_id.size(), false);
    
     dfs(user_id, banned_id, visited, result, currentSet, 0);

    return result.size();
}

#문제 간단 정리

브루트 포스로는 시간초과와 효율성으로 엉망일게 보이니

투 포인터/슬라이딩 윈도우를 활용하자

#문제 해결 방법

우선 사실 구간을 [1,3] [2,4] 이런식으로 출력 하라는 것 자체가

어쩌면 투 포인터 사용에 대한 힌트일지도 모른다.

1.우선 전체 보석의 종류의 개수를 센 뒤에.

2. 투 포인터를 사용한다

 만약 현재 보석의 모든 개수를 포함한다면

 left를 증가시키고 

보석의 종류가 부족하다면 right 를 증가시키면 된다.

2-1 

 여기서 보석종류에 따른 개수를

map 으로 기록해주는데

만약 left가 한칸 올라가서 map에 있는 보석종류의 개수가 0이되었다면

전체 보석의 개수를 기록하고 있는 변수를 (currenTypes)를 -1 해주면된다

반대로 right 한칸 올라가서 보석종류의 개수가 0개였다면

전체 보석의 개수를 기록하고 있는 변수를 (currenTypes)를 +1 해주면된다

이 작업은 효율성 때문에 이뤄지는 작업이다.

현재 가지고있는 보석의 종류 개수를 쉽게 카운트 하기 위해서.

나머지는 전체 코드를 보고 이해하는게 쉬울것이다.

#전체 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <climits>
#include <set>

using namespace std;

vector<int> solution(vector<string> gems) {
    unordered_map<string, int> gemCount;
    set<string> gemTypes(gems.begin(), gems.end());
    int totalTypes = gemTypes.size();
    
    int minlength = INT_MAX;
    pair<int, int> index;
    
    // 투 포인터, 슬라이딩 윈도우를 활용
    int l = 0, r = 0;
    int currentTypes = 0;
    
    while (true) {
        if (currentTypes == totalTypes) { // 모든 종류의 보석이 포함되었을 때
            if (minlength > r - l) {
                minlength = r - l;
                index = make_pair(l, r);
            }
            if (--gemCount[gems[l]] == 0) {
                currentTypes--;
            }
            l++;
        } else { // 모든 종류의 보석이 포함되지 않았을 때
            if (r == gems.size()) break; // 종료 조건
            if (gemCount[gems[r]]++ == 0) {
                currentTypes++;
            }
            r++;
        }
    }
    
    vector<int> answer = {index.first + 1, index.second};
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/49191

#문제 간단 정리

플로이드 워셜을 사용

#문제 해결 방법

기본적으로 플로이드 워셜을 사용한다.

플로이드-워셜 알고리즘을 잘 모른다면 

https://namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

를 참고해서 확인하고 오도록 하자

기본적으로 플로이드 워셜은 모든 노드에 대한 최단거리를 갱신하는데 (N^3)

이어져 있지 않은 노드라면 INF 로 남아있게 된다

즉 플로이드 워셜을 사용한 후

INF 로 남아있는 거리가 있는지 확인하고

그 노드는 순위를 확인 할 수 없는 노드이다.

#전체 코드

#include <vector>
#include <queue>
#include <climits>


using namespace std;
int solution(int n, vector<vector<int>> results) {
    const int INF = 1000000000;
    vector<vector<int>> nodes (n+1, vector<int>(n+1,INF));
    
    for(int i=1; i<=n; i++){
        nodes[i][i] = 0;
    }
    for(auto result : results){
        nodes[result[0]][result[1]] = 1;
    }
    
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
               if(nodes[i][j] > nodes[i][k] + nodes[k][j]){
                   nodes[i][j] = nodes[i][k]+nodes[k][j];
               } 
            }
        }
    }
    
    
    int answer = 0;
    for (int i = 1; i <= n; ++i) {
        bool flag = true;
        for (int j = 1; j <= n; ++j) {
            if (i != j && (nodes[i][j] == INF && nodes[j][i] == INF)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            answer++;
        }
        
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/49189

#문제 간단 정리

bfs를 활용해서 거리 측정

#문제 해결 방법

bfs를 활용해서 가장 먼 노드의 개수를 측정해 주면 된다

양방향 노드기 때문에 양방향 설정에 주의하도록 하자

그 이외에는 딱히 기본 bfs 기 때문에 주의할 건 없다.

#전체 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    
    vector<vector<int>> graph(n + 1);
    for ( auto e : edge) {
        graph[e[0]].push_back(e[1]);
        graph[e[1]].push_back(e[0]); 
    }
    
    vector<bool> visited(n + 1, false);
    vector<int> dist(n + 1, 0);

    queue<int> q;
    q.push(1); 

    visited[1] = true;

    int maxDist = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (int next : graph[now]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
                dist[next] = dist[now] + 1;
                maxDist = max(maxDist, dist[next]);
            }
        }
    }
    int count = 0;
    for(int i=1; i<=n; i++){
        if(dist[i] == maxDist){
            count++;
        }
    }
    
    for(int a : dist){
        cout << a << ' ';
    }

    return count;
}

코딩테스트 연습 - 단속카메라 | 프로그래머스 스쿨 (programmers.co.kr)

#문제 간단 정리

그리디 문제기 때문에

구현보다 발상이 더 어렵다

#문제 해결 방법

우선 무조건 단속 카메라의 끝나는 지점으로 정렬해서

다음에 오는 시작지점이 현재 끝나는 지점에 바깥에 있다면 

단속 카메라가 하나 더 필요한거기 때문에 

단속카메라 개수를 1개 늘리고

마지막 지점 변수를 업데이트 해준다,

마지막 지점으로 체크한다는 발상이 어려운데

이 힌트를

각 구간을 전부 저장하는건 비효율적이고 너무 구현이 어렵기 때문에

더 좋은 방향을 자연스럽게 떠올리려는 것이 필요하다

#전체 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {

    sort(routes.begin(), routes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    int cctv = 0;
    int lastCamera = -30001; 

    for (const auto& route : routes) {
        if (route[0] > lastCamera) { 
            lastCamera = route[1];
            cctv++;
        }
    }

    return cctv;
}

https://school.programmers.co.kr/learn/courses/30/lessons/42579#qna

#문제 간단 정리

해시를 조금 더 복잡하게 사용하는 문제

#문제 해결 방법

일단 문제 설명이 복잡해서 조금 헷갈릴 수 있는데, 정리하자면

가장 높은 조회수를 기록한 장르의  조회수가 가장 높은 1,2번 곡들을 차례대로 

수록하는것이다

이걸 구현하기 위해서 우선

map 으로 장르별로 조회수를 취합하고

이걸 vector 로 복사해 정렬해서 장르별 순위를 알아낸다.

이 장르별 순위대로 

주어진 곡들 벡터를 순회하는데 현재 장르랑 같은 경우에

1순위 2순위를 갱신하도록한다,

그리고 순서대로 정답 벡터에 넣어주면된다

이해가 잘 안된다면 코드 주석을 살펴보자

#전체 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool valueComp(const pair<string, int>& a, const pair<string, int>& b) {
    return a.second > b.second; // 장르별 총 재생 수에 따라 내림차순 정렬
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    map<string, int> genreMap;

    // 장르별 총 재생 수를 계산
    for (int i = 0; i < genres.size(); i++) {
        genreMap[genres[i]] += plays[i];
    }

    // 장르별 총 재생 수를 벡터로 이동
    vector<pair<string, int>> vec(genreMap.begin(), genreMap.end());

    // 벡터를 재생 수에 따라 정렬
    sort(vec.begin(), vec.end(), valueComp);

    vector<int> answer;
    for (int i = 0; i < vec.size(); i++) {
        pair<int, int> first = {-1, -1}; // 최대 재생수, 인덱스
        pair<int, int> second = {-1, -1}; // 두번째로 많은 재생수, 인덱스

        for (int j = 0; j < genres.size(); j++) {
            if (genres[j] == vec[i].first) {
                if (plays[j] > first.first) {
                    second = first; // 기존 첫번째 최대값을 두번째로 밀어냄
                    first = {plays[j], j}; // 새로운 최대값 설정
                } else if (plays[j] > second.first) {
                    second = {plays[j], j}; // 두번째 최대값 갱신
                }
            }
        }
        if (first.second != -1) answer.push_back(first.second);
        if (second.second != -1) answer.push_back(second.second);
    }
    
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/60059

#문제 간단 정리

2차원 배열을 이용하여 자물쇠와 키를 대조하여 정답을 찾자.

다만 키가 자물쇠의 영역을 벗어나는 것이 주목 포인트다

#문제 해결 방법

일단 대략적인 내용은 문제를 읽어서 이해했다고 치고

큰 문제 해결의 맥락을 잡으면

1. 키와 자물쇠를 2차원 배열을 이용해서 표시한다.

2. 그렇게 받은 키의 회전 함수를 구현한다. (하나씩 대조하면서 좌표가 어떻게 변하는지 확인하자)

3. 키를 자물쇠에 넣어서 확인한다.

이 문제에서는 3번이 핵심이 된다.

우선 처음에는 방법 두어가지가 떠오르는데.

3-1. 자물쇠에 넣을 키의좌표를 유동적으로 넣어가면서 검사.

3-2.  자물쇠를 연장시켜서 자물쇠*3의 맵을 만들어 키를 넣어가면서 검사.

우선 1번이 좀 더 고급진 방법이겠지만

구현문제이기 때문에 가장 구현이 쉽고 간단할 3-2번 방법으로 선택

그림으로 표현하자면  대략 다음과 같다

그림을 보면  나는  n(자물쇠)*3 로 구현을 했지만 키가 완전히 맵과 안겹치는건 쓸모가 없기 때문에 한칸 줄여서 맵을 만들면 좀 더 속도가 빨라졌을 것이다.

이후 내가 푸는 방법은

자물쇠의 0의 개수를 세준다음

연장한 자물쇠는 모두 2로 채워준다

그리고 키를 첫번째 칸부터 마지막 칸까지 이동시키면서 대조한후

회전시킨후 반복을 3번 더 시켜준다 (360도)

그림으로 보이자면 대략 이렇다

만약 대조하면서 키가 1 자물쇠가 0 라면 정답 카운트 +1

자물쇠가 1 키가 1 이면 정답 카운트를 -123456789로 설정하여 오답처리

자물쇠가 0 키가 0 이여도 오답처리

정답카운트가 자물쇠의 빈 공간 카운트와 일치한다면

정답을 찾은것이다.

사실 여기서 자물쇠의 키의값을 더해서 정답을 찾아도 좋을 것 같고.

우선 주어진 맵의 길이가 20정도로 작기 때문에 연장후 회전까지 한 테스트 케이스가

생각보다 작기 때문에 단순한 맵 연장이 가장 좋을 것 같다는 생각이 들었다.

(단순하고 틀리기 가장 어려우니까)

#전체 코드

#include <string>
#include <vector>
#include <iostream>
int n,m;


using namespace std;

vector<vector<int>> rotate(vector<vector<int>> key){ // key 시계방향 90도 회전
    vector<vector<int>> tmp;
    tmp.resize(n,vector<int>(n,0));
    
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            tmp[i][j] = key[m-1-j][i];
        }
    }
    return tmp;
}



int match(){
    
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    bool answer = false;
    m = key[0].size(); n = lock[0].size();

    vector<vector<int>> newMap;
    newMap.resize(n*3,vector<int>(n*3,2)); // 확장된 자물쇠 m*3의 크기
    
    
    int countEmpty = 0;
    cout << "map: \n";
    for(int i=0;i<n;i++){ //lock 의 빈 공간 카운트
        for(int j=0;j<n;j++){
            if(lock[i][j] == 0){
                countEmpty++;
            } 
            newMap[i+m][j+m] = lock[i][j]; //newMap 갱신
            cout << lock[i][j] <<" "; //map 출력
        }
        cout << "\n";
    }
    
    cout << "key: \n";
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cout << key[i][j] << " ";
        }
        cout << "\n";
    }
    
    cout << "emptyCount: " << countEmpty << "\n";

    for(int k=0; k<4; k++){
        if(k != 0) key = rotate(key);

    
    for(int i=0;i<m*3;i++){ //match 인지 확인하기
        for(int j=0;j<m*3;j++){
            
            //lock에 맞는지 확인하는 구간
            int ansCount = 0;
            for(int i2=0; i2<m; i2++){
                for(int j2=0; j2<m; j2++){
                    if(i2 + i < n*3 && j2 + j <n*3){ //범위 제한
                        
                    
                    if(newMap[i+i2][j+j2] == 0 && key[i2][j2] == 1 ){ 
                            ansCount++;
                    }  
                    if(newMap[i+i2][j+j2] == 0 && key[i2][j2] == 0){ 
                            ansCount = -123456789;
                    } 
                    if(newMap[i+i2][j+j2] == 1 && key[i2][j2] == 1){ 
                            ansCount = -123456789;
                    } 
                        
                    }//범위지정
                }   
            }
            cout << ansCount << " ";
             if(ansCount == countEmpty){
                        answer = true;
                }
        }
        
    } 
        
    } // 회전
    
    
    
    return answer;

}