JArchive 프로그래밍 일기

문제 링크 

리뷰 

문자열 길이가 100만 이하다. 그래서 효율성을 고려해야한다. 

그리고 자연수라는 조건이 있다. 자연수는 0 포함임을 유의하자! 

맞았습니다 코드

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

int solution(string s){
  int answer = 0;
  int len = s.length();
  int i = 0;
  stack<char> st;

  if(s.empty() || len % 2 == 1) return 0;
  while(i < len){
    if(st.empty() || st.top() != s[i]) {
      st.push(s[i]);
    }
    else if(st.top() == s[i]) {
      st.pop();
    }
    i++;
  }
  answer = (st.size() != 0) ? 0 : 1;
  return answer;
}

문제 링크 

맞았습니다 코드 

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

bool check[51]; // 확인 여부 

int solution(string begin, string target, vector<string> words) {
  int min_cnt = 1e9; // 최소 이동 횟수 
  int vector_size = words.size();
  int word_size = begin.size();

  queue<pair<int,string>> qu;
  qu.push({0, begin});

  while(!qu.empty()){
    int cnt = qu.front().first;
    string current_s = qu.front().second; // 비교 문자열
    qu.pop();

    for(int i = 0; i < vector_size; i++){
      // 이미 확인한 문자 지나감
      if(check[i]) continue;

      // 현재 문자열과 i번째 문자열이 1개만 다른지 확인
      int diff_cnt = 0;
      for(int d = 0; d < word_size; d++){
        if(words[i][d] != current_s[d]) diff_cnt++;
      }

      if(diff_cnt == 1){
        if(words[i] == target) { min_cnt = cnt + 1; break; } // 찾음
    
        qu.push({cnt+1, words[i]}); // 1개만 다르니까 여기로 이동 
        check[i] = true; // 이동했으니까 표시 
      }
    }
  }
  if(min_cnt == 1e9) min_cnt = 0;
  return min_cnt;
}

문제 링크 

숫자를 제거했을 때, 맨 앞에 0이 위치하면 안된다. 

맞았습니다 코드 

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


string solution(string number, int k) {
    string answer = "";
    int len = number.length() - k; // 첫 번째 숫자로서 가능한 인덱스 
    int start_idx = 0; // 비교를 시작할 인덱스 

    for (int i = 0; i < len; i++) {

        char max_num = number[start_idx];
        int max_idx = start_idx;

        for (int j = start_idx ; j <= k+i; j++) {
            if (max_num < number[j]) {
                max_num = number[j];
                max_idx = j;
            }
        }
        start_idx = max_idx + 1;
        answer += max_num;
    }
    return answer;
}

문제 링크 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector<int> &a, vector<int> &b){
  return a[2] < b[2];
}
int get_parent(vector<int> &parent, int x){
  // 부모노드가 자신이라면 자신을 리턴
  if(parent[x] == x) return x;
  // 부모노드가 자신이 아니라면, 최상위 부모 찾기
  return parent[x] = get_parent(parent, parent[x]);
}

void union_parent(vector<int> &parent, int a, int b){
  a = get_parent(parent, a);
  b = get_parent(parent, b);
  // 작은 노드쪽의 부모로 병합
  a < b ? parent[b] = a : parent[a] = b;
}
bool find(vector<int> &parent, int a, int b){
  a = get_parent(parent, a);
  b = get_parent(parent, b);
  return a == b; // 비교 내용을 리턴, 사이클 방지용
}
// 크루스칼 알고리즘 : 비용이 적은 순으로 costs 정렬
int solution(int n, vector<vector<int>> costs) {
  int answer = 0, maxNum = 0;

  sort(costs.begin(), costs.end(), cmp);
  for(auto c : costs) if(maxNum < c[1]) maxNum = c[1];

  vector<int> parent; // i번째 노드의 부모노드를 저장하는 parent 벡터
  for(int i = 0; i <= maxNum; i++) parent.push_back(i);

  for(auto c : costs){
    // 두 개의 부모 노드가 다르다면 (사이클 없다면)
    if(!find(parent, c[0], c[1])){
      answer += c[2]; // 결과에 가중치 추가
      union_parent(parent, c[0], c[1]); // 부모노드 병합
    }
  }
  return answer;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n = 4;
  vector<vector<int>> costs{{0,1,1}, {0,2,2}, {1,2,5}, {1,3,1}, {2,3,8}};
  cout << solution(n, costs);

  return 0;
}

문제 링크 

문자열로 주어진 숫자배열을 숫자만 추출해서 deque에 넣어야 했다. 

숫자가 여러자리 수인 경우가 있다. 그래서 숫자인 문자를 이어붙이고, 특수문자가 나오면 숫자인 문자열을 stoi()로 정수로 바꿨다. 

함수를 순회할 때,

D 일 때도 그렇고 R일 때도 deque가 비어있는건지를 확인해야한다. 이것때문에 계속 틀렸었다. 

"맞았습니다" 코드 링크 

#include <bits/stdc++.h>
using namespace std;

int t, n;
string func, arr;

void check(string f, int n, string arr){
  string answer = "";
  bool flag = true;
  bool reverse_flag = false;
  deque<int> dq;

  string st_digit = "";
  for(int i = 0; i < arr.length(); i++){
    if(isdigit(arr[i])){
      st_digit += arr[i];
    }else{
      if(!st_digit.empty()){
        dq.push_back(stoi(st_digit));
        st_digit = "";
      }
    }
  }

  for(auto o : f){
    if(o == 'R') reverse_flag = !reverse_flag;
    else {
      if(dq.empty()) { flag= false; cout << "error\n"; break; }
      if(reverse_flag)  dq.pop_back();
      else dq.pop_front();
    }
  }

  if(flag){ // error 아닌 경우에만 배열 출력 
    cout << "[";

    if(reverse_flag){ // 뒤집혀있다면,
      for(auto d = dq.rbegin(); d != dq.rend(); d++){
        if(d == dq.rend()-1) {
          cout << *d;
        }
        else { cout << *d << ","; }
      }
    }else{
      for(auto d = dq.begin(); d != dq.end(); d++){
        if(d == dq.end()-1) {
          cout << *d;
        }
        else { cout << *d << ","; }
      }
    }
    cout << "]\n";
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> t;
  while(t--){
    cin >> func >> n >> arr;
    check(func, n, arr);
  }
  return 0;
}

문제 링크 

"맞았습니다" 코드 

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>

using namespace std;

map<string, int> report_cnt; // 유저별 신고당한 횟수
unordered_map<string, set<string>> report_map; // 유저별 신고한 타 유저 리스트

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
  vector<int> answer;

  for(string s : report){
    int blank = s.find(' ');
    string from = s.substr(0, blank);
    string to = s.substr(blank);

    if(report_map[from].find(to) == report_map[from].end()){
      report_cnt[to]++; // to 가 신고당한 횟수
      report_map[from].insert(to); // from 이 to를 신고함
    }
  }
  for(string s : id_list){
    int res = 0;
    for(string target : report_map[s]){ // 유저 s가 신고한 타겟들
      if(report_cnt[target] >= k) res++; // 타겟이 신고당한 횟수가 k이상이면? res를 증가시킴
    }
    answer.emplace_back(res);
  }
  return answer;
}

문제 링크 

게임판 1차원 배열 board 가 있다. 뱀이나 사다리가 있는 칸만 0이 아닌 값이 있다. 

뱀이나 사다리가 있는 칸은, 목적지 칸 인덱스를 저장하도록 했다.

42칸에 사다리가 있으면 50으로 이동할 때, board[42] = 50 이다. 

1의 위치에서 시작하고, 목적지는 100이다. 최소 이동횟수를 구하는 bfs로 푼 코드다. 

"맞았습니다" 코드 링크 

숨바꼭질 문제와 비슷하게 느껴졌다. 

#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
int answer = 1e9;
int board[102]; // 게임판
bool visited[102]; // 방문 체크

int bfs(){
    queue<pair<int,int>> qu; // <현재위치, 주사위 던진 횟수>
    qu.push({1, 0});
    visited[1] = true;

    while(!qu.empty()){
      pair<int,int> p = qu.front();
      qu.pop();

      int cur = p.first;
      int cur_cnt = p.second;

      if(cur == 100) {  answer = min(answer, cur_cnt); break; }// 목적지 도착

      for(int i = 1; i <= 6; i++){ // 주사위
        int next_cur = cur + i;
        if(next_cur > 100 || visited[next_cur]) continue; // 방문했거나 범위 초과시 지나감
        visited[next_cur] = true;
        
        if(board[next_cur] == 0) qu.push({next_cur, cur_cnt + 1});
        else qu.push({board[next_cur], cur_cnt + 1});
      }
    }
    return answer;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n+m; i++){ // 사다리와 뱀 
    cin >> a >> b; board[a] = b;
  }
  cout << bfs();
  return 0;
}