JArchive 프로그래밍 일기

압축 문제 링크 

리뷰 

사전에는 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;
}

프로그래머스 튜플 문제 링크 

리뷰 

입력이 문자열로 주어지는데, 괄호와 콤마가 섞인 숫자가 있는 문자열이다. 

"{{2},{2,1},{2,1,3},{2,1,3,4}}"

문자열 내에 숫자 그룹이 4개다. 이걸 4개의 그룹으로 구분해야 한다고 생각해서 2차원 벡터를 선언했다. 

그런데 풀다보니 map으로 각 숫자의 개수를 센다. -> 2 4개, 1 3개, 3 2개, 4 1개 

개수가 많은 숫자부터 출력하면 답이 된다. 

sort() 함수에 비교함수 cmp 를 넣어서 pair.second 개수를 기준으로 내림차순 정렬을 했다. 

따로 2차원 벡터로 구분할 필요가 없어서 두 번째 코드는 int 배열에 모든 숫자를 넣고 map으로 숫자의 개수를 셌다. 

"맞았습니다" 코드 1 

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

bool cmp(pair<int,int> &a, pair<int,int> &b){
  return a.second > b.second;
}
vector<int> solution(string s) {
  vector<int> answer;
  map<int,int> tuple_map; // {숫자, 숫자의 개수}
  int slen = s.size();

  // 2차원 벡터 선언 
  vector<vector<int>> v(500, vector<int>());
  int v_num = 0; // {그룹 번호 == 벡터의 행 번호 }
  
  string s_num;

  for(int i = 1; i < slen-1; i++){
    
    if(isdigit(s[i])) s_num += s[i]; // 숫자라면, s_num 문자열에 이어붙인다.

    else if(!s_num.empty()){ // 숫자가 아닌게 나오면 벡터에 푸시하고 문자열 초기화
      v[v_num].push_back(stoi(s_num));
      s_num = "";
      
      if(s[i] == '}') v_num++; // 닫는 괄호 }가 나오면, 그룹 하나가 끝난거니까 벡터의 행을 증가시킴
    }
  }

  for(int i = 0; i < v_num; i++){ // 숫자 마다의 개수를 센다 
    for(int j = 0; j < v[i].size(); j++){
      tuple_map[v[i][j]]++;
    }
  }

  vector<pair<int,int>> pv(tuple_map.begin(), tuple_map.end());
  sort(pv.begin(), pv.end(), cmp); // '개수'기준으로 내림차순 정렬 

  for(int i = 0; i < pv.size(); i++) answer.push_back(pv[i].first);
  return answer;
}

"맞았습니다" 코드 2 

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

bool cmp(pair<int,int> &a, pair<int,int> &b){
  return a.second > b.second;
}
vector<int> solution(string s) {
  vector<int> answer;
  string s_num;

  for(char ch : s){

    if(isdigit(ch)) s_num += ch; // 숫자라면, s_num 문자열에 이어붙인다.

    else if(!s_num.empty()){ // 숫자가 아닌게 나오면 벡터에 푸시하고 문자열 초기화
      answer.push_back(stoi(s_num));
      s_num = "";
    }
  }
  map<int,int> tuple_map;
  for(int i = 0; i < answer.size(); i++){
    tuple_map[answer[i]]++;
  }
  answer.clear();

  vector<pair<int,int>> pv(tuple_map.begin(), tuple_map.end());
  sort(pv.begin(), pv.end(), cmp);
  for(int i = 0; i < pv.size(); i++) answer.push_back(pv[i].first);

  return answer;
}

약수의 개수와 덧셈 문제 링크 

리뷰 

숫자 범위가 1000 이하다. n의 약수는 n을 1부터 n까지 나눴을 때, 나머지가 0인 수이다. 

1과 자기자신 n은 약수에 항상 포함된다. 

"맞았습니다"코드 

#include <string>
#include <vector>

using namespace std;
bool check(int n){
  int cnt = 0;
  for(int i =1; i <= n; i++) {
    if(n % i == 0) cnt++;
  }
  return (cnt % 2 == 0)? 1 : 0;
}
int solution(int left, int right) {
  int answer = 0;

  for(int i = left; i <= right; i++){
    if(check(i)) answer += i;
    else answer -= i;
  }
  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;
}

수열 2559번 문제링크 

연속된 k개의 합을 구하되, 최대 합을 답으로 내는 문제다.

항상 k개여야 하니까, 시작 인덱스 0, 끝 인덱스 k-1 의 합으로 시작한다.

길이가 일정한 누적합이기 때문에, 시작 인덱스와 끝 인덱스만 바뀐다. 투포인터 문제다. 

k= 3 이라면,  아래 처럼 인덱스가 일정하게 증가한다. 

시작0 ~ 끝2,  시작1 ~ 끝3, 시작2 ~ 끝4

현재 시작인덱스의 값을 빼주고, 현재 끝인덱스 +1 의 값을 더해주면 된다. 

"맞았습니다"코드 링크 

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

int n, k, start_idx, end_idx;
long long sum, sum_temp;

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

  cin >> n >> k;
  vector<int> v(n); 
  for(int i = 0; i < n; i++) cin >> v[i]; // 입력받기 끝 

  // 인덱스 0부터 k-1까지 k개의 합 
  for(int i = 0; i < k; i++) sum_temp += v[i];
  start_idx = 0, end_idx = k-1; 

  sum = sum_temp;
  
  while(end_idx < n){ 
    sum_temp -= v[start_idx++]; // 현재 인덱스 값 빼기, 인덱스 증가
    if(end_idx + 1 == n) break;
    sum_temp += v[++end_idx];   // 인덱스 증가시킨 후 그 인덱스 값 더하기
    sum = max(sum_temp, sum);
  }
  cout << sum;
  return 0;
}