Computer Science & Engineering

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

이 문제에서는 각 집합을 탐색하며 숫자인지를 판별하고 검색될 때마다 검색된 횟수를 1씩 올려주는 방식으로 풀이했다.

#include <string>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //sort 비교 함수
    return a.second > b.second; //검색횟수가 많은 순서대로 저장
}

vector<int> solution(string s) {
    vector<int> answer;
    char num[100001] = {0}; //숫자를 만들 배열
    vector<int> arr;
    vector<pair<int,int>> tmpans;
    bool visit[501]; //탐색한지 확인
    int cnt = 0;
    int idx = 0;
    for(int i = 0; i < s.length(); i++) {
            if(s[i] == '{') { //시작시 메모리 초기화
                idx = 0;
                memset(visit, 0, sizeof(visit));
                memset(num, 0, sizeof(num));
            }
            else if(s[i] == '}') {
                if(num[0] != 0) { //숫자생성
                    int n = atoi(num);
                    memset(num, 0, sizeof(num));
                    arr.push_back(n);
                    cnt++; //한 집합에서 숫자의 개수 추가
                }
                else {//입력의 마지막 '}'인 경우
                    continue;
                }
                if(arr.size() != 0) { //집합에 숫자가 있는 경우
                    if(cnt < tmpans.size()) { //만약 지금까지 탐색한 튜플의 원소가 더 많은 경우 검색횟수만 +1
                        for(int j = 0; j < tmpans.size(); j++) {
                            for(int k = 0; k < arr.size(); k++) {
                                if(tmpans[j].first == arr[k]) {
                                    tmpans[j].second++;
                                }
                            }
                        }
                    }
                    else { //새로운 튜플 원소가 나타난 경우
                        for(int j = 0; j < arr.size(); j++) {
                            int chk = 0;
                            int k;
                            for(k = 0; k < tmpans.size(); k++) {
                                if(visit[k]) { //탐색한 튜플 원소 건너뜀
                                    continue;
                                }
                                if(tmpans[k].first == arr[j]) { //이미 검색된 원소는 검색횟수 1추가
                                    tmpans[k].second++;
                                    visit[k] = 1;
                                    chk = 1;
                                    break;
                                }
                            }
                            if(!chk && (k == tmpans.size())) { //새로운 원소 추가하고 검색횟수 1로 설정
                                tmpans.push_back({arr[j], 1});
                            }
                        }
                    }
                    memset(visit, 0, sizeof(visit));
                }
                else continue;
                cnt = 0;
                arr.clear();
                idx = 0;
                memset(num, 0, sizeof(num));
            }
            else if(s[i] ==  ',') {
                if(num[0] != 0) { //집합을 구분 짓는 ','이 아닌 경우
                    int n = atoi(num);
                    arr.push_back(n);
                    memset(num, 0, sizeof(num));
                    cnt++;
                }
                memset(num, 0, sizeof(num));
                idx = 0;
                continue;
            }
            else { //10진수 숫자 생성
                num[idx++] = s[i];
            }
    }
    sort(tmpans.begin(), tmpans.end(), cmp); //검색 횟수 순으로 정렬
    for(int i = 0; i < tmpans.size(); i++) { //정답 옮겨 저장
        answer.push_back(tmpans[i].first); 
    }
    return answer;
}

임시 정답 vector를 선언하고 원소와 검색된 횟수를 저장한다. 모든 집합을 탐색하며 기존에 검색된 원소 수보다 많은 경우 모두 1씩 증가하고 없는 원소는 추가하여준다. 입력값을 모두 탐색한 후 가장 많은 빈도의 원소 순으로 정렬되므로 정답에는 원소만 옮겨 저장해준다. 

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

이 문제에서는 vector로 입력이 주어진다. 주의해야할 점은 주어진 NxN 행렬에서 탐색하려는 행만 접근하는 것이 아닌 0번 행부터 N-1번 행까지 0이 아닐 때 까지 열을 모두 탐색해야한다는 점이다. 즉 한 행은 뽑기 기계의 깊이를 나타낸다. 아래는 풀이한 코드이다.

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

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    vector<int> arr;
    int answer = 0;
    for(int i = 0; i < moves.size(); i++) { 
        int idx = moves[i]-1; //탐색하고자 하는 열
        int doll = 0;
        for(int j = 0; j < board.size(); j++) { //해당 각 행에서 인형이 있는지 확인
            if(board[j][idx] != 0) { //인형이 발견한 경우
                doll = board[j][idx];
                board[j][idx] = 0;
                break;
            }
        }
        if(doll == 0) continue; //인형을 발견하지 못한 경우
        if(arr.size() == 0) { //뽑은 인형을 담는 바구니가 비어있는 경우
            arr.push_back(doll);
            continue;
        }
        else if(arr.back() == doll) { //바구니 맨 위에있는 인형과 뽑은 인형이 같은 경우
            arr.pop_back();
            answer+=2; //이미 있는 인형과 발견한 인형 모두 사라지므로 +2
        }
        else arr.push_back(doll); //바구니 맨 위에있는 인형과 뽑은 인형이 다른 경우
        
    }
    return answer;
}

뽑으려고하는 열들은 move라는 vector로 주어진다. 뽑기를 진행하며 주어진 행렬 board의 해당 열에 인형이 있는지 확인한다. 인형이 있는 경우 바구니인 arr의 마지막 값과 비교한다. 만약 arr가 비어있는 경우 push_back을 하고 arr의 마지막 값이 인형과 같은 경우 두 인형 모두 터져서 사라지고 인형 2개가 사라지므로 answer를 2 올려준다. 마지마으로 인형이 다른 경우 마지막에 push_back해준다.