JArchive 프로그래밍 일기

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

리뷰 

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

"{{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;
}

문제링크

연속된 수들의 합을 구해야한다.

수열의 시작 인덱스 a와 마지막 인덱스 b 를 두고 합이 m이 나오면 개수를 세준다. 

인덱스 a와 b는 같을 수 있다. b는 수열 길이 n 직전까지 증가한다.

계속 다른 수열합을 확인해야 하니까 a와 b 인덱스는 계속 증가한다.

단, a가 b보다 큰 인덱스가 되면 안된다.  a <= b  여야 한다. 

누적 합 sum이 m보다 작다면, 수열의 마지막 인덱스 b를 증가시킨다. 

누적 합 sum이 m보다 크다면, 수열의 시작 인덱스 a를 증가시킨다. 

맞았습니다 코드 링크 

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

ll a, b, sum, n, m, answer;
int arr[10005];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n; i++ ) cin >> arr[i];

  sum = arr[a];
  while(b < n && a <= b){
    if(sum <= m){
      if(sum == m) answer++;
      sum += arr[++b];
    }else { // sum > m
      sum -= arr[a++];
      if(a > b){
        b = a;
        sum = arr[a];
      }
    }
  }
  cout << answer;
  return 0;
}

이진 변환 반복하기 문제링크

리뷰 

0제거 개수

문자열에서 0을 제거할 때 카운팅하고, 1이면 새로운 string에 이어붙였다.

이진수 변환 횟수

2로 나눈 나머지를 문자로 바꿔서 새로운 string에 이어붙였다. 

맞았습니다 코드 

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

vector<int> solution(string s) {
  vector<int> answer(2, 0);

  while(s != "1"){
    string temp = "";

    for(int i = 0; i < s.size(); i++){ 
      if (s[i] == '0') answer[1]++; // 제거한 0의 개수 세기
      else temp += "1";
    }
    int c = temp.size(); // temp의 길이 c
    string c_st = "";
    
    while(c > 0){ 
      c_st += to_string(c % 2);
      c /= 2;
    }
    answer[0]++; // 이진 변환 횟수 카운팅
    reverse(c_st.begin(), c_st.end()); // 이진수를 s에 대입
    s = c_st;
  }
  
  return answer;
}