[C++ 코테] 코딩 테스트 연습 & 알게된점(1)

 

 

백준 2309

 

🔲  내 풀이

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

int n = 9, k = 7;
int a[9];

vector<int> result(7);

void combi(int start, vector<int> b) {
  if (b.size() == k) {
    if (accumulate(b.begin(), b.end(), 0) == 100) {
      copy(b.begin(), b.end(), result.begin());
    }
    return;
  }
  for (int i = start + 1; i < n; i++) {
    b.push_back(a[i]);
    combi(i, b);
    b.pop_back();
  }
}
int main() {
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  vector<int> b;
  combi(-1, b);

  sort(result.begin(), result.end());

  for (int i : result) cout << i << "\n";

  return 0;
}

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 순열을 사용하여 더 쉽게 구할 수도 있었다. next_permutation 사용

 

2️⃣ 9개 중 7개를 뽑는 것보단, 9개 중 2개를 뽑는 편이 더 낫다. 중첩 for문을 통해 해결할 수도 있다.

 

3️⃣ 순열 작성 방법(next_permutation, 재귀함수), 조합(재귀함수) 작성 방법은 머릿속에 박아두자.

 

 

 

 

백준 10808

 

 

🔲  내 풀이

 

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

int main() {

    string s;
    int a[26] = {0, };
    cin >> s;

    for(char c : s) {
        a[(int)c-97] += 1;
    }

    for(int num : a) {
        cout << num << " ";
    }
    
}

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ C++에서 char를 int로 변환을 위해 (int)를 써도 된다.

 

2️⃣ counting star는 map 또는 배열을 사용하자.

 

3️⃣ String 기반이면 map을 사용하고, Int 기반이면 Array를 사용하는 편이다.

 

4️⃣ A는 65, a는 97만 외워두자.

 

5️⃣ 숫자 대신 'a'를 넣어도 된다.

 

 

 

백준 2979

 

 

🔲  내 풀이

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


int main() {
    int a, b, c;
    int max = 0;
    int min = 101;
    cin >> a >> b >> c;

    map<int, int> mp;
    int result = 0;

    for(int i=0; i<3; i++) {
        int start, end;
        cin >> start >> end;
        mp[start] = end;
        if (max <= end) max = end;
        if (min >= start) min = start;
    }

    for(int i=min; i<=max-1; i++) {
        int cars = 0;
        for(auto it : mp) {
            if (it.first <= i && it.second - 1 >= i) {
                cars++;
            }
        }

        if (cars == 1) {
            result += a;
            cout << "car가 1인 경우" << "\n";
            cout << i << "\n";
        } else if (cars == 2) {
            result += b*2;
            cout << "car가 2인 경우" << "\n";
            cout << i << "\n";
        } else if (cars == 3) {
            result += c*3;
            cout << "car가 3인 경우" << "\n";
            cout << i << "\n";
        }
    }
    cout << result << "\n";
    return 0;

}

 

이렇게 푸니 틀렸다고 뜨더라.. 조금만 바꾸면 될 것 같긴한데, 그 보다 counting 배열을 쓰는 편이 훨신 편해보이긴한다.

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 이러한 문제는 counting 배열을 생각했어야 했다.

 

2️⃣시각은 이상/미만으로 생각하는 것이 좋다.

 

 

🔲 올바른 코드

 

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


int main() {
    int a, b, c;
    int start, end;
    int cnt[101] = { 0, };
    int ret = 0;
    cin >> a >> b >> c;

    for(int i=0; i<3; i++) {
        cin >> start >> end;
        for(int j=start; j<end; j++) cnt[j]++;
    }

    for(int j=1; j<100; j++) {
        if(cnt[j]) {
            if (cnt[j] == 1) ret += a;
            else if (cnt[j] == 2) ret += 2*b;
            else if (cnt[j] == 3) ret += 3*c;
        }
    }
    cout << ret << "\n";
    return 0;

}

 

 

 

 

 

백준 10988

 

🔲  내 풀이

 

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

int main() {
    string s;
    bool isP = 1;

    cin >> s;

    for(int i=0; i<s.length(); i++) {
        if (s[i] != s[s.length() - i - 1]) {
            isP = 0;
        }
    }

    cout << isP << "\n";
    
}

 

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ reverse()라는 함수를 사용해서 풀어도 된다. 뒤집어서 같으면 1출력, 다르면 0출력을 하면된다.

 

 

 

 

 

 

 

백준 1159

 

 

🔲  내 풀이

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

int main() {
    int n;
    int arr[26] = { 0, };
    string result = "";

    cin >> n;

    for(int i=0; i<n; i++) {
        string s;
        cin >> s;

        arr[s[0] - 'a'] ++;
    }

    for(int i=0; i<26; i++) {
        if (arr[i] >= 5) {
            char c = char(i+97);
            result += c;
        }
    }
    if (!result.size()) cout << "PREDAJA";
    else cout << result;
}

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ char(i + 97)도 되지만, 그냥 i + 97하고 앞의 타입만 char나 string이면 자동 캐스팅 된다.

 

 

 

 

 

 

백준 11655

 

 

🔲  내 풀이

 

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

int main() {

    string s, ret;
    getline(cin, s);

    for(char c : s) {
        if (c >= 'A' && c <= 'Z') {
            if (char(c + 13) > 'Z') {
                ret += char(((int)c + 13) - 'Z' + 64);
            } else {
                ret += char(c+13);
            }
        } else if (c >= 'a' && c <= 'z') {
            if (char(c+13) > 'z' || c+13 > 126) {
                ret += char(((int)c + 13) - 'z' + 96);
            } else {
                ret += char(c+13);
            }
        } else {
            ret += c;
        }
    }

    cout << ret << "\n";
    return 0;
}

 

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 왠만하면 숫자로 비교하자. 아스키 코드 지원은 126까지 밖에 안되서 문자로 비교할 시, 오류가 날 수 있다. 즉, 숫자로 비교하는 로직을 짜자.

 

2️⃣ 그냥 c + 13 - 26을 해도 되었다.

 

 

 

백준 9996

 

 

🔲  내 풀이

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

vector<string> split(const string& input, string delimeter) {
  vector<string> result;
  auto start = 0;
  auto end = input.find(delimeter);

  while (end != string::npos) {
    result.push_back(input.substr(start, end - start));
    start = end + delimeter.size();
    end = input.find(delimeter, start);
  }

  result.push_back(input.substr(start));
  return result;
}

int main() {
  int n;
  cin >> n;
  string hint;
  cin >> hint;

  vector<string> lists = split(hint, "*");

  for (int i = 0; i < n; i++) {
    string s;
    string isP = "DA";
    cin >> s;

    if (lists[0].size() + lists[1].size() > s.size()) {
      isP = "NE";
    } else {
      for (int j = 0; j < lists[0].size(); j++) {
        if (s[j] != lists[0][j]) isP = "NE";
      }

      for (int j = 0; j < lists[1].size(); j++) {
        if (s[s.size() - 1 - j] != lists[1][lists[1].size() - 1 - j])
          isP = "NE";
      }
    }

    cout << isP << "\n";
  }
}

 

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 이 문제는 반례 찾기가 어렵다. 들어오는 문자열의 사이즈를 체크해야하기 때문이다. 모든 경우의 수를 항상 생각하며 풀자.

 

2️⃣ split 함수 대신에 find와 substr만 사용해도 좋다. 어짜피 한 부분 밖에 split하지 않기 때문이다.

 

3️⃣ for문으로 문자 하나하나 비교 x -> substr을 통해서 한번에 비교가 가능하다.

 

 

 

 

 

 

 

백준 2259

 

 

🔲  내 풀이

 

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

int maxInfo = -101;
vector<int> arr;

int n, k;

void getMax() {
  auto start=arr.begin();
  auto end = start + k;
  while(end != arr.end() + 1) {

    int temp = accumulate(start, end, 0);
    if (temp >= maxInfo) {
      maxInfo = temp;
    }

    start++;
    end++;
  }
}

int main() {

  
  cin >> n >> k;
  for(int i=0; i<n; i++) {
    int value;
    cin >> value;
    arr.push_back(value);
  }
  
  getMax();

  cout << maxInfo << "\n";


}

 

시간 초과가 났다.

 

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 구간 합 문제라는 것을 알아차려야 한다.

 

 

2️⃣ 이 문제의 최솟 값은 -1,000,0000이라는 것을 알아야 한다. 실제로는 이 수보다 살짝 작은(4정도) 값을 더 빼주는 것이 좋다

 

3️⃣ 성능 향상을 위해 아래 cin, cout 시 아래 구문을 써주자.

ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);

 

c++만의 독립적이 버퍼를 생성하게 하여 실행 속도가 빨라진다.

 

4️⃣ 구간 합 공식은 아래와 같다.

 

for(int i=1; i<=n; i++) {
    cin >> temp; psum[i] = psum[i-1] + temp;
}

for(int i=k; i<=n; i++) {
    ret = max(ret, psum[i] - psum[i-k]);
}

 

psum[i] - psum[i-k]를 해보면, k가 2일때, psum[2] - psum[0], psum[3] - psum[1] ... 과 같이 구간 마다의 합을 구할 수 있다.

 

 

 

🔲 올바른 코드

 

#include <bits/stdc++.h>
using namespace std;
int n, k, temp, psum[100001], ret = -10000004;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  cin >> n >> k;
  for(int i=1; i<=n; i++) {
    cin >> temp; psum[i] = psum[i-1] + temp;
  }

  for(int i=k; i<=n; i++) {
    ret = max(ret, psum[i] - psum[i-k]);
  }

  cout << ret << "\n";
  return 0;

}

 

 

 

 

 

 

백준 1620

 

 

🔲  내 풀이

 

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


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int n, m;
  map<string, int> lists;

  cin >> n >> m;

  for(int i=0; i<n; i++) {
    string temp;
    cin >> temp;
    lists[temp] = i+1;
  }

  for(int i=0; i<m; i++) {
    string input;
    cin >> input;

    if (atoi(input.c_str()) != 0) {
      int number = atoi(input.c_str());
      
      for(auto value : lists) {
        if (value.second == number) {
          cout << value.first << "\n";
        }
      }
    } else {
      cout << lists.at(input) << "\n";
    }

  }
}

 

 

시간 초과가 났다.

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ map을 사용할 때, key를 통해 value를 찾는데는 O(logN)만큼 걸리나, value를 통해 key를 찾을 때는 훨씬 많이 걸린다.

 

2️⃣ 이를 보완하기 위해서, map 자료구조를 2개를 사용하는 방법을 사용한다. string-int, int-string 조합으로 두개를 만들면, 짧은 시간 복잡도 이내에 key와 value의 탐색이 가능하다.

 

3️⃣ atoi(string.c_str())을 사용하면 문자열이 숫자라면 해당 숫자를 내놓고, 문자라면 0을 내놓는다.

 

 

 

 

 

백준 9375

 

 

🔲  내 풀이

 

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

int main() {

  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int n;
  cin >> n;

  for(int i=0; i<n; i++) {
    int m;
    cin >> m;
    map<string, int> mp;
    for(int j=0; j<m; j++) {
      
      string s, t;

      cin >> s >> t;

      mp[t] += 1;
    }
    int result = 1;
    for(auto j : mp) {
      result *= (j.second + 1);
    }
    result -= 1;

    cout << result << "\n";
  }

  return 0;
}

 

 

 

🔲 보완할 점 & 알게된 점

 

 

1️⃣ 경우의 수 문제는 일일이 세는 방식도 있지만, 전체 경우의 수에서 특정 경우의 수를 빼는 방식도 생각할 수 있다.

 

2️⃣ map에서 int의 초기화 값은 0이다.

 

 

 

 

 

 

백준 1213

 

 

🔲  내 풀이

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  string s;
  cin >> s;
  map<char, int> mp;

  for (char c : s) {
    mp[c]++;
  }

  int even_num = 0;
  for (auto item : mp) {
    if (s.length() % 2 == 0 && item.second % 2 == 1) {
      cout << "I'm Sorry Hansoo"
           << "\n";
      exit(0);
    }
    if (s.length() % 2 == 1) {
      if (item.second % 2 == 1) {
        even_num++;
      }
    }
  }
  if (even_num != 1 && s.length() % 2 == 1) {
    cout << "I'm Sorry Hansoo"
         << "\n";
    exit(0);
  }

  string temp = "";
  string result = "";
  if (s.length() % 2 == 0) {
    for (auto item : mp) {
      for (int i = 0; i < item.second / 2; i++) {
        temp += item.first;
      }
    }
    result += temp;
    reverse(temp.begin(), temp.end());
    result += temp;
  } else {
    string middle;
    for (auto item : mp) {
      if (item.second % 2 == 1) {
        item.second--;
        middle = item.first;
      }
      for (int i = 0; i < item.second / 2; i++) {
        temp += item.first;
      }
    }
    result += temp;
    result += middle;
    reverse(temp.begin(), temp.end());
    result += temp;
  }

  cout << result << "\n";
}

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ string을 reverse하기 위해서, reverse(s.begin(), s.end())를 사용하면 된다.

 

2️⃣ 홀수 체크는 cnt[i] & 1과 같은 식으로도 가능하다.

 

3️⃣return string을 만들고, for문으로 양 옆에 추가하는 방식으로 짜도된다. +=2를 하면 코드 수도 줄일 수 있다.

 

4️⃣홀수일 때, mid값을 insert하는 처리로 가는 것이 조금 더 편하다.

 

 

🔲 개선된 코드

#include<bits/stdc++.h> 
using namespace std; 
string s, ret; 
int cnt[200], flag; 
char mid;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	for(char a : s)cnt[a]++;
	for(int i = 'Z'; i >= 'A'; i--){
		if(cnt[i]){
			if(cnt[i] & 1){
				mid = char(i);flag++;
				cnt[i]--;
			}
			if(flag == 2)break;
			for(int j = 0; j < cnt[i]; j += 2){
				ret = char(i) + ret; 
				ret += char(i);
			}
		}
	}
	if(mid)ret.insert(ret.begin() + ret.size() / 2, mid);
	if(flag == 2)cout << "I'm Sorry Hansoo\n";
	else cout << ret << "\n"; 
}

 

 

 

 

 

백준 1940

 

🔲  내 풀이

 

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

int n, m;
int result = 0;
int arr[15001];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> n;
  cin >> m;

  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    arr[i] = a;
  }
  
  for(int i=0; i<n; i++) {
    for(int j=0; j<i; j++) {
      if (arr[i] + arr[j] == m) {
        result++;
      }
    }
  }

  cout << result << "\n";
}

 

 

🔲 보완할 점 & 알게된 점

 

 

1️⃣ 처음에는 조합을 사용하기 위해 재귀함수를 사용하였다. 그러자 메모리 초과가 났고, 이는 스택에 함수가 쌓여 발생함을 알게되었다.

 

2️⃣ 그래서 중첩 for문으로 메모리 초과를 막았다.

 

3️⃣ 만약 시간 초과가 빡세다면, 안되는 경우는 if문으로 체크해야 한다.

if(m > 200000) cout << "0" << "\n";

 

 

 

 

 

 

 

백준 3986

 

 

🔲  내 풀이

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);

  int n;
  string s;
  int ret=0;

  cin >> n;
  for(int i=0; i<n; i++) {
    
    cin >> s;
    stack<char> stk;

    for(char a : s) {
      if (stk.size() && stk.top() == a) stk.pop();
      else stk.push(a);
    }
    if (stk.size() == 0) ret++;
  }
  cout << ret << "\n";
}

 

 

🔲 보완할 점 & 알게된 점

 

 

1️⃣ 문제를 볼 때 이해가 안된다면, 도식화하거나 그림을 그린다. 90도 회전, 뒤집어 보기, 붙여보기

 

2️⃣ 스택을 사용한다. 폭발을 일으키자..!

 

3️⃣ 문제에서 짝짓기, 폭발이라는 단어가 있다면 스택을 생각해보자.

 

 

 

 

 

 

백준 1629

 

🔲 개선된 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b) {
  if (b == 1) {
    return a % c;
  }

  ll ret = go(a, b / 2);
  ret = (ret * ret) % c;
  if (b % 2) ret = (ret * a) % c;
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> a >> b >> c;
  cout << go(a, b) << "\n";
  return 0;
}

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 깡으로 곱하는 것보단, 재귀적으로 들어가면 곱하는 것이 시간 복잡도가 더 줄어드는 경우가 있다. Log 시간으로 줄어들기 때문이다. 예를들어, 단순한 a를 여러번 곱하는 것이 재귀함수를 사용함으로써, 로그시간으로 줄어든다.

 

2️⃣ (a + b) % c = a % c + b % c, (a * b) % c = a % c * b % c, 값이 overflow가 되는 것을 방지하기 위함. 정수론의 일종

 

3️⃣ 정수론의 모듈 연산을 통해 overflow 방지, 재귀함수를 통한 곱하기의 시간 복잡도 줄이기

 

 

 

 

 

백준 4375

 

 

🔲  내 풀이

 

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

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);
  // cout.tie(NULL);
  ll n;

  while(cin >> n) {
    ll num = 1;
    bool is_not_done = true;
    int result = 1;
    while(is_not_done) {
      if (num % n == 0) {
        is_not_done = false;
        cout << result << "\n";
      } else {
        string new_num = to_string(num);
        new_num += "1";
        result++;
        num = stoll(new_num);
      }
    }
  }
  return 0;
}

 

런타임 에러가 났다.

결국 long long도 벗어나는 숫자가 만들어지므로, 모듈 연산을 통해 overflow를 방지하여야 한다.

 

 

🔲 보완할 점 & 알게된 점

 

1️⃣ 정수론의 모듈연산을 통해서 % 연산을 분산화 시켜주어야 한다.

 

 

 

🔲 개선된 코드

 

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

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);
  // cout.tie(NULL);
  ll n;

  while(cin >> n) {
    ll num = 1;
    bool is_not_done = true;
    int result = 1;
    while(is_not_done) {
      if (num % n == 0) {
        is_not_done = false;
        cout << result << "\n";
      } else {
        num = (num * 10) + 1;
        num %= n;
        result++;
      }
    }
  }
  return 0;
}

 

 

 

 

 

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 - 인프런