JArchive 프로그래밍 일기

문제 링크 

리뷰 

처음에 이중 for문으로 하다가 시간초과나서 틀렸다. 

left 부터 right까지의 인덱스 찾기

일차원 배열일 때, 행 하나씩 0,1,2,3,4,5 의 연속적인 값의 인덱스를 갖는다. 

해당 인덱스의 값 찾기

n = 4 일 때 , 1, 2, 3, 4 값을 가지는 칸은 이중 for문으로 이차원 배열을 순회할 때의 (i, j) 좌표를 떠올리자. 

i와 j를 비교했을 때, 큰 값을 '값'으로 가진다. 

맞았습니다 코드 

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

vector<int> answer;
vector<int> v;
vector<int> solution(int n, long long left, long long right) {

  for(ll i = left; i <= right; i++){
    answer.push_back(1+ max(i / n, i % n));
  }
  return answer;
}

입국심사 문제 링크 

리뷰 

이분 탐색은 원소들이 정렬된 상태에서 탐색이 가능하므로 sort() 해준다. 

처음에 틀린 부분은, 데이터 타입 때문이다.

이분 탐색의 시작시간과 종료시간 초기화에서 long long 으로 초기화가 안되어 있어서 틀렸다. 

함수의 파라미터 n과 벡터 times는 전부 int 형이다. 

탐색의 최대시간을 초기화할 때, int 벡터의 마지막 인덱스 값을 참조하니까, 따로 (long long)형변환을 해줘야 한다. 

long long solution(int n, vector<int> times) {

  long long max_time = (long long)times[size_of_times-1] * n; // 가장 오래걸리는 시간
}

아래 코드처럼 짜면, max_time변수가  int 곱하기 int 값으로 초기화 된다.

그래서 max_time이 int 형이 된다.  

long long solution(int n, vector<int> times) {

  long long max_time = times[size_of_times-1] * n; // 가장 오래걸리는 시간
}

심사할 사람의 최소값은 1명. 심사 시간 최소값은 1분이다.

따라서 탐색의 최소 시간 min 은 1 이다. 

심사할 사람의 최대값 1,000,000,000명. 심사 시간 최대값은 1,000,000,000분이다. 

심사 시간 최대값 max는 주어진 배열에서 가장 큰 숫자로 초기화 한다.

min,max의 중간값 mid 시간에 n명을 다 처리할 수 있는지 계산한다.

mid 시간 동안 각 심사대는 몇 명을 처리할 수 있는지 계산해서 ( mid_time / times[i] ) man_cnt에 센다.

주어진 시간 안에 man_cnt명을 처리했을 때 n보다 크거나 같아야 한다.

이 때의 mid값이 최소 이면 answer에 저장한다. 

맞은 코드 (테스트케이스 10개 중 10개 O)

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

long long solution(int n, vector<int> times) {

  int size_of_times = times.size();
  sort(times.begin(), times.end());

  long long min_time = 1L; // 가장 짧은 시간
  long long max_time = (long long)times[size_of_times-1] * n; // 가장 오래걸리는 시간
  long long mid_time = (min_time + max_time) / 2; // 중앙값
  long long answer = max_time;

  while(min_time <= max_time){

    mid_time = (min_time + max_time) / 2;
    long long man_cnt = 0;
    for(auto t : times) { // mid_time 동안 처리할 수 있는 사람 수를 센다.
      man_cnt += mid_time / t;
    }

    if(n <= man_cnt){
      answer = min(answer, mid_time);
      max_time = mid_time - 1;
    }
    else {
      min_time = mid_time + 1; // 시간이 부족
    }
  }
  return answer;
}

틀린 코드  (테스트케이스 10개 중 9개 O)

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

long long solution(int n, vector<int> times) {

  int size_of_times = times.size();
  sort(times.begin(), times.end());

  long long min_time = 1L; // 가장 짧은 시간
  long long max_time = times[size_of_times-1] * n; // 가장 오래걸리는 시간
  long long mid_time = (min_time + max_time) / 2; // 중앙값
  long long answer = max_time;

  while(min_time <= max_time){

    mid_time = (min_time + max_time) / 2;
    long long man_cnt = 0;
    for(auto t : times) { // mid_time 동안 처리할 수 있는 사람 수를 센다.
      man_cnt += mid_time / t;
    }

    if(n <= man_cnt){
      answer = min(answer, mid_time);
      max_time = mid_time - 1;
    }
    else {
      min_time = mid_time + 1; // 시간이 부족
    }
  }
  return answer;
}

이중우선순위큐 문제링크 

리뷰 

최소값 삭제와 최대값 삭제를 위해 매번 큐의 정렬을 다시 할 수 는 없다. 그래서 우선순위큐 2개를 뒀다. 

우선순위큐의 기본 정렬은 less라서 오름차순이다. 

오름차순 정렬하는 최소값 큐 min_pq

내림차순 정렬하는 최대값 큐 max_pq 

큐 사이즈를 관리하는 변수가 0이 되면, 큐 2개 다 비워줘야하는데! 이 부분을 빠뜨려서 다른 분 코드를 참고했다. 

1. priority_queue 2개 사용한 코드 

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

priority_queue<int, vector<int>, greater<>> min_pq;
priority_queue<int, vector<int>, less<>> max_pq;
int pq_size; // 큐의 사이즈 관리

vector<int> solution(vector<string> op) {
  vector<int> answer = {0, 0};

  for(auto s : op){
    string order = s.substr(0, 1); // 명령 문자 I 또는 D 

    int num = stoi(s.substr(2, s.size())); // 숫자부분  

    if(order == "I") {
      min_pq.push(num);
      max_pq.push(num);
      pq_size++;
    }
    else if(pq_size > 0 && order == "D"){

      (num == -1) ? min_pq.pop() : max_pq.pop();
      pq_size--;

      if(pq_size == 0){
        while(!min_pq.empty()) min_pq.pop();
        while(!max_pq.empty()) max_pq.pop();
      }
    }
  }

  if(!min_pq.empty() && !max_pq.empty()) answer = {max_pq.top(), min_pq.top()};
  return answer;
}

풀고 나니깐 다른 분들 코드에 set이 보이길래 multiset으로 풀어도 됬겠다 싶었다.  

2. vector 로 푼 코드 

앞, 뒤에서 하나씩 erase로 지워주기만 하면 되니까. vector로도 괜찮다. 

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

vector<int> solution(vector<string> op) {
  vector<int> answer = {0,0};
  vector<int> v;

  for(auto s : op){
    string order = s.substr(0, 1); // 명령
    int num = stoi(s.substr(2)); // 숫자

    if(order == "I") {
      v.push_back(num);
      sort(v.begin(), v.end(), greater<>()); // 푸시하고 바로 정렬.
    }
    else {
      if(v.size() == 0) continue;

      (num == -1) ? v.erase(v.end()-1) : v.erase(v.begin());
    }
  }

  if(!v.empty()) {
    answer.clear();
    answer = {v[0], v[v.size()-1]};
  }
  return answer;
}

정수 삼각형 문제 링크 

리뷰 

등굣길 문제와 비슷하게 느껴졌다. 

삼각형의 가로 세로는 500이하라는 조건이 있으니까 점화식 값을 저장할 DP배열 크기를 501, 501로 잡아둔다. 

최대 합을 구하려면, 반드시 1층부터 마지막층까지 이동해야 한다. 

모든 층의 첫번째 칸은 바로 위에서만 올 수 있다. 

모든 층의 마지막 칸은 왼쪽 위에서만 올 수 있다. 

이 2가지 예외를 제외하고, 아래와 같은 점화식을 만족한다. 

D[a][b] = max(D[a-1][b] , D[a][b-1]) + 현재칸의 값 A[a][b]

맞았습니다 코드 

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

int D[501][501];

int solution(vector<vector<int>> t) {
  int answer = 0;

  D[0][0] = t[0][0];
  D[1][0] = t[1][0] + D[0][0];
  D[1][1] = t[1][1] + D[0][0];

  int height_t = t.size();

  for(int i = 2; i < height_t; i++){

    for(int j = 0; j <= i; j++){
      if(j == 0) D[i][j] = t[i][j] + D[i-1][j];
      else if(j == i) D[i][j] = t[i][j] + D[i-1][i-1];
      else{
        D[i][j] = t[i][j] + max(D[i-1][j], D[i-1][j-1]);
      }
    }
  }

  for(int i = 0; i < height_t; i++){
    answer = max(answer, D[height_t-1][i]);
  }

  return answer;
}

등굣길 문제링크 

리뷰 

최단 경로를 세야 하니까 오른쪽 또는 아래로만 이동해야 한다. 

그래서 특정 지점까지 몇번을 거쳐 가는지 점화식을 세야 한다. 

웅덩이가 있으면 최단경로를 세면 안되니까 처음부터 -1로 초기화 해둔다. 

현재 지점 기준으로 위, 또는 왼쪽의 최단경로를 기반으로  현재 지점의 최단경로를 계산한다. 

인덱스에 음수가 발생하지 않도록 (1, 1)을 시작점으로 두고 (1, 1)의 최단경로를 1로 초기화한다. 

핵심 코드는 아래와 같다

temp_a = (위칸이 음수가 아니라면, ) D[a-1][b] 
temp_b = (왼쪽칸이 음수가 아니라면, ) D[a][b-1] 

D[a][b] = (temp_a + temp_b) % div_num;

맞았습니다 코드 

#include <string>
#include <vector>

using namespace std;
int D[101][101]; // 최단거리를 저장할 배열
int div_num = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {

  for(auto v : puddles){
    D[v[1]][v[0]] = -1; // 물웅덩이를 -1로 초기화
  }
  D[1][1] = 1;

  for(int i = 1; i <= n; i++){ // n: 행
    for(int j = 1; j <=m; j++){ // m: 열
      if(D[i][j] == -1) continue;
      int temp_a = 0, temp_b = 0;

      if(D[i-1][j] != -1) temp_a = D[i-1][j];
      if(D[i][j-1] != -1) temp_b = D[i][j-1];

      D[i][j] += (temp_a + temp_b) % div_num;
    }
  }

  return D[n][m];
}

문제 링크 

리뷰 

처음에 감을 못잡은 문제... 어떤 파라미터 넘겨서 탐색해야되지? 다음에 다시 풀어봐야겠다. 

맞았습니다 코드 

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

int global_N, target_number;
int max_cnt = 8;
int min_cnt = 1 + max_cnt;

void dfs(int cur_num, int cnt){ // (현재 숫자, N을 사용한 개수)
  if(cnt > max_cnt) return;
  else if(cur_num == target_number){
    min_cnt = min(cnt, min_cnt);
    return;
  }

  int n = 0;  // 계산할 숫자 n 
  for(int i = 1; i <= 6; i++){ // N을 1개~6개 사용가능
    // 계산할 숫자 n -> N, NN, NNN
    n = n*10 + global_N;
      
    dfs(cur_num + n, cnt + i);
    dfs(cur_num - n, cnt + i);
    if(cur_num != 0 || cnt > 8){
      dfs(cur_num * n, cnt + i);
      dfs(cur_num / n, cnt + i);
    }
  }
}

int solution(int N, int number) {
  global_N = N;
  target_number = number;
  dfs(0, 0);
  return (min_cnt == 9) ? -1 : min_cnt;
}

문제 링크 

리뷰 

항상 가장 작은 수와, 그 다음 작은 수가 필요해서 자동으로 정렬해주는 우선순위 큐를 이용했다. 

우선순위 큐에서 front()를 first로 받고, pop()후에 front()를 second로 받으면 쉽게 접근할 수 있다. 

항상 2개를 꺼내니까 pop()을 2번 해줘야하는 것을 유의하자. 

전부 스코빌지수가 K가 됬는지는 큐의 크기가 1이 됬을 때 검사한다. 

마지막 남은 원소가 K 미만이라면 answer 는 실패다. 

맞았습니다 코드 

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

int solution(vector<int> scoville, int K) {
  int answer = 0;
  bool result = true;

  priority_queue<int, vector<int>, greater<int>> pq;

  for(auto s : scoville){ pq.push(s); }

  while(!pq.empty()){

    if(pq.top() > K) break; // 더 검사하지 않아도 된다
    if(pq.size() == 1 && pq.top() < K) { result = false; break; } // 실패

    int first = pq.top();
    pq.pop();
    int second = pq.top();
    pq.pop();

    pq.push(first + (second * 2));
    // cout << "first: " << first << " second:" << second << ' ';
    answer++;
  }
  if(!result) answer = -1;
  return answer;
}

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

  int k = 7;
  vector<int> scofille = {1, 2, 3, 9, 10, 12};
  cout << solution(scofille, k);

  return 0;
}