1. 1158 - 큐 / Array(?)
https://life-with-coding.tistory.com/408
https://blockdmask.tistory.com/332
원형으로 이어져있는 것처럼, 3번째 뒤의 것을 빼는데, 7 다음은 1이다.
제외 순서는 무지개 순서와 같다.
이전에 자바로 풀었던 문제이고, 큐를 사용했던 것 같다.
해결
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N, K;
int tmp_K = 1;
int tmp_value;
queue<int> Josep_input;
queue<int> Josep_result;
cin >> N >> K;
// 일단 input queue에 다 채워 넣는다.
for (int i = 1; i < N+1; i++)
{
Josep_input.push(i);
}
// input queue가 다 빌 때까지 뺀다.
while (!Josep_input.empty())
{
if (tmp_K == K)
{
// 해당 값을 결과큐에 이동시킨다.
Josep_result.push(Josep_input.front());
Josep_input.pop();
tmp_K = 1;
}
else
{
// 맨 앞의 값을 맨 뒤에 넣는다.
tmp_value = Josep_input.front();
Josep_input.pop();
Josep_input.push(tmp_value);
tmp_K++;
}
}
//출력부분도 신경 써야만 한다.
cout << '<';
while(!Josep_result.empty()){
tmp_value = Josep_result.front();
Josep_result.pop();
if(Josep_result.empty()){
cout << tmp_value << ">";
}
else{
cout << tmp_value << ", ";
}
}
return 0;
}풀이
2개의 queue를 사용한다.
input에 해당하는 queue를 사용하는데, 이건 큐가 무조건 구현하는 것이 좋을까 고민된다.
그 이유는, 큐의 맨 앞의 값을 맨뒤로 옮기는 비용이 굉장히 무거워보인다.
다른 방식을 생각해보자면,, 배열로 구현을 하고,
제외된 인덱스의 값은 0으로 바꾸고,
계속 순환하는 매커니즘은, 배열이 i=0부터 N까지 다 돌았음에도,
배열의 모든 값이 0이 아닌경우로 둘 수 있겠다.
하지만, 모든 값을 확인하는 매커니즘 또한 무겁다.
그래서 empty라는 함수를 찾았고, 0으로 초기화가 된 경우에도 적용되는지 시험해봣는데, 되지 않는다.
그 이유는, array의 empty함수는, array의 size가 0인 것을 empty라고 하기 때문이다..
즉, input을 구현하기 위해서
큐가 쓰이는 것이 좋은 경우는, K가 작을수록 좋을 것이다.
맨 앞의 값을 이동시킬 필요없이, 바로 result로 이동시키면 되기 때문이다.
그 반면, Array가 쓰이는 것이 좋은 경우는, K가 클수록, N이 작을수록 좋을 것이다.
K번째가 아닌동안 맨 앞의 값을 불필요하게 뒤로 이동시키지 않아도 되고,
N이 작아야 전체값이 0인지 빠르게 판별할 수 있기 때문이다.
그렇다면 result에 해당하는 자료구조는?
이건 그냥 들어온 순서대로 빼기만 하면 되므로,
큐가 제일 적합하지만, 배열도 가능할 것이다.
성능의 차이는 없을 듯 싶다. array가 비용이 더 적을듯하긴 한데...
처음에는 왜인지 result 큐에 원소가 들어가지 않았다..
while문의 empty 조건을 !를 붙여야 했다.
정상적으로 result로 순서대로 이동하게 된다.
이 문제의 핵심은 원형 매커니즘을 어떻게 구현하는가?에 있고,
추가로 출력에 있어서
이런식으로 괄호에 , 찍는 별 것 아니지만 신경써야하는 부분으로 볼 수 있겠다.
출력코드
2. 2164 - Queue / Deque
https://wing-beat.tistory.com/24
시도
#include <iostream>
#include <queue>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tmp;
int N;
cin >> N;
queue<int> cards;
for(int i=1; i<N+1; i++){
cards.push(i);
}
while(!cards.empty()){
//첫번째 카드 그냥 빼기, 빼기전에 일단 저장
tmp = cards.front();
cards.pop();
//첫번째 카드를 뺐을 때, 하나도 없다면, 바로 출력
if(cards.empty()){
cout<<tmp;
}
//두번째 카드 맨 뒤에 넣기
tmp = cards.front();
cards.pop();
cards.push(tmp);
}
return 0;
}메모리 초과
생각해보니 현실에서의 동작 그대로 짠 것 같다.
더 현명하게 짤 필요가 있어보인다.
시도 2
잘 생각해보면, 맨위를 버리고 그 다음 카드를 놓는 작업을 하게 되는데,
홀수가 다 걸러진다.
아래처럼 반을 나눠서 넣어도 메모리 초과오류가 발생.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int tmp;
int N;
cin >> N;
queue<int> cards;
if (N == 1)
{
cout << N;
}
else
{
if (N % 2 == 0)
{
for (int i = 1; i < N + 1; i++)
{
if (i % 2 == 0)
{
cards.push(i);
}
}
}
else
{
cards.push(1);
for (int i = 1; i < N + 1; i++)
{
if (i % 2 == 0)
{
cards.push(i);
}
}
}
}
/* 생략 */
return 0;
}해결
#include <iostream>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int tmp;
int N;
cin >> N;
queue<int> q;
for (int i = 1; i <= N; ++i) {
q.push(i);
}
while (q.size() > 1) {
q.pop();
q.push(q.front());
q.pop();
}
cout<<q.front();
return 0;
}풀이
메모리 초과라고 해서 자료구조의 문제인가 싶어서 Deque로도 바꾸고 난리를 쳤는데,
그냥 while문을 더 짧게 쓰니 통과된다..
유일하게 추가된게 tmp라는 int변수 하나뿐이고,
심지어 초기화도 main 내에서 한 번만 하게 되는데 왜 메모리초과가 발생한건지 모르겠다.
메모리 제한은 128MB이고,
1~50만개의 정수를 입력받을 수 있는데,
50만 x 4를 하여, 큐의 크기를 구하면, 200만바이트,
= 1950 정도의 킬로바이트
= 1메가바이트정도밖에 되지 않는다..
실제로 sizeof함수를 사용하면 최대일때 80바이트?밖에 되지 않는다?
하나에 80이라는 뜻인가?
cout << sizeof(q) << "\n";
실제 계산 결과는 405KB밖에 뜨지 않았다.
128MB의 1MB근처도 가지 못했다.
풀어도 찝찝한 문제..
3. 3986 - Stack
https://life-with-coding.tistory.com/406
해결
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
int count = 0;
string this_stirng;
char input_char;
cin >> N;
// case 만큼 반복,
for (int i = 0; i < N; i++)
{
stack<char> input_stack;
cin >> this_stirng;
// 해당 string의 글자수만큼 반복,
for (int k = 0; k < this_stirng.length(); k++)
{
if (input_stack.size() == 0)
{
input_stack.push(this_stirng[k]);
}
else
{
if (input_stack.top() == this_stirng[k])
{
input_stack.pop();
}
else
{
input_stack.push(this_stirng[k]);
}
}
}
if (input_stack.size() == 0)
{
count++;
}
}
cout << count;
return 0;
}풀이
전형적인 짝맞추기 문제였고,
해당 유형에 대부분 쓰이는 stack을 활용하여 풀 수 있었다.
초기화 구문을 따로 넣지 않고, for문내에서 계속 생성하도록 하였다.
4. 10828 - Stack 구현 / enum switch
시도
//[결과]
1
push 1
value :0정상적으로 push라는 switch의 case로 들어가서
s_push라는 함수까지 정확하게 호출하는 것 같은데...
왜 cin>>input_value 문장만 실행되지 않는 걸까?
안에 변수의 초기화를 집어넣어도 결과는 마찬가지이다.
심지어 초기화도 쓰레기값이 들어가있다.
결론적으로 Enum을 이용한 Switch문이 제대로 동작하지 않았다.
해결
#include <iostream>
using namespace std;
int stack[100000]; // 임의의 stack
int stack_size = 0;
void s_push(int value);
void s_pop();
void s_size();
void s_empty();
void s_top();
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// 명령어 모드
string mode;
int input_value;
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> mode;
if (mode == "push")
{
cin >> input_value;;
s_push(input_value);
}
else if (mode == "pop")
{
s_pop();
}
else if (mode == "size")
{
s_size();
}
else if (mode == "empty")
{
s_empty();
}
else if (mode == "top")
{
s_top();
}
}
return 0;
}
// size가 가리키는 위치에 넣고, size++
void s_push(int value)
{
stack[stack_size] = value;
stack_size++;
}
void s_pop()
{
if (stack_size >= 1)
{
cout << stack[stack_size - 1] << '\n';
stack[stack_size - 1] = 0;
stack_size--;
}
else
{
cout << -1 << '\n';
}
}
void s_size()
{
cout << stack_size << '\n';
}
void s_empty()
{
if (stack_size == 0)
{
cout << 1 << '\n';
}
else
{
cout << 0 << '\n';
}
}
void s_top()
{
if (stack_size == 0)
{
cout << -1 << '\n';
}
else
{
cout << stack[stack_size - 1] << '\n';
}
}풀이
그냥 if else if문으로 해결하였다..
구현은 어렵지 않았다.. 깔끔하게 코드를 부분이 핵심인 문제인듯 하다.
cpp는 enum switch문이 왜 안되는 걸까
JAVA의 경우, 그냥 switch문이 입력받은 string으로 잘 적용된다.
CPP의 경우, 반드시 정수계열 형식이나, 열거형 형식이 있어야만 한다..
6. 1302 - Map / Iterator / List.sort(문자열비교)
https://life-with-coding.tistory.com/305
https://blockdmask.tistory.com/76
해결
#include <iostream>
#include <map>
#include <list>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
string name;
int max = 0;
// 가장 많이 팔린 책들을 담을 리스트
list<string> bestseller;
// 책 각각이 몇권 팔렸는지에 대한 map
map<string, int> books;
for (int i = 0; i < N; i++)
{
cin >> name;
if (books.find(name) != books.end())
{
books[name]++;
}
else
{
books.insert({name, 1});
}
}
//가장 많이 팔린 매수를 셈
for (auto iter = books.begin(); iter != books.end(); iter++)
{
if (max <= iter->second)
{
max = iter->second;
}
}
//가장 많이 팔린 매수에 해당하는 책들을 가져옴
for (auto iter = books.begin(); iter != books.end(); iter++)
{
if (max == iter->second)
{
bestseller.push_back(iter->first);
}
}
bestseller.sort();
cout << bestseller.front();
return 0;
}해결
가장 많이 언급된 책을 꼽는데, 언급된 정도가 동일하다면,
사전순으로 가장 맨 앞의 것만 출력하는 문제였고,
인기도관련된 것은 map으로 쉽게 풀어봤기에 술술 풀었지만,
마지막에 같은 인기도의 것들을 따로 모아서
각 문자하나하나마다 for문 돌려서 문자열비교를 하려고 생각하니 막막했다.
그 와중에 list라는 자료구조를 보았고,
CPP의 List는 sort를 하면, 자동으로 정렬해준다고 해서,
그대로 썼다.
그리고 front값만 가져오니 해결...
🎃sort 정말 좋다..
STL을 공부하면 할수록, 구현된 기능을 알차게 쓸 수 있으므로,
날잡고 STL만 한 번 파둬야겠다.
7. 9613 - 유클리드 호제법 / Vector
= 최대공약수 / GCD / 유클리드 알고리즘
시도
#include <iostream>
#include <vector>
using namespace std;
int GCD(int, int);
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int N;
cin >> N;
int T;
int num;
// N개의 줄을 받음
for (int i = 0; i < N; i++)
{
vector<int> arr;
int sum = 0;
// 줄마다 T개의 원소들을 받음
cin >> T;
if(T==1){
cout << sum << '\n';
break;
}
for (int t = 0; t < T; t++)
{
cin >> num;
arr.push_back(num);
}
// Debug 원소 출력
// for (int t = 0; t < T; t++)
// {
// cout << arr.at(t) << ", ";
// }
for (int q = 0; q < T - 1; q++)
{
for (int p = q+1; p < T; p++)
{
//debug
//cout << "{q : " << q << " p: " << p << "} \n";
if (arr.at(q) >= arr.at(p))
{
//debug
//cout << "+ "<< GCD(arr.at(q),arr.at(p)) <<'\n';
sum += GCD(arr.at(q),arr.at(p));
}
else
{
//debug
//cout << "+ "<< GCD(arr.at(p),arr.at(q)) <<'\n';
sum += GCD(arr.at(p),arr.at(q));
}
}
}
cout << sum << '\n';
}
return 0;
}
// 유클리드 호제법
int GCD(int a, int b)
{
int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}틀렸다고 나온다.
질문게시판을 보니, sum이 int범위를 넘을 수 있어서 생기는 오류라고 한다.
어떻게?
해결
풀이
int였던 sum을
long으로 바꾸니 그냥 풀렸다.
- why use long
조건을 보았을 때, N의 개수는 의미없고,
한 케이스에 이런 경우가 있을 수 있다.
100개의 수가 존재하고, 100개가 모두 100 0000인 경우,
100 0000이 GCD이므로, 99! x 100 0000을 하게되면, 무조건 int형의 크기(21억)를 넘게된다.
long을 사용하면 해결된다.
(32비트에선 long이 int와 크기가 같다고 한다.)
그냥 웬만하면 변수 하나는 기본적으로 long을 사용하는게 좋을 듯 하다.
