JArchive 프로그래밍 일기

문제링크

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

수열의 시작 인덱스 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;
}

숫자의 표현 문제링크 

리뷰 

입력이 15일 때, 15 하나 자체도 표현 방법으로 친다. 

그래서 answer 는 1로 초기화한다. 

15를 2로 나눴을때의 몫 부터 연속된 수를 더해본다. 

15를 2로 나눴을때의 몫은 7이다. 

7부터 더해보고,

6부터 더해보고, 

5부터 더해보고, 

.... 

1부터 더해보고. 

15/2 부터 1까지 누적 덧셈을 시도한다. 더하다가 n과 똑같아지면 카운팅한다. 

맞았습니다 코드 

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

int solution(int n) {
  int answer = 1;
  int start = n/2;

  for(int i = start; i > 0; i--){ // start 부터 1 까지.
    int sum = i, j = i+1; // 합을 저장할 sum, 더해줄 숫자 j
    while(sum <= n){
      sum += (j++);
      if(sum == n) {answer++; }
    }
  }
  return answer;
}

JadenCase 문자열 만들기 문제링크

리뷰 

문자열에는 숫자도 공백문자도 포함되어 있다.

문자열을 하나씩 순회해서 문자마다 알파벳이 맞는지 확인하는 isalpha() 함수를 썼다. 이건 불필요한 작업이었다. 

공백이든 숫자든 toupper() 와 tolower() 에 영향을 받지 않고 에러도 안낸다..

공백과 연속된 문자를 대문자로 바꾸고, 나머지는 전부 lower 처리 하면 된다. 

맞았습니다 코드1

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

string solution(string s) {

  string answer = "";
  string space_delimiter = " ";
  int pos = 1;

  while(pos != string::npos){
    pos = s.find(space_delimiter);
    string w = s.substr(0, pos);

    if (isalpha(w[0])) { w[0] = toupper(w[0]); };
    for(int i = 1; i < w.size(); i++){
      if (isalpha(w[i])) { w[i] = tolower(w[i]); };
    }
    answer += (w + " ");
    s.erase(0, pos + space_delimiter.length());
  }
  answer = answer.substr(0, answer.size()-1);
  return answer;
}

더 짧은 맞았습니다 코드2

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

string solution(string s) {
  string answer = "";

  answer += toupper(s[0]);
  for(int i = 1; i < s.size(); i++){
    if(s[i-1] == ' '){ // 공백 뒤에 대문자
      answer += toupper(s[i]);
    }else{
      answer += tolower(s[i]);
    }
  }

  return answer;
}

문제 링크 

리뷰 

1이 나타나는 곳에서 1이 끝날때 까지의 길이를 세서 정사각형인지 확인하는 방법을 썼다. 

근데 테스트 케이스 몇개가 안되서 다른 방법이 필요했다. 

맞았습니다 코드 

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

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

  for(int i = 1; i < h; i++){
    for(int j = 1; j < w; j++){
      if(board[i][j] == 1){
        // 오른쪽, 아래, 대각선의 최소값을 구하고, 1을 더한다.
        board[i][j] = 1 + min({board[i-1][j-1], board[i][j-1], board[i-1][j]});
        answer = max(board[i][j], answer);
      }
    }
  }
  return answer * answer;
}

지도 자동 구축 문제 링크 

리뷰 

점 개수가 늘어나는 규칙보다는 전체 개수의 규칙을 셌다. 

0단계에서 한 변의 점 개수는 2개다. 

1단계에서 한 변의 점 개수는 3개다. 

2단계 에서는 5개, 3 단계에서는 9개가 된다. 

사각형의 전체 점 개수는 한 변의 점 개수의 제곱이다. 

2, 3, 5, 9  ==>  2의 0승 1승 2승 만큼 증가한다.  여기서 DP를 이용해 짰다. 

맞았습니다 코드 

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

int n;
ll D[10];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  D[0] = 2, D[1] = 3;
  ll addnum = 1;
  for(int i =2; i <= n; i++){
    addnum *= 2;
    D[i] = D[i-1] + addnum;
  }
  cout << D[n] * D[n];
  return 0;
}

제출기록

우물 안 개구리 문제 링크 

리뷰 

힘을 저장하는 배열 power 과, 최고라고 생각한다/안한다 를 저장하는 iambest 배열을 따로 만들었다. 

처음에는 모두 다 '나는 최고'라고 생각하도록 iambest를 1로 초기화 했다. 

친분관계를 순회하면서 자신보다 힘쎈 사람인지 power 배열 값으로 비교한다. 

힘이 같거나 힘이 약하면 iambest 값을 0 으로 바꾼다. 

마지막에 iambest 가 1인 사람만 카운팅 해서 답을 낸다. 

코드를 짜고 나니깐 이차원 배열로 해도 상관없을 것 같다는 생각이 들었다. 

맞았습니다 코드 

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

int n, m, a, b, answer;

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

  cin >> n >> m;

  vector<bool> iambest(n+1, 1);
  vector<int> power(n+1, 0);

  for(int i = 1; i <= n; i++) cin >> power[i];

  while(m--){
    cin >> a >> b;
    if(power[a] < power[b]){
      iambest[a] = 0;
    }else if(power[a] > power[b]){
      iambest[b] = 0;
    }else{
      iambest[a] = 0;
      iambest[b] = 0;
    }
  }
  // 아직 1인 사람(최고라고 생각) 카운팅
   for(int i = 1; i <= n; i++) if (iambest[i] > 0) answer++;
   
  cout << answer;
  return 0;
}

제출 기록