JArchive 프로그래밍 일기

줄 서는 방법 문제 링크 

리뷰 

줄 서는 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;
}

문제 링크 

리뷰 

크레인은 칸의 최상위 인형만 뽑을 수 있다. 그래서 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;
}

징검다리 문제 링크 

리뷰 

코딩테스트 고득점 키트의 '이분탐색'카테고리에 있는 문제다. 

바위 중에 n개를 제거했을 때, 바위 간 거리의 최소값중에서 최대가 되는 값이 답이 된다. 

도착 위치는 distance로 주어지고, 출발 위치는 항상 0이다. 

만약 바위가 1개인데 위치가 5 라면, 바위 간 거리는 0~ 5,  5 ~ distance 를 비교한다. 

둘 중에 거리차이가 최대인게 답이다.

도착 위치 distance 는 1이상 1억 이하다. 따라서 이분탐색으로 범위를 빠르게 좁혀줘야 한다. 

이분 탐색의 대상은 '거리의 최소값' 이다. 

바위 위치 배열을 오름차순 정렬 하고, 거리의 최소값이 mid를 만족하는지 모든 바위에 대해 검사한다. 

바위 n개를 제거하면서, 모든 바위간의 거리의 최소값이 mid임을 만족해야 한다.

바위 간의 거리차이가 mid 미만이라면, 조건을 만족하니까 제거한 바위 카운팅을 증가시킨다. 

만약, 제거한 바위가 n개를 초과한다면, 거리의 최소값 mid 크기를 줄여야한다. 

n개 이상을 제거 해야 거리의 최소값이 mid 임을 만족시킨다는 의미이기 때문이다. 

"맞았습니다" 코드 

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

int solution(int distance, vector<int> rocks, int n) {

  sort(rocks.begin(), rocks.end()); // 오름차순 정렬
  int rlen = rocks.size(), answer = 0;
  int left = 0, right = distance;

  // 거리의 최소값이 mid 이하인지 검사한다.
  while(left <= right){
    int mid = (left + right ) /2; // 거리의 최소값
    int prev_idx = 0; // 직전 바위의 위치
    int remove_cnt = 0; // 제거한 바위 개수

    for(int i = 0; i < rlen; i++){
      if(rocks[i] - prev_idx < mid) { // 거리 차이가 mid 이하라면 제거한다.
        remove_cnt++;
      }else{
        prev_idx = rocks[i];
      }
    }
    // 도착지점과 마지막바위 간의 거리차이가 mid 이하라면 제거
    if(distance - prev_idx < mid) remove_cnt++;
    if(remove_cnt <= n) {
      answer = max(mid, answer); // n개 이하로 제거했다면, 거리의 최소값을 증가시켜본다.
      left = mid + 1;
    } else{
      right = mid - 1; // 거리의 최소값을 더 줄여본다.
    }
  }
  return answer;
}

도둑질 문제 링크 

리뷰 

인접한 두 집을 털면 경보가 울린다. 따라서 한 개 건너서 털어야 한다. 

집이 동그랗게 이어져있으니까, 첫번째 집을 털면 마지막 집은 털 수 없다. 

마지막 집을 털면 첫번째 집은 털 수 없다. 이걸 구분해서 DP 배열을 만들어야한다. 

첫 번째 집을 턴다 (== 마지막 집 못 턴다)

마지막 집을 턴다 (== 첫번째 집 못 턴다)

"맞았습니다"코드

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

int D1[1000001]; // 첫번째 집을 턴다
int D2[1000001]; // 첫번째 집 안털고, 마지막 집을 턴다.

int solution(vector<int> money) {
  int answer = 0;
  int msize = money.size();

  D1[0] = money[0]; // D1: 첫번째 집을 턴다.
  D1[1] = max(money[0], money[1]);

  D2[0] = 0;        // D2: 마지막 집을 턴다.
  D2[1] = money[1];

  for(int i = 2; i < msize-1 ; i++) { // 첫번째 집을 터니까 msize-2 까지 반복.
    D1[i] = max(D1[i-2] + money[i], D1[i-1]);
  }
  for(int i = 2; i < msize; i++) { // 마지막 집을 터니까 msize-1 까지 반복.
    D2[i] = max(D2[i-2] + money[i], D2[i-1]);
  }
  answer = max(D1[msize-2], D2[msize-1]);
  return answer;
}