JArchive 프로그래밍 일기

기타레슨 문제 링크

리뷰 

강의 전부가 M장 블루레이에 담겨야 한다. 따라서 블루레이 크기가 최소 몇분이 되야 하는지 찾는 문제다. 

이분탐색의 타겟은 블루레이의 크기다. 

블루레이의 크기는 최소 1분, 최대 모든 강의의 크기 중에서 탐색할 수 있다.

주의할 점은 블루레이의 크기보다 강의 하나의 크기가 큰 경우도 있을 수 있다는 점이다. 

main 함수 while문에서 이분탐색을 한다.

if문의 b_search() 함수는 블루레이가 mid크기의 강의를 담을 수 있다고 했을 때, M장의 블루레이만으로 모든 강의를 담을 수 있는지 확인하는 bool 함수다. 

이분탐색 문제는 무엇을 주제로 이분탐색 할 지를 잘 생각하고 시작해야되니까 연습이 좀 필요한 것 같다. 

"맞았습니다" 코드 

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

int N, M, answer, front, mid, back;
int blue[100001]; // 강의 길이 목록

bool b_search(int mid){ // mid 크기의 M장 블루레이에 모두 담기는지 확인.

  int sum_time = 0, cnt = 1; // sum_time 은 mid 이하여야 한다. 블루레이 개수 cnt.

  for(int i = N-1; i>=0; i--){

    if(blue[i] > mid){
      return false; // 블루레이 1장에 강의 1개도 못들어가는 경우.
    }

    sum_time += blue[i];
    if(sum_time > mid){
      cnt++;
      sum_time = blue[i];
    }
  }
  return M >= cnt; // 블루레이 개수가 M이하라면 만족.
}

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

  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    cin >> blue[i];
    back += blue[i]; // 모든 강의 길이를 더해서 back에 저장 
  }
  front = 1; // 1분

  while(front <= back){

    mid = (front + back) / 2; // 블루레이 1장의 크기 mid

    if(b_search(mid)){ // mid크기의 블루레이로 M장 이하에 담을 수 있는지?
      answer = mid;
      back = mid-1;
    }else{
      front = mid+1;
    }
  }
  cout << answer;
  return 0;
}

줄 서는 방법 문제 링크 

리뷰 

줄 서는 k번째 방법을 출력해야한다. 

k는 n!이하의 숫자라고 하니깐 뭔가 규칙성이 있을 것 같았다. 

단순하게 next_permutation()으로 구현하니깐 정확성은 다 맞지만, 효율성에서 시간초과나서 틀렸다. 

n = 2 라면, 2가지 방법이 있다. 

[ 1, 2 ] 

[ 2, 1 ] 

n = 3개라면, 3! == 3 * 2 * 1 == 6가지 방법이 있다. 

[ 1 2 3] 

[ 1 3 2]

---------- 1번째, 2번째 방법은 앞자리가 1이다. 

[ 2 1 3]

[ 2 3 1]

--------- 3번째, 4번째 방법은 앞자리가 2다. 

[ 3 1 2]

[ 3 2 1]

--------  5번째, 6번째 방법은 앞자리가 3이다. 

일단 [ 1 2 3 ] 숫자가 들어있는 벡터 num_v를 만든다. 

k번째 방법을 (n-1)! 으로 나누면 idx번째 숫자가 들어갈 자리를 알아낼 수 있다. 

효율성에서 "시간 초과" 난 코드.

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

vector<int> solution(int n, long long k) {
  vector<int> answer;

  vector<int> permu_v;
  for(int i = 1; i <= n; i++) permu_v.push_back(i);

  do{
    k--;
    if(0 != k) continue;
    else{
      for(int i = 0; i < n; i++){
        answer.push_back(permu_v[i]);
      }
      break;
    }
  }while(next_permutation(permu_v.begin(), permu_v.end()));

  return answer;
}

"맞았습니다"코드

#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll factorial(int n){
  if(n == 1) return 1;
  else return n * factorial(n-1);
}
vector<int> solution(int n, long long k) {
  vector<int> answer;

  long long idx, target_num;
  vector<int> num_v;
  for(int i = 1; i <= n; i++) num_v.push_back(i);

  while(0 < n){
    idx = factorial(n) / n;
    target_num = int((k-1) / idx); // answer에 넣을 숫자
    answer.push_back(num_v[target_num]);
    num_v.erase(num_v.begin() + target_num);
    n--;
    k %= idx;
    if(k == 0) k = idx;
  }

  return answer;
}

피로도 문제 링크 

리뷰 

어떤 순서로 던전을 방문해야 가장 많이 방문할 수 있는지 순서를 섞어봐야한다. 

던전이 3개라면, 벡터에 0, 1, 2를 넣고 모든 경우에 방문한 던전개수를 세보며 순열을 돌려서 풀 수 있었다. 

"맞았습니다" 코드 

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

int solution(int k, vector<vector<int>> dungeons) {
  int answer = -1;
  int dungeons_cnt = dungeons.size();
  vector<int> permu_v;

  for(int i = 0; i < dungeons_cnt; i++) permu_v.push_back(i);

  do{
    int temp_k = k, cnt = 0;

    for(int i = 0; i < dungeons_cnt ; i++){
      int turn = permu_v[i];
      if(temp_k < dungeons[turn][0]) {

        break;
      }else{
        temp_k -= dungeons[turn][1];
        cnt++;
      }
    }
    answer = max(answer, cnt);
  }while(next_permutation(permu_v.begin(), permu_v.end()));

  return answer;
}

문제 링크 

리뷰 

n이 1일때, n이 2일때 부터 n이 5일때 몇 가지 경우의 수가 있는지 그려보면 규칙성이 보인다. 

공간의 세로 길이는 항상 2다. 

모든 막대는 1 X 2크기다. 

아래는 n == 5 인 경우, 가능한 배열을 그린것이다. 

막대 5개를 세운다. 

막대 3개는 세우고, 2개는 눞인다. 

막대 1개는 세우고, 4개는 눞인다. 

맞았습니다 코드 

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;

int D[60001];
int solution(int n) {

  D[1] = 1, D[2] = 2; 
  
  for(int i = 3; i <= n; i++){
    D[i] = (D[i-1] + D[i-2] ) % MOD;
  }
  return D[n];
}

괄호 회전하기 문제 링크 

리뷰 

입력 예시 -> "[ ] ( ) { } "  (길이 6 문자열) 

주어진 문자열을 1만큼 회전하면, 인덱스 0 번째 문자가 문자열의 제일 뒤로 간다. -> " ] ( ) { } [ "

입력 문자열을 연이어 붙이면 "[ ] ( ) { } [ ] ( ) { } " 가 된다.   (길이 12 문자열) 

크기 x 는 0부터 '문자열의 길이 -1' 까지다. 

 "[ ] ( ) { } [ ] ( ) { } "에서 0부터 6개를 잘라내서 올바른 괄호인지 검색한다. 

1부터 6개 잘라내서 검사한다. 2부터 6개 잘라내서 검사한다.

이렇게 하면 괄호를 n만큼 회전한 문자를 구할 수 있다. 

"맞았습니다" 코드 

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

int answer, ssize;

bool check(string s){ // 문자열이 올바른 괄호인지 확인하여 T/F 리턴 
  bool res = true;
  stack<char> st;

  for(int i = 0; i < ssize; i++){
    if(s[i] == '{' || s[i] == '(' || s[i] == '['){
      st.push(s[i]);
    }else if(!st.empty()){
      if( (st.top() - s[i] == -1) || (st.top() - s[i] == -2)){
        st.pop();
      }else{
        res = false; break;
      }
    }else if(st.empty()){
      if(s[i] == '}' || s[i] == ')' || s[i] == ']')
        res = false; break;
    }
  }
  if(!st.empty()) res = false; // 검사 후 스택이 비어있어야 올바른 괄호 
  return res;
}

int solution(string s) { // 괄호를 회전하면 괄호가 반복되니까 s를 이어붙임. 
  ssize = s.size();      // "[](){}" -> "[](){}[](){}"
  s += s;

  for(int i = 0; i < ssize; i++){ // 0부터 6개, 1부터 6개, 2부터 6개 ... 
    string target = s.substr(i, ssize);
    bool result = check(target);
    if(result) answer++;
  }
  return answer;
}

압축 문제 링크 

리뷰 

사전에는 A부터 Z까지 들어있는데, 없는 문자열을 만나면 사전에 추가해야 한다. 

사전에 문자열이 있나 없나 확인할 연산이 많으니까 사전 자료구조는 map을 썼다. 

map < 문자열 string , 색인번호 int >  dic ;

사전에서 탐색할 문자열은 target 스트링에 한 글자씩 이어붙여서 만든다. 

예제의 입력 "KAKAO" 가 있다. 

K는 사전에 존재하지만, KA는 사전에 없다. 

if(dic.find(target) == dic.end())  조건문 에 만족하게 된다. 

사전에 없는 KA를 넣는다.  dic[target] = num++;

KA 말고, 그 직전 문자 K는 사전에 존재한다는 거니까. target 문자열에서 길이 1개가 짧은 문자열 K을 answer에 추가한다.

여기서 중요한건 target이라는 탐색 문자열을  ""로 초기화 해야된다는 것이다. 

target 문자열 "KA"는 입력문자열 "KAKAO"의 0번째와 1번째 문자를 이어붙인 것이다. 

K, KA를 확인했으니 이제 A를 확인할 차례다. 

따라서 KA라는 없던 문자열을 사전에 추가했으니, 이어붙일 단어의 인덱스는 A의 인덱스 1이 되어야 한다. 

i--  로 target 문자열에 이어붙일 인덱스를 감소시켜줘야 한다. 

"맞았습니다" 코드 

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

map<string,int> dic; // {단어, 색인 번호}
int num = 1; // 색인 번호 

void init_dictionary(){
  char ch = 'A';
  for(; ch <= 'Z'; ch++, num++){
    string st = ""; st += ch;
    dic[st] = num;
  }
}

vector<int> solution(string msg) {
  vector<int> answer;

  init_dictionary();
  int len = msg.length();
  int start_idx = 0;

  string target = "";
  for(int i = 0; i < len; i++){ // 탐색 시작할 인덱스 i
    target += msg[i]; // 탐색할 문자

    if(dic.find(target) == dic.end()){
      dic[target] = num++; // 사전에 등록

      target = target.substr(0, target.size()-1);
      answer.push_back(dic[target]);
      target = "";
      i--;
    }
  }
  answer.push_back(dic[target]); // 마지막 글자 
  return answer;
}

문제 링크 

리뷰 

크레인은 칸의 최상위 인형만 뽑을 수 있다. 그래서 board 열 개수만큼 스택을 선언했다. 

board의 가장 아래 열 부터 0번째 열 방향으로 순회하면, 스택에 문제 그림과 비슷하게 인형이 쌓인다. 

크레인의 접근 열 순서를 담고있는 배열 moves 를 순회하여 열 번호에 해당하는 stack 을 확인한다. 

stack의 top을 확인하기 전에, stack의 크기가 0 이 아닌지 확인해야 한다. 

"맞았습니다" 코드 

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

int solution(vector<vector<int>> board, vector<int> moves) {
  int answer = 0;
  int h = board.size(), w = board[0].size();

  vector<stack<int>> v(w+1); // 칸 마다 스택 만들어둔다
  stack<int> basket; // 바구니 

  for(int i = h-1; i >= 0; i--){
    for(int j = 0; j < w; j++ ){
      if(board[i][j] != 0) v[j].push(board[i][j]);
    }
  }

  for(int m = 0; m < moves.size(); m++){
    int i = moves[m]; // 크레인이 인형을 꺼낼 칸 번호  
    if(v[i-1].size() == 0) continue; // 칸에 인형이 없으면 지나감 

    int target = v[i-1].top(); // target: 인형 번호 
    v[i-1].pop();

    if(basket.size() > 0 && basket.top() == target) {
      basket.pop(); answer += 2;
    } else basket.push(target);
  }
  return answer;
}