99클럽 코테 스터디 2일차 TIL C++ 이분탐색, 문자열: "333" < "444" 의 비교가 가능

오늘의 학습 키워드

(1) 문제1 : 문자열
: https://school.programmers.co.kr/learn/courses/30/lessons/147355

(2) 문제2 : 이분탐색, 자료형 (어제 문제 다시풀기)
: https://www.acmicpc.net/problem/1072

공부한 내용 본인의 언어로 정리하기

문제1 :  문자열은 서로 비교할수 있다. ("333" < "444")

 

(1) 문자열은 서로 비교할수 있다. 

문자열끼리의 부등호 연산이 가능한지 몰랐다. 그래서 for문을 돌려가면서, at으로 해당 자리의 값을 꺼내서 비교하는 삽질을 했다.

(2) string::length() : 문자열의 길이 구하기

(3) string::substr(i_startIndex, i_length) : 문자열 자르기

(4) int i_number = stoi(str_number) : string to int

10000자리가 넘는 숫자를 저장하려면, 아래처럼 long long 자료형을 사용해야 한다. int의 범위 보다 큰 수를 서로 비교해야 한다면, string으로 처리하는 것도 고려해보자.

long long int intP = stoll(p);

* 참고 int의 범위 : -2,147,483,648 ~ 2,147,483,647 (10자리 이하의 수만 담을 수 있다.)

 

(5) 전체 풀이

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

using namespace std;

bool compare(string t, string p) {
    /*int i_lenP = p.length();
    for (int i=0;i<i_lenP;i++){
        char c_t = t.at(i);
        char c_p = p.at(i);
        if (c_t < c_p) return true;
        if (c_t > c_p) return false;
    }*/
    // 문자열은 서로 비교할수 있다. 
    
    return t<=p;
}

int solution(string t, string p) {
    string st_tsub;
    int i_lenP = p.length(); // 문자열의 길이 구하기
    int i_lenT = t.length();
    int ans = 0;
    
    for (int i=i_lenP;i<=i_lenT;i++){
        string st_tsubstr = t.substr(i-i_lenP, i_lenP); // 문자열 자르기
        bool b_compare = compare(st_tsubstr, p);
        if (b_compare) ans++;
        
        //cout << st_tsubstr << ">" << p << "->" << b_compare << endl;
    }
    
    return ans;
}

 

문제2

 

(1) 이분탐색의 원형

이분 탐색의 원형을 생각해두면, 나중에 가져다 쓰기 쉬울 것 같다. 자동완성 없이 이분탐색의 원형을 타이핑 할수 있도록 손에 익혀두자. 

 

(2) 주의할점

이 문제에서는 세가지 엣지 케이스를 주의해야 한다. 

첫번째로, 총경기의 횟수(Y)가 0일때 1번만 경기를 이겨도 승률(Z)이 100%가 되므로 1이 정답이 된다. 

두번째로, 총경기의 횟수(Y)와 이긴횟수(X)가 같으면, 이후 경기에서 몇번을 이긴다고 해도 승률(Z)은 계속 100%이다. 그러므로 총경기의 횟수(Y)==이긴횟수(X) 일때에는 -1이 정답이 된다.

 

마지막으로, 현재까지의 승률이 99%일때, -1이 정답이 된다. 왜냐하면, 이미 이긴횟수(X)<총경기횟수(Y)인 상황에서, 몇번을 더 이긴다고 해도, 승률(Z)은 100%가 될수 없다. 

 EX) 100번 경기하고 99번 승리했을 때, 이후 경기를 계속 이긴다고 해도 승률은 99%이다.

순번	전체경기 수	이긴경기 수	승률
1	101	100	99(99.009..)
2	102	101	99(99.019..)
3	103	102	99(99.029..)
4	104	103	99(99.038..)
5	105	104	99(99.047..)

 

(3) 전체 풀이

#include <iostream>
#include <math.h>

using namespace std;
int solve(long long totCnt, long long winCnt);
int getRate(long long totCnt, long long winCnt) {
	long long ans = (100 * winCnt) / totCnt; // totCnt, winCnt가 1억이 넘는 수 이므로, long long으로 처리해야 한다. 
	return ans;
}

int main(int argc, char* argv[]) {
	long long totCnt, winCnt, ans;
	
	cin >> totCnt >> winCnt;
	ans= solve(totCnt, winCnt);
	
	cout << ans << endl;
	
	return 0;
}

int solve(long long totCnt, long long winCnt){
	
	if (totCnt == 0) return 1; // 엣지케이스1
	if (totCnt == winCnt) return -1; // 엣지케이스2
	
	long long right = 1000000000;
	long long left = 1;
	long long mid;
	int rate1 = getRate(totCnt, winCnt);
	int rate2;
    
    if (rate1 == 99) return -1; // 엣지케이스3
	
	while (left <= right){
		mid = (right+left)/2;
		rate2 = getRate(totCnt+mid, winCnt+mid);
		if (rate2>rate1) right = mid-1;
		else left = mid+1;
	}
	
	return left;
}

오늘의 회고

문자열이나 벡터 등 아직 기본적인 활용을 하는 것이 익숙하지 않다. 필요한 기본 문법들에 익숙해져서 빨리 원하는 대로 구성을 할수 있으면 좋겠다.