오산마 study day 1

DaewoongJeon·2021년 3월 4일

OSanMa Algorithm Study

목록 보기

1/10

날짜 : 2021. 3. 1. (월)

1. 목표

A. 스터디 운영 방식 수립

B. 스터디 단기 목표 설정

C. 프로그래머스 코테 문제 1단계 10문제 풀기

2. 스터디 운영 방식

스터디 모임은 매주 월~목 오전 10시부터 2~3시간 가량 진행
스터디 모임 시간에는 전날 풀었던 코테 문제들을 서로 리뷰하고, 전날 습득한 CS 지식들을 공유한다.

3. 스터디 단기 목표

A. 3월 20일 LINE 코딩테스트

프로그래머스 코테 문제 1~2단계를 모두 풀어보고, 코드 리뷰를 통해 스터디원들의 피드백을 받아서 코테에 적응하는 것을 목표로 한다.

B. 3월 27일 LINE 필기시험

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linked-list
위 사이트에서 매일 CS 지식에 대해 공부한다.
http://www.kocw.net/home/m/search/kemView.do?kemId=1046323
위 사이트에서 운영체제 기초 개념에 대한 강의를 수강할 듯.

4. 프로그래머스 코테 문제 1단계 10문제

푼 문제 list

크레인 인형뽑기 게임 https://programmers.co.kr/learn/courses/30/lessons/64061
완주하지 못한 선수 https://programmers.co.kr/learn/courses/30/lessons/42576
모의고사 https://programmers.co.kr/learn/courses/30/lessons/42840
체육복 https://programmers.co.kr/learn/courses/30/lessons/42862
3진법 뒤집기 https://programmers.co.kr/learn/courses/30/lessons/68935
같은 숫자는 싫어 https://programmers.co.kr/learn/courses/30/lessons/12906
두 정수 사이의 합 https://programmers.co.kr/learn/courses/30/lessons/12912
문자열 내 p와 y의 개수 https://programmers.co.kr/learn/courses/30/lessons/12916
문자열 다루기 기본 https://programmers.co.kr/learn/courses/30/lessons/12918
소수 찾기 https://programmers.co.kr/learn/courses/30/lessons/12921

A. 크레인 인형뽑기 게임

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> tmp;
    tmp.push_back(0);
    int i;
    int j;
    for (i = 0; i < moves.size(); i++)
    {
        for (j = 0; j < board.size(); j++)
        {
            if (board[j][moves[i] - 1] != 0)
            {
                if (tmp.back() == board[j][moves[i] - 1])
                {
                    answer += 2;
                    tmp.pop_back();
                }
                else
                    tmp.push_back(board[j][moves[i] - 1]);
                board[j][moves[i] - 1] = 0;
                break;
            }
        }
    }
    return answer;
}

코드 설명

tmp vector를 선언하여 moves가 가리키는 인덱스에서 board에 0이 아닌 값이 있는 경우, 해당 값을 tmp에 stack 방식으로 채워넣고 board에 있는 값을 삭제한다.
tmp vector의 마지막 값과 moves가 가리키는 인덱스에서의 board 값을 비교하여 일치하는 경우, tmp에서 해당하는 값과 board의 값을 삭제하고 삭제한 인형의 갯수를 answer 변수에 더한다.

부가 설명

vector<int> tmp : <> 괄호 안은 vector 변수의 자료형을 지정해준다. 자료형으로 구조체를 받을 수 있고 다른 vector 변수 및 pair 변수를 받을 수 있다.
tmp.push_back(0) : <vector> 클래스에서 사용할 수 있는 함수이다. 해당 vector의 마지막 index 공간에 ()괄호안의 값을 넣어준다. 코드에서 push_back으로 tmp vector를 초기화 해준 이유는 선언하고 값을 넣어주는 함수를 활용하지 않으면 메모리가 할당이 안된 상태므로, 메모리 할당이 안된 상태에서 해당 vector를 참조할 경우 오류가 발생한다.
moves.size() : moves 벡터의 크기를 반환한다.
tmp.pop_back() : tmp vector의 마지막 index에 해당하는 값을 지워준다.

참고
cpp 함수 : https://hwan-shell.tistory.com/119
복사생성자 : https://metalkim.tistory.com/245
클래스와 생성자 : https://velog.io/@lshjh4848/%ED%81%B4%EB%9E%98%EC%8A%A4%EC%99%80-%EC%83%9D%EC%84%B1%EC%9E%90
2차원 벡터 활용법 : https://leeeegun.tistory.com/3
cpp 함수 : https://blockdmask.tistory.com/70

B. 완주하지 못한 선수

C. 모의고사

D. 체육복

#include <string>
#include <vector>

using namespace std;

int compare(int x, vector<int> reserve)
{
    int i;
    for (i = 0; i < reserve.size(); i++)
    {
        if (x == reserve[i])
            return (i);
    }
    return (-1);
}

int solution(int n, vector<int> lost, vector<int> reserve) {
    vector<int> tmp_vec(lost.size(), -1);
    int index = 0;
    int answer;
    int tmp;
    int i;
    for (i = 0; i < lost.size(); i++)
    {
        if (-1 < compare(lost[i], reserve))
        {
            reserve.erase(reserve.begin() + compare(lost[i], reserve));
            lost.erase(lost.begin() + i);
            i--;
        }
    }
    answer = n - lost.size();
    for (i = 0; i < lost.size(); i++)
    {
        if (-1 < compare(lost[i] - 1, reserve) && -1 < compare(lost[i] + 1, reserve))
            tmp_vec[index++] = i;
        else if (-1 < compare(lost[i] - 1, reserve))
        {
            answer++;
            reserve.erase(reserve.begin() + compare(lost[i] - 1, reserve));
        }
        else if (-1 < compare(lost[i] + 1, reserve))
        {
            answer++;
            reserve.erase(reserve.begin() + compare(lost[i] + 1, reserve));
        }
    }
    for (i = 0; i < index; i++)
    {
        if (-1 < compare(lost[tmp_vec[i]] - 1, reserve))
        {
            answer++;
            reserve.erase(reserve.begin() + compare(lost[tmp_vec[i]] - 1, reserve));
        }
        else if (-1 < compare(lost[tmp_vec[i]] + 1, reserve))
        {
            answer++;
            reserve.erase(reserve.begin() + compare(lost[tmp_vec[i]] + 1, reserve));
        }
    }
    return answer;
}

코드 설명

문자열과 특정 문자를 매개변수로 입력 받는 compare 함수 선언. 특정 문자가 입력 받은 문자열 내에 있을 때, 해당 index를 반환하고 없을 때 -1을 반환한다.(strcmp같은 라이브러리 함수를 활용하도록 하자)
먼저 체육복을 도난당했지만 여벌의 체육복이 있는 경우를 첫 번째 for loop를 통해 lost vector에서 제거해준다.
전체 학생 수(n)에서 도난당한 학생수(lost.size())를 빼주어 체육시간에 참여할 수 있는 학생 수(answer)를 초기화해준다.
도난당한 학생의 앞뒤로 여벌의 체육복을 갖고 있는 학생이 있는 경우를 우선순위에서 제외하고 앞 또는 뒤의 학생만 여벌의 체육복을 갖고 있는 경우를 두 번째 for loop를 통해 우선적으로 처리해준다.(사실 앞의 학생부터 순서대로 체육복을 빌려주거나 빌린다면, 이 복잡한 과정을 안거쳐도 될 듯?)
마지막 for loop를 통해 남은 도난당한 학생수를 모두 처리해준다.

부가 설명

reserve.erase(reserve.begin() + i) : reserve vector의 특정 index에 해당하는 값을 삭제해준다. index 값으로 주소 값을 입력해 주어야 한다. reserve.begin()은 reserve vector의 첫 번째 인덱스 주소값을 나타낸다. 해당 주소값에 특정 int 값을 더해주거나 빼주면 자동으로 특정 인덱스를 가리키는 주소값으로 계산해준다.

E. 3진법 뒤집기

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int cal_num(int n)
{
    int i;
    for (i = 0; n / 3 != 0; i++)
    {
        n = n / 3;
    }
    return (i + 1);
}

char *to_three(int n, int size)
{
    char *result;
    int i;
    result = (char*)malloc(size + 1);
    for (i = 0; n != 0; i++)
    {
        result[i] = n % 3 + '0';
        n = n / 3;
    }
    result[i] = '\0';
    return (result);
}

int to_int(char *tmp_arr, int size)
{
    int result = 0;
    int tmp = 1;
    int i;
    int index = size - 1;
    for (i = 0; i < size; i++)
    {
        result += (tmp_arr[index--] - '0') * tmp;
        tmp *= 3;
    }
    return (result);
}

int solution(int n) {
    int answer = 0;
    int size = cal_num(n);
    char *tmp_arr = to_three(n, size);
    char tmp;
    int i;
    answer = to_int(tmp_arr, size);
    return answer;
}

코드 설명

cal_num 함수를 통해 입력 받은 숫자의 자릿수를 파악하였다.
1에서 파악한 자릿수를 활용하여 to_three함수를 통해 입력 받은 숫자(n)를 3진수로 변환해준다.
to_three 함수에서 인덱스에 반대로 입력하여 값을 뒤집어 준다.
to_int 함수에서 반환받은 3진수 문자열을 int로 변환해준다.

부가 설명

해당 문제는 c로 풀었음. cpp의 라이브러리를 활용하여 쉽게 풀 수 있는 방법을 고안해야할 듯.

F. 같은 숫자는 싫어

#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    int i;
    answer.push_back(arr[0]);
    for (i = 1; i < arr.size(); i++)
    {
        if (arr[i] != answer.back())
            answer.push_back(arr[i]);
    }
    return answer;
}

코드 설명

answer벡터를 arr의 0 index 값으로 초기화시켜준다.
for loop에서 answer의 마지막 index 값과 arr 값을 비교하여 일치하는지 확인한다. 일치하지 않으면 answer vector에 차곡차곡 stack 방식으로 값을 넣어준다.

G. 두 정수 사이의 합

#include <string>
#include <vector>

using namespace std;

long long solution(int a, int b) {
    long long answer = 0;
    int i;
    if (a > b)
    {
        for (i = b; i <= a; i++)
            answer += i;
    }
    else
    {
        for (i = a; i <= b; i++)
            answer += i;
    }
    return answer;
}

코드 설명

입력 받은 숫자 사이의 값을 모두 더해주어야 하는 문제이다.
그러므로 입력 받은 숫자를 for loop의 첫번째 index와 마지막 index로 설정하고 for loop를 돌려준다.
for loop를 통해 증가하는 i 값을 answer에 지속적으로 더해준다.
입력 받은 두 int 값의 대소 관계를 통해 어떤 숫자를 첫 번째 index로 설정하고 마지막 index로 설정할지 정해준다.

H. 문자열 내 p와 y의 개수

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

bool solution(string s)
{
    bool answer = true;
    int i;
    int p_num = 0;
    int y_num = 0;
    for (i = 0; s[i] != '\0'; i++)
    {
        if (s[i] == 'p' || s[i] == 'P')
            p_num++;
        else if (s[i] == 'y' || s[i] == 'Y')
            y_num++;
    }
    if (p_num != y_num)
        answer = false;
    return answer;
}

코드 설명

for loop를 통해 문자열 내 대소문자 구분 없이 p와 y의 갯수를 계산해준다.
계산된 갯수를 비교하여 answer 변수에 true or false 값을 넣어준다.

I. 문자열 다루기 기본

#include <string>
#include <vector>

using namespace std;

bool solution(string s) {
    bool answer = true;
    int i;
    for (i = 0; i < 6 && s[i] != '\0'; i++)
    {
        if (s[i] < '0' || s[i] > '9')
            answer = false;
    }
    if (i != 4 && i != 6)
        answer = false;
    if (i == 6 && s[i] != '\0')
        answer = false;
    return answer;
}

코드 설명

for loop를 통해 문자열이 숫자로 구성되어 있는지 확인한다.
for loop에서 사용된 i 값에 따라 문자열의 크기를 판단한다.

부가 설명

문자열이 숫자로 구성되어 있는지는 isnumber 함수를 이용하면 될 것 같다.

J. 소수 찾기

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> result;
    result.push_back(1);
    result.push_back(1);
    for (int i = 2; i <= n; i++)
        result.push_back(1);
    for (int i = 2; i * i <= n; i++)
    {
        if (result[i] == 1)
        {
            for (int j = i * i; j <= n; j += i)
            {
                result.erase(result.begin() + j);
                result.emplace(result.begin() + j, 0);
            }
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (result[i] == 1)
            answer++;
    }
    return answer;
}

코드 설명

에라토스테네스의 체를 응용하였다.(소수를 구하고자 하는 구간 안에서 소수에 해당하지 않는 수의 자기자신을 제외하고 그의 배수를 제외시키는 방식으로 소수를 추출함)
첫번째 for loop에서 n보다 작은 모든 인덱스 값을 1로 초기화함(1값을 가진 인덱스가 소수임을 표현)
i제곱이 n일때까지 i를 1씩 증가시킬 것이고 i가 소수일 때, 그의 배수인덱스에 0을 입력함으로서 모두 소수가 아님을 표현할 것임
마지막 for loop에서 1인 인덱스 값을 세어 answer로 return 함.

참고
https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

DaewoongJeon

다음 포스트

오산마 study day 1

OSanMa Algorithm Study

1. 목표

A. 스터디 운영 방식 수립

B. 스터디 단기 목표 설정

C. 프로그래머스 코테 문제 1단계 10문제 풀기

2. 스터디 운영 방식

3. 스터디 단기 목표

A. 3월 20일 LINE 코딩테스트

B. 3월 27일 LINE 필기시험

4. 프로그래머스 코테 문제 1단계 10문제

A. 크레인 인형뽑기 게임

B. 완주하지 못한 선수

C. 모의고사

D. 체육복

E. 3진법 뒤집기

F. 같은 숫자는 싫어

G. 두 정수 사이의 합

H. 문자열 내 p와 y의 개수

I. 문자열 다루기 기본

J. 소수 찾기

오산마 study day 2

0개의 댓글