JArchive 프로그래밍 일기

문제 링크 

맞았습니다 코드 

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

bool cmp(vector<int> &a, vector<int> &b){
  return a[2] < b[2];
}
int get_parent(vector<int> &parent, int x){
  // 부모노드가 자신이라면 자신을 리턴
  if(parent[x] == x) return x;
  // 부모노드가 자신이 아니라면, 최상위 부모 찾기
  return parent[x] = get_parent(parent, parent[x]);
}

void union_parent(vector<int> &parent, int a, int b){
  a = get_parent(parent, a);
  b = get_parent(parent, b);
  // 작은 노드쪽의 부모로 병합
  a < b ? parent[b] = a : parent[a] = b;
}
bool find(vector<int> &parent, int a, int b){
  a = get_parent(parent, a);
  b = get_parent(parent, b);
  return a == b; // 비교 내용을 리턴, 사이클 방지용
}
// 크루스칼 알고리즘 : 비용이 적은 순으로 costs 정렬
int solution(int n, vector<vector<int>> costs) {
  int answer = 0, maxNum = 0;

  sort(costs.begin(), costs.end(), cmp);
  for(auto c : costs) if(maxNum < c[1]) maxNum = c[1];

  vector<int> parent; // i번째 노드의 부모노드를 저장하는 parent 벡터
  for(int i = 0; i <= maxNum; i++) parent.push_back(i);

  for(auto c : costs){
    // 두 개의 부모 노드가 다르다면 (사이클 없다면)
    if(!find(parent, c[0], c[1])){
      answer += c[2]; // 결과에 가중치 추가
      union_parent(parent, c[0], c[1]); // 부모노드 병합
    }
  }
  return answer;
}

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

  int n = 4;
  vector<vector<int>> costs{{0,1,1}, {0,2,2}, {1,2,5}, {1,3,1}, {2,3,8}};
  cout << solution(n, costs);

  return 0;
}

문제 링크 

"맞았습니다" 코드 

#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>

using namespace std;

map<string, int> report_cnt; // 유저별 신고당한 횟수
unordered_map<string, set<string>> report_map; // 유저별 신고한 타 유저 리스트

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
  vector<int> answer;

  for(string s : report){
    int blank = s.find(' ');
    string from = s.substr(0, blank);
    string to = s.substr(blank);

    if(report_map[from].find(to) == report_map[from].end()){
      report_cnt[to]++; // to 가 신고당한 횟수
      report_map[from].insert(to); // from 이 to를 신고함
    }
  }
  for(string s : id_list){
    int res = 0;
    for(string target : report_map[s]){ // 유저 s가 신고한 타겟들
      if(report_cnt[target] >= k) res++; // 타겟이 신고당한 횟수가 k이상이면? res를 증가시킴
    }
    answer.emplace_back(res);
  }
  return answer;
}

문제

구명보트 프로그래머스 level2

리뷰

이 문제의 핵심은 1명 또는 2명의 사람만 태울 수 있다는 것이다.

왜냐하면 제한사항이 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지기 때문이다.

맨 앞을 가리키는 인덱스 변수와 맨 뒤를 가리키는 인덱스 변수를 둔다.

그리고 people 벡터를 정렬 한다.

int front = 0; // 맨 앞 인덱스 
int back = people.size() - 1;  // 맨 뒤 인덱스 

sort(people.begin(), people.end()); // 오름차순 정렬 [50, 50, 70, 80]  

양 끝 인덱스의 사람 무게 합이 무게제한보다 작다면,

양 끝 인덱스를 증가 및 감소시킨다. (front 증가 , back 감소 )

// 인덱스 변화 :  앞에서는 증가, 뒤에서는 감소 
if (people[front] + people[back] <= limit && (back-front >= 1) ) { 
    front++; back--;  
    // 2명을 태워 보낸 셈이니까 인덱스 차이가 (back-front >= 1)  만족해야 함.
}
else { // 뒤에 큰 값만 제거 
    back--;
}

코드

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

int solution(vector<int> people, int limit) {

    int answer = 0; 
    int front = 0; // 맨 앞 인덱스 
    int back = people.size() - 1;  // 맨 뒤 인덱스 

    sort(people.begin(), people.end()); // 오름차순 정렬 

    while (front <= back) { //  양 끝 인덱스가 만날 때 까지 

        if (people[front] + people[back] <= limit && (back-front >= 1) ) {
            front++; back--;  // 인덱스 변화 :  앞에서는 증가, 뒤에서는 감소 
        }
        else { // 뒤에 큰 값만 제거 
            back--;
        }
        answer++;
    }

    return answer;
}

문제

징검다리 건너기 프로그래머스 level3

리뷰

완전 탐색으로 푸니까 정확도100점, 효율성0점이 나왔다.

1씩 돌의 숫자를 감소시키다보면, 돌 최대 개수가 20만개니까 시간초과가 날 수 밖에 없다. 어려웠다..

다른 분들 풀이를 보니 이분탐색이라는 힌트가 있었다.

다리 건너는 사람 수를 돌에 써있는 숫자의 최소값과 최대값을 가지고 탐색하는 것이다.

// 다리를 건너는 사람 수를 탐색 
int front = 1;
int back = *max_element(stones.begin(), stones.end()); // 범위 내의 최대값 #include <algorithm> 

// 이분탐색 
while (front <= back) {

    int mid = (front + back) / 2;

    if (limit_check(stones, mid, k)) {
        back = mid - 1;
    }
    else {
        front = mid + 1;
    }
}

limit_check()

모든 돌을 순회하면서 mid 숫자를 빼본다.

limit가 충족된다면, true를 리턴한다.

// 연속적으로 0 이 limit개 만큼 있는지 참/거짓 확인한다. 

bool limit_check(vector<int> s, int mid, int limit) {

    int cnt = 0; // 연속으로 0 이 있는 개수

    for (auto i : s) { // 돌의 숫자에서 mid를 뺀다 

        if (i - mid <= 0) {
            cnt++;
            if (cnt == limit) // mid 명이 건널 수 있다고 판단. 
                return true;
        }
        else {
            cnt = 0;
        }
    }
    return false;
}

정답 뜬 코드

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

// 연속적으로 0 이 limit개 만큼 있는지 참/거짓 확인 
bool limit_check(vector<int> s, int mid, int limit) {
    int cnt = 0; // 연속으로 0 이 있는 개수

    for (auto i : s) { // 돌에서 mid를 뺀다 

        if (i - mid <= 0) {
            cnt++;
            if (cnt == limit)
                return true;
        }
        else {
            cnt = 0;
        }
    }
    return false;
}

int solution(vector<int> stones, int k) {

    // 다리를 건너는 사람 수를 탐색 
    int front = 1;
    int back = *max_element(stones.begin(), stones.end()); // 최대값 

    // 이분탐색 
    while (front <= back) {

        int mid = (front + back) / 2;

        if (limit_check(stones, mid, k)) { // mid 숫자로 limit가 충족된다면, 
            back = mid - 1; // 숫자를 줄여본다. 
        }
        else {
            front = mid + 1;
        }
    }
    return front;
}

코드 [ 효율성 0점 정확도 100점 완전탐색 ]

이렇게 짜지 말아야지 하는 마음으로 기록해둔다.

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

int solution(vector<int> stones, int k) {

    int answer = 0; // 사람 수 
    bool flag = true;

    while (flag) {

        int limit_cnt = 0;
        // 0 이 연속되는지 확인 
        for (auto it = stones.begin(); it != stones.end(); ++it)
        {
            if (*it == 0) {
                limit_cnt++;
                if (limit_cnt >= k) return answer; // 제한 숫자 초과 시 종료 
            }
            else {
                limit_cnt = 0;
            }
        }

        // 1 감소 
        for (auto it = stones.begin(); it != stones.end(); ++it)
        {
            if(*it > 0) *it = *it - 1;
        }

        if (limit_cnt >= k) flag = false;
        else {
            answer++;
        }
    }

    return answer;
}

문제

실패율 프로그래머스 level1

2019 KAKAO BLIND RECRUITMENT

리뷰

answer에 담아야 하는 건 실패율 높은 순의 '인덱스'이다.

그래서 pair 에 인덱스와 실패율을 담았다. 자료형에 주의하자.

vector<pair<int, double>> per; // <인덱스, 실패율>

// 실패율  =  N스테이지에 위치한 사람 수  / N스테이지 이상에 위치한 사람 수 
double a = count(stages.begin(), stages.end(), i);  // N에 위치한 사람 
double b = count_if(stages.begin(), stages.end(), [i](int elem) { return elem >= i; });  // N 이상인 사람

제한 사항을 주의해야 한다.

• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• bool compare(pair<int, double> a, pair<int, double> b) { if (a.second == b.second) return (a.first < b.first); return (a.second > b.second) ; }

• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

if (b == 0) { // 스테이지에 도달한 사람이 없으면, 실패율 0 
    per.push_back({i , 0 });
    continue;
}

코드

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

// 만약 실패율이 같은 스테이지가 있다면,  작은 번호의 스테이지가 먼저 온다 

bool compare(pair<int, double> a, pair<int, double> b) {
    if (a.second == b.second) return (a.first < b.first); 
    return (a.second > b.second) ;
}

vector<int> solution(int N, vector<int> stages) {

    vector<int> answer;
    vector<pair<int, double>> per; // <인덱스, 실패율>

    for (int i = 1; i <= N; i++) { // 스테이지 : 1부터 N까지 

        double a = count(stages.begin(), stages.end(), i);  // i에 위치한 사람 
        double b = count_if(stages.begin(), stages.end(), [i](int elem) { return elem >= i; });  // i 이상인 사람

        if (b == 0) { // 스테이지에 도달한 사람이 없으면, 실패율 0 
            per.push_back({i , 0 });
            continue;
        }

        double fail = a / b; 
        per.push_back({i, fail});
    }

    sort(per.begin(), per.end(), compare); 

    for (int i = 0; i < N; i++) { // 인덱스를 answer에 옮긴다 
        answer.push_back(per[i].first);
    }

    return answer;
}

문제

체육복 프로그래머스 level1

리뷰

문제에서 주의할 점은 이 문장이다.

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다.
• 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

이 점 때문에 헷갈릴 것 같아서. 여벌 가진 학생과 도난당한 학생을 따로 처리했다.

 //  answer 초기화.  모든 학생이 자신의 체육복을 가지고 있다고 가정한다.
int answer = n ;

// 1.  모든 학생이 1개의 체육복을 가지고 있다고 가정한다.
vector<int> student(n+1, 1); 

// 2.  여벌 있는 학생만  + 1 
for (auto i : reserve) { 
    student[i]++;
}

// 3.  도난 당했다면 -1
for (auto i : lost) { 
    student[i]--;
    if (student[i] == 0) answer--; // 0 이라면 정답에서 빼준다. 
}

자신의 앞이나 뒤의 학생에게만 체육복을 빌려줄 수 있다.

따라서 [ 2, 0 ] 인 경우, 내 뒤에 학생에게 빌려주면 [ 1 , 1] 이 된다.

[ 0, 2 ] 인 경우에도, 똑같이 [ 1, 1] 이 된다.

이 두 가지 경우에만 answer를 증가시킬 수 있다.

학생 두 명을 동시에 확인하니까 반복문 인덱스를 주의해야 한다.

    for (int i = 1; i < n; i++) { // 빌려줄 수 있는 경우는 (2, 0) 그리고 (0, 2) 인 경우 뿐이다. 

        if (student[i] == 2 && student[i+1] == 0) {
            student[i] = student[i + 1] = 1;
            answer++;

        }else if(student[i] == 0 && student[i + 1] == 2) {
            student[i] = student[i + 1] = 1;
            answer++;
        }
    }

코드

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

int solution(int n, vector<int> lost, vector<int> reserve) {

    int answer = n;

    vector<int> student(n+1, 1); // 1로 초기화 

    for (auto i : reserve) { // 여벌 있으면 + 1 
        student[i]++;
    }

    for (auto i : lost) { // 도난 당했다면 -1
        student[i]--;
        if (student[i] == 0) answer--;
    }

    for (int i = 1; i < n; i++) { // 빌려줄 수 있는 경우는 (2, 0) 그리고 (0, 2) 인 경우 뿐이다. 

        if (student[i] == 2 && student[i+1] == 0) {
            student[i] = student[i + 1] = 1;
            answer++;

        }else if(student[i] == 0 && student[i + 1] == 2) {
            student[i] = student[i + 1] = 1;
            answer++;
        }
    }

    return answer;
}

문제

최대공약수와 최소공배수 프로그래머스 level1

리뷰

최대공약수는 유클리드 호제법으로 구할 수 있다.

유클리드 호제법은 나머지를 구하는 MOD 연산을 이용한다.

MOD 연산

// MOD 연산 : 나머지를 구하는 연산 
5 % 3 = 2 
// 5를 3으로 나눈 몫은 1 이다. 나머지는 2. 

유클리드 호제법 (Euclidean algorithm)

2개의 자연수에 대해서. a 를 b로 나눈 나머지를 r 이라고 한다면. ( 단, a > b )

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지를 구하는 과정을 반복하여.

나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대 공약수다.

예시를 읽으면 금방 이해된다. 위키백과 유클리드호제법

14와 24의 최대공약수(GCD, Greatest Common Divisor)

// 24와 14의 최대 공약수 구하기.  주의할 점은 a > b 

24 % 14 = 10 
14 % 10 = 4
10 % 4  = 2
4  % 2  = 0

// MOD 연산 결과가 0 이 되면 종료된다. -->  24와 14의 최대공약수는 2 

나머지가 0 일 때, 나누는 수 2가 최대공약수다.

재귀 코드

// 나머지가 0이 나올 때 종료.
int GCD(int a, int b)   // 단, a > b
{
    if (b == 0) return a;
    else return GCD(b, a%b);
}

반복문 코드

int GCD(int a, int b){  // 단, a > b
    int temp = 0;

    while(b){
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

최소공배수 (LCM, Least Common Multiple)

a 와 b의 최소공배수는 최대공약수를 구하면 계산할 수 있다.

LCM =  a * b * GCD(a, b);

코드

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

int gcd(int a, int b) 
{
    if (b == 0) return a;
    else return gcd(b, a%b);

}

vector<int> solution(int n, int m) {
    vector<int> answer;

    // 큰 값을 앞에, 작은 값을 뒤에.
    int gcd_num = gcd(max(n, m), min(n, m));

    answer.push_back(gcd_num);
    answer.push_back((n*m)/gcd_num);

    return answer;
}