1. 목표
A. 프로그래머스 코테 문제 1단계 10문제 풀기
B. Array, Linked list, Stack, Queue
2. 프로그래머스 코테 문제 1단계 10문제
- 두 개 뽑아서 더하기 https://programmers.co.kr/learn/courses/30/lessons/68644
- 신규 아이디 추천 https://programmers.co.kr/learn/courses/30/lessons/72410
- K번째 수 https://programmers.co.kr/learn/courses/30/lessons/42748
- 2016년 https://programmers.co.kr/learn/courses/30/lessons/12901
- 가운데 글자 가져오기 https://programmers.co.kr/learn/courses/30/lessons/12903
- 나누어 떨어지는 숫자 배열 https://programmers.co.kr/learn/courses/30/lessons/12910
- 문자열 내 마음대로 정렬하기 https://programmers.co.kr/learn/courses/30/lessons/12915
- 폰켓몬 https://programmers.co.kr/learn/courses/30/lessons/1845
- 문자열 내림차순으로 배치하기 https://programmers.co.kr/learn/courses/30/lessons/12917
- 서울에서 김서방 찾기 https://programmers.co.kr/learn/courses/30/lessons/12919
A. 두 개 뽑아서 더하기
#include <string>
#include <vector>
using namespace std;
int compare(vector<int> answer, int tmp)
{
int i;
for (i = 0; i < answer.size(); i++)
{
if (answer[i] == tmp)
return (1);
}
return (0);
}
vector<int> solution(vector<int> numbers) {
vector<int> answer;
int i;
int j;
int z;
int tmp;
int flag;
for (i = 0; i < numbers.size() - 1; i++)
{
for (j = i + 1; j < numbers.size(); j++)
{
flag = 0;
tmp = numbers[i] + numbers[j];
if (!(compare(answer, tmp)))
{
for (z = 0; z < answer.size(); z++)
{
if (tmp < answer[z])
{
answer.emplace(answer.begin() + z, tmp);
flag = 1;
break;
}
}
if (flag == 0)
answer.push_back(tmp);
}
}
}
return answer;
}
- compare 함수를 선언하여 특정 문자가 특정 문자열 내에 있는 문자인지 판단한다.
- 두 개의 for loop를 중첩하여 입력받은 numbers vector 내에 있는 값을 모두 서로 더해준다.
- 더한 값을 stack 방식으로 쌓을 answer 변수 내에 더한 값인 tmp 값이 있는지 compare 함수를 통해 확인해준 후에 없다면 for loop를 한번 더 돌려서 오름차순으로 answer 변수에 넣는다.
- answer.emplace(answer.begin() + z, tmp) : answer vector의 answer.begin() + z위치에 tmp 값을 삽입해준다. 함수가 실행될 때마다 vector의 모든 메모리는 재할당 된다.
B. 신규 아이디 추천
C. K번째 수
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
vector<int> answer;
vector<int> tmp;
int i;
int j;
int k;
int a;
int b;
int x;
for (x = 0; x < commands.size(); x++)
{
i = commands[x][0];
j = commands[x][1];
k = commands[x][2];
tmp.push_back(array[i - 1]);
for (a = i; a < j; a++)
{
if (tmp.back() < array[a])
tmp.push_back(array[a]);
else if (tmp.front() > array[a])
tmp.emplace(tmp.begin(), array[a]);
else
{
for (b = 0; b < tmp.size(); b++)
{
if (tmp[b] >= array[a])
{
tmp.emplace(tmp.begin() + b, array[a]);
break;
}
}
}
}
answer.push_back(tmp[k - 1]);
tmp.clear();
}
return answer;
}
- 바깥의 for loop를 통해 command 2차원 vector에 입력된 정보를 하나씩 받아온다.
- 하나씩 받아온 command vector 정보를 활용하여 array의 범위를 지정한다.
- 마지막 for loop를 통해 지정한 array의 범위를 오름차순 정렬한다.(algorithm 클래스의 sort함수를 활용하면 될 듯)
- 정렬된 array의 범위에서 k번째 수를 받고 answer vector 변수에 stack 방식으로 넣는다.
D. 2016년
#include <string>
#include <vector>
using namespace std;
string solution(int a, int b) {
string answer = "";
vector<string> day = {"THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"};
vector<int> max_day = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int i;
int day_tmp = 0;
for (i = 0; i < a - 1; i++)
day_tmp += max_day[i];
day_tmp += b;
answer = day[day_tmp % 7];
return answer;
}
- 2016년 1월 1일이 금요일이므로 이에 맞게 순서대로 인덱스에 매칭하여 day vector 변수에 날짜 데이터를 넣는다.(일수를 7로 나눈 나머지가 1일 경우 "FRI"금요일임)
- max_day vector 변수에 1월부터 순서대로 max_day 값을 지정해놓는다.(2016년은 윤년이므로 2월의 max_day는 29일이다.)
- for loop를 통해 a로 입력된 월수를 토대로 해당 월까지의 일수를 계산한다.
- b로 입력된 일수를 월까지의 일수에 더한다.
- 총 더해진 값을 7로 나눈 나머지를 day vector의 인덱스로 활용하여 최종적으로 answer에 날짜 값을 입력한다.
E. 가운데 글자 가져오기
#include <string>
#include <vector>
using namespace std;
string solution(string s) {
string answer = "";
int size = s.size();
if (size % 2 == 0)
answer = s.substr(size / 2 - 1, 2);
else
answer = s.substr(size / 2, 1);
return answer;
}
- 입력받은 string의 크기가 짝수인지 홀수인지에 따라 가운데 값이 두개일지 한개일지 결정된다. if 조건문을 활용하여 값을 두개 넣을지 한개 넣을지를 결정한다.
- substr 함수를 활용하여 특정 인덱스 값으로부터 몇 개를 answer 변수에 넣을지 결정한다.
- s.substr(size / 2 - 1, 2) : string 변수 s에서 size / 2 - 1 인덱스 값으로 부터 2개를 반환한다.
F. 나누어 떨어지는 숫자 배열
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> arr, int divisor) {
vector<int> answer;
int i;
int j;
for (i = 0; i < arr.size(); i++)
{
if (arr[i] % divisor == 0)
{
if (answer.size() == 0)
answer.push_back(arr[i]);
else
{
if (answer.back() <= arr[i])
answer.push_back(arr[i]);
else if (answer.front() >= arr[i])
answer.emplace(answer.begin(), arr[i]);
else
{
for (j = 0; j < answer.size(); j++)
{
if (answer[j] > arr[i])
{
answer.emplace(answer.begin() + j, arr[i]);
break;
}
}
}
}
}
}
if (answer.size() == 0)
answer.push_back(-1);
return answer;
}
- for loop를 활용하여 arr vector 내의 값이 divisor로 나눠지는지 확인한다.
- 나누어 진다면 answer 변수에 값을 넣기 전에 기존 answer 변수 값과 대소관계를 if 조건문을 활용하여 확인한다.
- 내부의 for loop를 활용하여 answer 내부 값과 대소관계를 비교하여 알맞은 위치에 값을 넣는다.
G. 문자열 내 마음대로 정렬하기
#include <string>
#include <vector>
using namespace std;
vector<string> solution(vector<string> strings, int n) {
vector<string> answer;
string tmp;
int i;
int j;
int k;
for (i = 0; i < strings.size() - 1; i++)
{
for (j = i + 1; j < strings.size(); j++)
{
if (strings[i][n] > strings[j][n])
{
tmp = strings[i];
strings[i] = strings[j];
strings[j] = tmp;
}
else if (strings[i][n] == strings[j][n])
{
for (k = 0; k < strings[i].size(); k++)
{
if (strings[i][k] > strings[j][k])
{
tmp = strings[i];
strings[i] = strings[j];
strings[j] = tmp;
break;
}
else if (strings[i][k] < strings[j][k])
break;
}
}
}
}
answer = strings;
return answer;
}
- 버블 정렬을 활용하여 오름차순 정렬한다. 단, 비교 값은 인자로 입력 받은 n 값을 index로 활용한 string 문자이다.
- 해당 인덱스 값을 활용하여 대소 관계를 확인할 수 없을 경우, 사전순으로 string 값들을 for loop를 활용하여 오름차순 정렬한다.
H. 폰켓몬
#include <vector>
using namespace std;
int compare(vector<int> tmp, int x)
{
int i;
for (i = 0; i < tmp.size(); i++)
{
if (tmp[i] == x)
return (1);
}
return (0);
}
int solution(vector<int> nums)
{
vector<int> tmp;
int answer = 0;
int i;
int j;
if (nums.size() == 2)
return (1);
tmp.push_back(nums[0]);
for (i = 1; i < nums.size(); i++)
{
if (!(compare(tmp, nums[i])))
tmp.push_back(nums[i]);
if (nums.size() / 2 == tmp.size())
break;
}
answer = tmp.size();
return answer;
}
- 최대한 다양한 폰켓몬을 선택해야 하므로 tmp vector에 폰켓몬을 중복으로 입력하면 안된다.
- 1을 활용하여 tmp vector에 입력된 값을 for loop를 통해 nums 값과 비교할 것이고, tmp vector에 없는 값으로 판단될 때, tmp에 넣는다.
- for loop가 끝날 때까지 tmp 값에 넣지 않는 경우, answer에 tmp의 size를 계산하여 입력하고, for loop 내부에서 tmp의 size가 nums size의 반이 된다면 for loop를 빠져나온다.
I. 문자열 내림차순으로 배치하기
#include <string>
#include <vector>
using namespace std;
string solution(string s) {
string answer = "";
string str_tmp = s;
string tmp;
int i;
int j;
for (i = 0; i < str_tmp.size() - 1; i++)
{
for (j = i + 1; j < str_tmp.size(); j++)
{
if (str_tmp[i] < str_tmp[j])
{
tmp = str_tmp.at(i);
str_tmp[i] = str_tmp.at(j);
str_tmp[j] = tmp.at(0);
}
}
}
answer = str_tmp;
return answer;
}
- 버블 정렬을 활용하여 내림차순 정렬한다.(해당 정렬은 sort 함수로 대체해도 된다.)
- str_tmp.at(i) : str_tmp string 변수의 i index 값을 참조하여 반환한다.(따로 주소를 반환한다고 함)
J. 서울에서 김서방 찾기
#include <string>
#include <vector>
using namespace std;
string solution(vector<string> seoul) {
string answer = "김서방은 ";
int i;
int j;
for (i = 0; i < seoul.size(); i++)
{
if ("Kim" == seoul[i])
{
answer += to_string(i);
answer += "에 있다";
break;
}
}
return answer;
}
- answer string 변수를 "김서방은 "으로 초기화해준다.
- for loop를 통해 seoul vector 안에 "Kim" string 변수가 있는지 확인한다.
- 있다면 해당 인덱스 값을 to_string 함수를 통해 string으로 변환하여 answer string에 더한다.
- 마지막으로 "에 있다"를 answer string 변수에 더해준다.
- string 변수에 string 값을 더해주는 방식으로 string 변수에 string 값을 뒤에 이어서 붙일 수 있다.
- to_string(i) : int 형으로 받은 i 값을 string 형으로 변환해준다.
3. Array, Linked list, Stack, Queue
A. Array
- 특정 원소의 인덱스 값만 알고 있으면 해당 원소로 접근할 수 있는 random access가 가능하다.
- 배열의 원소들을 삭제하고 삽입할 때 시간복잡도가 생긴다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용(cost)이 발생하고 이 경우의 시간 복잡도는 O(n)가 된다. 삽입의 경우도 마찬가지.
B. Linked list
- Array의 문제점 해결을 위한 자료 구조이다.(삽입과 삭제가 용이)
- 자신의 원소 뿐만 아니라 자신 다음이 어떤 원소인지도 기억하고 있다.(이 부분만 다른 값으로 바꿔주면 삭제와 삽입이 됨) 이러한 데이터 덩어리를 노드라고 칭한다.
- Random access가 불가하여 데이터를 삽입 및 삭제하고자 하면 첫번째 원소부터 다 확인해 봐야한다는 단점이 있다.(시간 복잡도 발생)
- 단일 linked list는 임의의 원소를 삭제할 때, 그 원소의 이전 노드의 *pNext를 삭제할 노드의 다음 노드로 옮겨주어야 한다. 하지만 노드에는 이전 노드에 대한 정보가 없기 때문에 한 번에 노드를 삭제하는 것이 불가능.-> 이를 위해 양방향 liked list를 사용함(삽입, 삭제, 정렬 시 단일에 비해 수행할 연산이 조금 더 늘어남)
C. Stack
D. Queue
