JArchive 프로그래밍 일기

문제

국영수 백준 10825

"맞았습니다."코드

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

struct student{
  string name;
  int kor, eng, math;
};

int n, kor, eng, math;
string st;
vector<student> v;

bool cmp(student &a, student &b){
  if(a.kor == b.kor && a.eng == b.eng && a.math == b.math) return a.name < b.name;
  else if(a.kor == b.kor && a.eng == b.eng) return a.math > b.math; // 수학 감소하는 순서
  else if(a.kor == b.kor) return a.eng < b.eng; // 영어 증가하는 순서
  else return a.kor > b.kor; //국어 감소하는 순서
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> st >> kor >> eng >> math;
    student s = {st, kor, eng, math};
    v.push_back(s);
  }
  sort(v.begin(), v.end(), cmp);
  for(auto i : v) cout << i.name << '\n';
  return 0;
}

리뷰

비교 함수를 정확히 구현해야 맞을 수 있는 문제였다.
비교 함수를 작성할 때 조건이 구체적인 것 부터 걸러내야 한다.
그래서 '모든 점수가 같으면' 이름이 사전순 증가 하게 출력하라는 조건부터 if문을 시작해야 한다.
문제에서 나오는 조건 대로 작성했다가 처음 풀었을 때 틀렸다.

문제

접미사 배열 11656

"맞았습니다"코드

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

string st;
vector<string> v;

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

  cin >> st;
  int stringlen = st.length();
  for(int i = 0; i < stringlen; i++) {
    string temp = st.substr(i);
    v.push_back(temp);
  }
  sort(v.begin(), v.end());
  for(auto i : v) cout << i << '\n';
  return 0;
}

리뷰

substr() 함수로 문자열의 특정 인덱스부터 끝까지 잘라냈다.

substr(2) = 2부터 끝까지 잘라내기
substr(2,5) = 2부터 5개 잘라내기

c++ 문자열 추출 substr 함수

문제

1로 만들기 1463

"맞았습니다"코드

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

int arr[1000005];
int x;

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

  cin >> x;
  arr[2] = 1; arr[3] = 1;
  for(int i = 4; i <= x; i++){
    arr[i] = arr[i-1]+1;
    if(i%3 == 0) arr[i] = min(arr[i], arr[i/3] + 1);
    if(i%2 == 0) arr[i] = min(arr[i], arr[i/2] + 1);
  }
  cout << arr[x];
}

리뷰

관찰이 필요한 DP문제다.

arr[i] = i를 1로 만들기 위해 필요한 연산 횟수의 최솟값

D[12]를 구할 때 어떤 과정인지, D[10]을 구할때 어떤 과정인지 구해보면 아이디어를 얻을 수 있었다.
3가지 연산 중에 최소 값을 찾아서 갱신해주면 된다.

1을 1로 만드는데 연산은 0번 필요하다. D[1] = 0
2를 1로 만드는데 연산은 1번 필요하다.(2로 나누거나 1을 빼기) D[2] = 1
이 문제에서는 D[1] 초기값만 정해주면 된다.

참고) 이 문제는 BFS로도 해결할 수 있다. dist 배열을 두고 초기값을 1로 한 뒤, x2, x3, +1로 뻗어나가면 답이 나온다.

문제

먹을 것인가 먹힐 것인가 백준 7795

"맞았습니다."코드

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

int tc, n, m, num;
vector<int> a, b;
int solve(){

  int answer = 0;
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  for(int i = a.size()-1; i >= 0; i--){
    for(int j = b.size()-1; j >= 0; j--){
      if(a[i] > b[j]) {
        answer += j + 1;
        break;
      }
    }
  }
  return answer;
}

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

  cin >> tc;
  while(tc--){
    cin >> n >> m;
    a.clear(); b.clear();
    while(n--) { cin >> num; a.push_back(num); }
    while(m--){ cin >> num; b.push_back(num); }
    cout << solve() << '\n';
  }
  return 0;
}

리뷰

main 함수에서는 입력만 받았고. 핵심은 solve() 함수이다.
벡터 a와 b를 각각 정렬한다.

a의 가장 큰 수와 b의 가장 큰 수를 비교한다.
a[i] > b[j] 라면, b의 모든 수를 a[i]가 먹을 수 있다. 따라서 바로 answer를 증가시키고 break;한다.

그 다음 두 번째로 큰 숫자 a[i]와 b의 가장 큰 수를 비교한다.
a[i] > b[j] 를 만족하지 못하면, b의 인덱스 j를 감소시키면서 먹을 수 있을 때 까지 순회한다.
먹을 수 있는 크기가 나타나면 j+1만큼 크기를 answer에 더해준다.

문제

빈도 정렬 백준 2910

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int n, c, num;
map<int,int> idxm; // {숫자, 처음 나온 인덱스} 저장
map<int,int> recentm; // {숫자, 빈도} 저장
vector<pair<int,int>> v;

bool cmp(pair<int,int> a, pair<int,int> b){ // 빈도 내림차순, 인덱스 오름차순
  if(a.X == b.X) return idxm[a.Y] < idxm[b.Y];
  return a.X > b.X;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> c;
  for(int i = 0; i < n; i++){
    cin >> num;
    recentm[num]++; // num의 빈도를 1 증가시킨다
    if(idxm[num] == 0 ){ // num이 처음 나왔다면, 인덱스를 저장한다.
      idxm[num] = i+1;
    }
  }

  // recentm {숫자, 빈도} -> {빈도, 숫자} 로 바꿔서 벡터에 저장
  for(auto & it : recentm){
    v.emplace_back(it.Y, it.X);
  }

  // 빈도를 기준으로 정렬하되, 인덱스 조건 고려하여 정렬하도록 cmp 함수 적용
  sort(v.begin(), v.end(), cmp);

  for(int i = 0; i < v.size(); i++){ // 숫자의 빈도(== v[i].X)만큼 숫자를 출력.
    for(int j = 0; j < v[i].X; j++){
      cout << v[i].Y << ' ';
    }
  }
  return 0;
}

리뷰

처음에는 벡터만을 생각해서 풀어서 감이 안오고 어렵게 느껴졌다.
key의 중복을 허용하지 않는 map을 이용해서 풀었다.

처음에 입력 받을 때 2개의 맵을 초기화한다.
(숫자, 빈도)를 저장하는 recentm map에 빈도를 저장한다.
(숫자, 숫자가 처음 나온 인덱스)를 저장하는 idxm map에 '숫자가 처음 등장한 인덱스'를 저장한다.

인덱스가 0이면 '처음 나왔다' 고 보기 때문에. 1+i를 인덱스로 저장했다.

빈도가 가장 많은 숫자가 앞에 와야 하니까 정렬이 필요하다.
map recentm {숫자, 빈도} 을 vector v {빈도, 숫자}로 바꿔서 저장한다.

여기서 vector.emplace_back()을 썼는데. vector.push_back()과 동일한 기능이다.

push_back() 과 달리 emplace_back()는 데이터를 삽입할 때 임시 객체를 생성하지 않아서 약간 더 빠르다고 한다.

빈도가 같은 경우에, '숫자가 처음 등장한 인덱스'가 작은것을 우선하라는 조건을 주기 위해 cmp 비교 함수를 넣고 sort() 한다.

정렬이 끝나면, 숫자를 '숫자의 빈도'만큼 출력해주면 되니까 이중 반복문으로 vector 를 순회하여 출력한다.

iterator로 순회하는 반복문 코드 2가지 형태를 배웠다.

  map<int,int> recentm; // {숫자, 빈도} 저장

  // 아래 2개 반복문은 똑같이 동작한다. 
  for(auto & it : recentm)

  for(auto it = recentm.begin(); it != recentm.end(); it++) 
}

문제

단어 정렬 백준 1181

"맞았습니다."코드

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

int n;
string st;
vector<string> v;

bool cmp(string &a, string & b){
  if(a.size() != b.size()) return a.size() < b.size(); // 길이 짧은것 우선
  else return a < b; // 사전순
}

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

  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> st;
    v.push_back(st);
  }
  sort(v.begin(), v.end(), cmp);
  v.erase(unique(v.begin(), v.end()), v.end());
  for(auto i : v) cout << i << '\n';
  return 0;
}

리뷰

중복을 제거하는 것은 unique와 erase를 썼는데 이번에 풀면서 배웠다.
unique 를 쓰면 중복은 제거되도 벡터의 크기가 줄어들지는 않는다. unique는 중복되는 원소의 포인터를 맨 뒤로 보내기 때문이다.
unique의 리턴 값은 중복 제거 된 원소의 포인터다.
그래서 erase로 중복 제거된 원소의 포인터 부터 맨 마지막 포인터까지 공간을 삭제해준다.
erase를 하면 아예 메모리가 해제되니까 중복된 부분의 크기만큼 반환되는 것이다.

c++ 벡터 중복 제거 unique와 erase 포스팅

문제

수 정렬하기5 백준 15688

"맞았습니다" 코드

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

int n, num;
int arr[2000002];

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

  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> num;
    arr[num+1000000]++;
  }

  for(int i = 0; i <= 2000000; i++) {
    while(arr[i] > 0) {
      cout << i-1000000 << '\n';
      arr[i]--;
    }
  }

  return 0;
}

리뷰

절대값이 100만 이하인 정수가 입력으로 들어오니까.
양수 음수 처리를 따로 해야겠다고 생각했었다.
일단 정답 코드를 제출하고 다른 분의 코드를 봤다.
200만 크기의 배열을 쓰면서도 어차피 입력받은 대로 더하고 빼주고 하면 입력 받은 숫자를 출력할 수 있으니까.
입력받을 때 저장하는 인덱스 : num + 1000000
출력할 때 숫자 : num - 1000000
이렇게 하면 충분했다.

나의 예전 코드

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

int n, num;
int arr[2000002];

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

  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> num;
    if(num < 0) arr[abs(num)+1000000]++;
    else arr[num]++;
  }

  for(int i = 2000000; i > 1000000; i--) {
    while(arr[i] > 0) {
      int temp = abs(i-1000000) * (-1);
      cout << temp << '\n';
      arr[i]--;
    }
  }
  for(int i = 0; i <= 1000000; i++) {
    while(arr[i] > 0) {
      cout << i << '\n';
      arr[i]--;
    }
  }

  return 0;
}