[알고리즘 문제 해설] 파트1~3

programmers.co.kr/learn/courses/18

알고리즘 문제 해설

* 강의 링크는 위에 있습니다

 

파트1. 자릿수 더하기 문제 

각 자릿수의 합 구하는 방법 : 1의 자리를 구함 -> 1의 자리를 제거(나누기 10)하고 나머지 숫자들을 오른쪽으로 한 칸씩 이동 -> 이동시킬 숫자가 없을 때 까지 반복

ex) 123 : 123 % 10 = 3, 123 / 10 = 12 ->  12 % 10 = 2, 12 / 10 = 1 -> 1 % 0 = 1, 1 / 10 = 0

#include <iostream>

using namespace std;
int solution(int n)
{
    int sum = 0;
    while(n>0)
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

*입력받은 n이 0보다 큰 동안 각 자릿수의 합 구하는 방법(sum += n %10; n /= 10;)을 이용해 코드를 구현

---

파트2. 순열 검사 문제

중복 없는 배열

1. 범위를 벗어나는 값이 있는지 확인해보기

2. 범위를 벗어나지 않는 값이 몇 번 등장하는지 체크하기

1) 배열 이용

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

int chk[100001] = {0};
bool solution(vector<int> arr)
{
    int n = arr.size();
    for(int i = 0; i < n; ++i){
        if(arr[i] < 1 || arr[i] > n)
            return false;
        chk[arr[i]]++;
    }
    for(int i = 1; i <= n; ++i)
        if(chk[i] != 1)
            return false;
    return true;
}

*입력받은 배열의 길이를 n에 저장

첫번째 for문 : 배열의 각 원소를 순회하면서 만약 범위를 벗어나는 숫자(n보다 크거나, 1보다 작거나)가 있다면 false 리턴

chk[arr[i]]++; : array의 i번째 원소가 chk의 인덱스로 들어가서 해당 값이 몇 번 나타났는지 체크

두번째 for문 : chk 배열의 값이 모두 1이라면(모든 값이 고르게 들어갔다면) true 리턴

 

2) 정렬 이용

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

bool solution(vector<int> arr)
{
    sort(arr.begin(), arr.end());
    for(int i = 0; i < arr.size(); ++i)
        if(arr[i] != i + 1)
            return false;
    
    return true;
}

*정렬을 이용하기 위해서는 #include <algorithm> 헤더 파일 필요

입력받은 배열을 정렬한 후에 for문을 이용하여 chk 배열의 값이 모두 1이라면(모든 값이 고르게 들어갔다면) true 리턴

---

파트3. 나머지 한 점 문제

직사각형 좌표 : (x1, y1), (x2, y1), (x1, y2), (x2, y2) -> x1, x2, y1, y2 개수가 각각 2개씩

1) 조건문

2) 해시

3) xor 이용(간단하게 구현 가능)

A xor A  = 0

(A xor A) xor B = B

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

vector<int> solution(vector<vector<int>> v) { // 기본적인 2차원 벡터의 선언 방식
    vector<int> ans = {0,0}; // 초기화
    
    for(int i = 0; i < 3; ++i){
        ans[0] ^= v[i][0];
        ans[1] ^= v[i][1];
    }
    return ans;
}

*먼저 3개의 점을 모두 입력을 받음

for문을 이용해 3번 반복(3개의 점)

ans[0] : x좌표, ans[1] : y좌표

v[0][0]부터 v[3][0]까지 3개의 점을 xor 연산(^)을 사용해서 나머지 한점의 x좌표를 구함

v[0][1]부터 v[3][1]까지 3개의 점을 xor 연산(^)을 사용해서 나머지 한점의 y좌표를 구함

 

조건문을 이용해서 작성하는 것보다 xor 연산을 이용하는 것이 더 코드가 짧아지는 것을 알 수 있었다