JArchive 프로그래밍 일기

문제 링크 

문자열로 주어진 숫자배열을 숫자만 추출해서 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;
}

문제 링크 

조합을 하나씩 써 보면 그 값이 파스칼의 삼각형과 똑같이 나오는 것이 보인다. 

nCm == n-1 C m-1  + n-1 C m 

       1C0, 1C1

   2C0, 2C1, 2C2

3C0, 3C1, 3C2, 3C3

0개를 고를때와 n개중에 n개를 전부 고를 때는 값이 항상 1이다. 

조합 계산할 때 숫자가 커지니까 string 끼리의 계산이 필요했다. 

일의 자리끼리 계산 하고,  10으로 나눈 나머지를 일의자리로 저장한다.

일의 자리 계산 결과를 나누기 10하면, 올림수가 발생했는지 판단할 수 있다. 

"맞았습니다" 코드 링크 

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

int n, m;
string dp[102][102];

string numAdd(string n1, string n2){
  string answer = "";
  int sum = 0;
  int len = max(n1.size(), n2.size());

  for(int i = 0; i < len || sum; i++){ // 일의 자리를 덧셈한다.
    if(n1.size() > i) sum += (n1[i] - '0');
    if(n2.size() > i) sum += (n2[i] - '0');
    answer += ((sum % 10) + '0');
    sum /= 10;
  }

  return answer;
}

string combination(int n, int m){
  if(n == m || m == 0) return "1";

  string &res = dp[n][m];
  if(res != "") return res;

  res = numAdd(combination(n-1, m-1), combination(n-1, m));
  return res;
}

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

  cin >> n >> m;
  string ans = combination(n, m);
  reverse(ans.begin(), ans.end());
  cout << ans;
  return 0;
}

문제 링크

반복문 1개로 푼 코드가 있다. 숫자 제한이 작아서 완전 제곱수를 찾아가며 개수를 셌다. 

"맞았습니다" 코드링크1

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

int m, n, i = 1, cnt;
vector<int> v;

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

  cin >> m >> n;

  while(i * i <= n){
    if(i*i >= m) {
      cnt++; v.push_back(i*i);
    }
    i++;
  }
  if(v.size()==0) cout << -1;
  else cout << accumulate(v.begin(), v.end(), 0) << '\n' << v[0];

  return 0;
}

두 번째는 완전 제곱수를 미리 찾아두고 시작한 코드다. 

"맞았습니다" 코드 링크2 

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

int m, n, total_sum;
int minnum= 1e9;
int arr[100001];

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

  cin >> m >> n;
  int num = 1;
  while(num * num <= n){
    arr[num * num] = 1;
    num++;
  }

  for(int i = m; i <= n; i++){
    if(arr[i]) {
      total_sum += i;
      minnum = min(minnum, i);
    }
  }
  if(total_sum == 0) cout << -1;
  else cout << total_sum << '\n' << minnum;

  return 0;
}

문제 링크 

숫자 하나가 주어진다.

각 자리 숫자를 바꿔서 30의 배수중에 가장 큰 숫자를 만들어야 한다. 

30의 배수가 되려면 일단 마지막 자리가 '0'이어야 한다. 

각 자리 숫자를 모두 더하면, 3의 배수가 되어야 한다. 

"맞았습니다" 코드 링크 

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

long long sum;
string num_st;

int main(void) { // 30의 배수의 조건 : 각 자리 수 합이 3의 배수. 0으로 끝나기.
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> num_st;
  int len = num_st.length();
  for(auto n : num_st) sum += (n - '0'); // 각 자리수 합
  sort(num_st.begin(), num_st.end(), greater<>()); // 내림차순정렬

  if(num_st[len-1] == '0' && sum % 3 == 0) cout << num_st;
  else cout << -1;

  return 0;
}

문제 링크 

"맞았습니다" 코드 링크

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

int n, num, i, mo, ja;

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

  cin >> n;

  while(num < n){ // i: 1, 2, 3, 4, ...
    i++;
    num += i;
  }
  // while문 종료 직후, num은 n보다 같거나 큰 수가 되어 있다.
  int diff = num - n; // 라인 시작점부터 이동할 숫자

  if(i % 2){  // 홀수 라인 - 밑에서 대각선으로 위로 숫자 변화
    ja = 1 + diff;
    mo= i - diff; 
  }
  else { // 짝수 라인 - 위에서 왼쪽 대각선으로 아래로 숫자 변화
    ja = i - diff; 
    mo = 1 + diff;
  }

  cout << ja << '/' << mo;
  return 0;
}

리뷰 

1. 대각선 라인을 기준으로 생각한다.  순서를 떠나서, 그림 그대로 바라보면 아래와 같다. 

[홀]  1번째 라인 : 1/1

[짝]  2번째 라인 : 2/1 , 1/2 

[홀]  3번째 라인 : 3/1, 2/2, 1/3

[짝]  4번째 라인 : 4/1, 3/2, 2/3, 1/4

2. 짝수 라인과 홀수라인에서 분자와 분모가 어떻게 변하는지 보면 규칙을 발견할 수 있다. 

짝수 2번째 라인 :  2 / 1  ,  1 / 2 

=> 분자 : 시작 2, 종료 1  (분자는 감소)

=> 분모 : 시작 1, 종료 2  (분모는 증가)

홀수 3번째 라인 :  3 / 1  ,  2 / 2,  1 / 3 

=> 분자 : 시작 3, 종료 1

=> 분모 : 시작 1, 종료 3 

3. 주어진 숫자 n이 홀수라인에 속하는지, 짝수 라인에 속하는지 확인해야 한다. 

  cin >> n; // n 번째 칸이 홀수 라인인지 짝수 라인인지 확인하기.

  while(num < n){ // i: 1, 2, 3, 4, ...
    i++;
    num += i;
  }

1번째는 1개 분수가 있다.

2번째 라인에는 2개 분수가 있다. num에 1, 2, 3, 4 .. 씩 더해주며 몇 번째 라인에 속한건지 반복문 돌린다.  

반복문 끝나면, 숫자 n은 i 번째 라인에 속한다. 

while문 종료 직후, num은 n보다 같거나 큰 수가 되어 있다. 반복문 마지막에 무조건 i를 더하고 종료하기 때문이다. 

4. offset 확인한다.

diff 변수 :  라인 내부에서 몇 번째 숫자인지를 나타낸다. 

i 가 짝수인 경우.

짝수 라인에서 분자는  i에서 시작한다. --> i - diff 

짝수 라인에서 분모는 1에서 시작한다. --> 1 + diff 

짝수 2번째 라인 :  2 / 1  ,  1 / 2 

=> 분자 : 시작 2, 종료 1  (분자는 감소)

=> 분모 : 시작 1, 종료 2  (분모는 증가)

  if(i % 2){  // 홀수 라인 - 밑에서 대각선으로 위로 숫자 변화
    ja = 1 + diff; // 분모가 1로 시작 i로 종료.
    mo= i - diff; // 분자가 i로 시작, 1로 종료.
  }
  else { // 짝수 라인 - 위에서 왼쪽 대각선으로 아래로 숫자 변화
    ja = i - diff; // 분모 i로 시작 1로 종료
    mo = 1 + diff; // 분자 1로시작 i로 종료
  }

풀릴 듯 안풀려서 고생했다.  나중에 다시 풀기!!!

참고 포스팅

문제 링크

숫자를 최소값으로 만드려면 음수가 많아야 한다. 그래서 '-' 이후에 나오는 숫자들은 모두 뺀다. 

"맞았습니다" 코드 링크 

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

string input, temp_st;
int num;
bool minus_flag;

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

  cin >> input;
  int len = input.size();

  for(int i = 0; i <= len; i++){
    if(input[i] == '-' || input[i] == '+' || i == len){
      (minus_flag) ? num -= stoi(temp_st) : num += stoi(temp_st);
      temp_st = "";
    }else {
      temp_st += input[i];
    }
    if(input[i] == '-') minus_flag = true; // '-'이 다음에 나오는 숫자는 모두 뺀다
  }

  cout << num;
  return 0;
}

문제 링크 

동전을 최소 갯수로 사용해서 합이 K원이 되야 한다. 

동전을 사용할 수 있으려면, K원이 동전값으로 나누어 떨어져야 한다. 

"맞았습니다" 코드 링크

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

int n, k, tempsum, cnt;
int coin[11]; // 동전 종류

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

  cin >> n >> k;
  for(int i = 0; i < n; i++) cin >> coin[i];

  for(int i = n-1; i >= 0; i--){
    cnt += (k / coin[i]);
    k = k % coin[i]; // 나머지 금액
  }
  cout << cnt;
  return 0;
}

문제 링크 

절대값이 가장 작은 것을 리턴해야 하니까 자동 정렬되는 priority queue를 썼다. 

pair<int,int> 는 first를 기준으로 정렬된다. 하지만 first가 똑같으면 second를 기준으로 정렬된다. 

따로 정렬함수를 정의하지 않아도 문제 조건에 맞게 정렬됬다. 

"맞았습니다" 코드 링크 

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

int n, input;

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

  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
  // <절대값, 원본값>

  cin >> n;
  while(n--){
    cin >> input;
    if(input == 0){
      if(pq.empty()) cout << 0 << '\n';
      else {
        cout << pq.top().second << '\n';
        pq.pop();
      }
    }else{
      pq.push({abs(input), input});
    }
  }
  return 0;
}