||문제 이해

총 학생수에서 친구관계인 학생들끼리 두명씩 묶어 나오는 경우의 수 구하기

단 순서 변경이나 중복은 허용되지 않는다.

||구현

set<int> friends[11];
bool check[11];

/* maxi - 총 학생 수
 * cnt - 짝을 지어야 하는 수, 짝을 지을때마다 감소하여 최종 0이 된다.
 * result - 문제의 결과 값
 */
void Counting(const int & maxi, int cnt, int & result)
{
	//모든 학생을 다 짝지었는지 확인
	if (cnt == 0)
	{
		++result;
		return;
	}

	//시작 할 학생 찾기
	int start;
	for (int i = 0; i < maxi; ++i)
	{
		if (check[i] == false)
		{
			start = i;
			break;
		}
	}

	//짝을 짓기
	for (int i = start + 1; i < maxi; ++i)
	{
		//start학생이 아니고 아직 짝이 지어지지 않았다면
		if (check[i] == false)
		{
			//서로 친구라면
			if (friends[start].find(i) != friends[start].end())
			{
				//짝을 지었다는 체크를 해주고
				check[start] = true;
				check[i] = true;

				//다음 학생을 찾는다.
				Counting(maxi, cnt - 1, result);
				
                //찾고나면 다시 체크를 풀어준다.
				check[start] = false;
				check[i] = false;
			}
		}
	}
}

||되돌아보기

이번 문제와 같이 항상 완전탐색을 너무 어렵게 생각하는 경향이 있다.

침착하게 차근차근 생각해보자

이런 같은 답을 중복으로 세는 상황에서 중복이 나오지 않게 세는 방법을 집중적으로 생각해보는것도 좋을 것 같다.

예로 묶음 0,1과 1,0이 같은 경우지만 다르게 인식하여 세고 있다면

미리 사전순으로만 묶음이 생기게 한다면 1,0 같은 경우는 나오지 않을거다.

즉, 특정 형태를 갖는 데이터들을 만드는것!

||개선 코드

종만북의 코드다

int n;
bool areFriends[10][10];

int Counting(bool taken[10])
{
	//가장 빠른 번호를 찾는다.
	bool first = -1;
	for (int i = 0; i < n; ++i)
	{
		if (taken[i] == false)
		{
			first = i;
			break;
		}
	}

	//기저 사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
	if (first == -1) return 1;

	int ret = 0;
	//짝지을 학생을 결정하기
	for (int second = first + 1; second < n; ++second)
	{
		if (taken[second] == false && areFriends[first][second])
		{
			taken[first] = taken[second] = true;
			ret += Counting(taken);
			taken[first] = taken[second] = false;
		}
	}
	return ret;
}

||문제 이해

제시된 7단계의 문자열 규칙에 따라 입력받은 문자열을 변경

||해결 계획

단순 문자열 다루기 구현이라 어떠한 함수를 사용할지 고민을 했다.

좀 생각했던건 

3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다

이 연속된 마침표를 하나만 남기고 어떻게 제거할까 생각하다가

중복? unique? 이렇게 생각이 나서 unique를 해보면 어떨까 생각했고

정렬을 하지 않은 원상태 그대로의 연속된 중복제거이기에 unique가 정말 잘 어울린다고 결론을 내렸다.

나머지는 erase, front, back, begin, end, size 를 통해 쉽게 구현이 가능하다.

||계획 검증

모두 단순 string class의 함수를 사용하는것이라 시간만 검증해보면 됐다.

입력된 문자열의 최대 길이는 1000이다.

사용한 string class의 함수를 보면 최대 O(n)으로 짐작할 수 있으므로

시간은 충분하다고 생각하고 구현했다.

||오답 원인

개~~~~~멍청하게 이거 하나때문에 30분을 날려먹었다.

다음엔 이런 실수는 하지 말자ㅠㅠ

||구현

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

bool myUnique(const int & a, const int & b)
{
	if (a == '.') return a == b;
	return false;
}

string solution(string new_id) {
	string answer = "";

	for (auto & d : new_id)
	{
		if ('A' <= d && d <= 'Z')
			answer += tolower(d);
		else if (d == '-' || d == '_' || d == '.' || ('0' <= d && d <= '9') || ('a' <= d && d <= 'z'))
			answer += d;
	}

	answer.erase(unique(answer.begin(), answer.end(), myUnique), answer.end());

	if (answer.front() == '.') answer.erase(answer.begin());
	if (answer.back() == '.') answer.pop_back();

	if (answer.size() == 0) answer = "a";

	if (16 <= answer.size()) answer.resize(15);
	if (answer.back() == '.') answer.erase(answer.end() - 1);

	while (answer.size() <= 2) answer += answer.back();

	return answer;
}

||되돌아보기

단순 string class의 함수를 다룰줄 알아? 라는 문제였던것같다.

1단계지만 40분이나 걸려서 더 열심히 공부해야겠다는 생각이 든다😪

||개선 코드

    for(auto & d : new_id)
    {
        if('A' <= d && d <= 'Z')
            answer += tolower(d);
           
        //내 코드/////////////////////////////////////////////////////////////////////
        else if(d == '-'|| d == '_' || d == '.' || ('0' <= d && d <= '9') || ('a' <= d && d <= 'z'))
            answer += d;
        //다른 분의 개선코드//////////////////////////////////////////////////////////
        else if(strchr("-_.",d) ||('0' <= d && d <= '9') || ('a' <= d && d <= 'z'))
            answer += d;
    }

저 한부분을 좀 편하게 사용할 수 있는 방법이 있었는데

strchr이란 함수를 사용하는 것!

문자열안에 문자가 있으면 문자의 포인터를, 없으면 null을 반환한다.

훨씬 깔끔하고 보기 좋다ㅎㅎ

||문제 이해

주어지는 여러 무게의 추를 조합하여 만들 수 없는 최소 무게를 구해라

||해결 계획

Greedy를 사용한다.

오름차순으로 정렬 후, [ i번째 까지의 누적합 + 1 < i번째 추의 무게 ] 가 true면

i번째 까지의 누적합 + 1이 정답이다.

||계획 검증

만들수 있는 최대 무게를 m이라 가정한다.

그럼 0 ~ m 의 무게를 만들수 있다.

여기서 무게 k인 추를 추가할 때 k가 m보다 + 1만큼 무겁다고 가정하자.

그럼 다시 만들수 있는 무게는 0, 1, 2, ..... m, k, k+1, k+2, ...... k + m 이 가능하다.

이런 범위는 k가 k <= m + 1 라면 k + m이하인 무게를 만들수 있는건 변함없다.

반면 k가 m보다 + 2만큼 무겁다고 가정한다.

그럼 다시 만들수 있는 무게는 0, 1, 2, ..... m, m + 1, k, k+1, k+2, ...... k + m 이 가능하다.

보다시피 m + 1은 만들수 없는 무게다.

고로 m + 1 < k 면 m + 1이 만들수 없는 최소 무게인것.

만들수 있는 무게의 범위는 모든 추의 무게를 합한것과 같다.

예를 들면

추 = { 1, 1, 3, 8 }

i번째까지 추의 누적합 : sum(i)

i번째의 추 : a(i)

sum(0) 은 0이다. 여기서 첫번째 무게 1의 추를 추가할 것이다.

sum(0) + 1 < a(1) == false 이므로 만들수 있는 무게는 0 ~ sum(0) + a(1)이다. ( 0 ~ 1)

sum(1) 은 1이다. 여기서 두번째 무게 1의 추를 추가할 것이다.

sum(1) + 1 < a(2) == false 이므로 만들수 있는 무게는 0 ~ sum(1) + a(2)이다. ( 0 ~ 2)

sum(2) 은 3이다. 여기서 세번째 무게 3의 추를 추가할 것이다.

sum(2) + 1 < a(3) == false 이므로 만들수 있는 무게는 0 ~ sum(2) + a(3)이다. ( 0 ~ 5)

sum(3) 은 5이다. 여기서 네번째 무게 8의 추를 추가할 것이다.

sum(3) + 1 < a(4) == true이므로 만들수 없는 최소 무게는 sum(3) + 1 이다. ( 6 )

||구현

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int arr[1001];
	int n; cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);

	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		if (sum + 1 < arr[i]) break;
		sum += arr[i];
	}
	cout << sum + 1;
	return 0;
}

||되돌아보기

일단 자력으로 풀지 못했고

혼자 생각 못한 이유라면, 이 문제는 가정과 식을 통해 쉽게 추론할 수 있는 문제였는데

내가 아직 식으로 가정 해보는게 서툴러서 도달하지 못했던것 같다.

항상 식으로 논리있는 문제풀이를 하려고 계속 노력하고 있지만

이렇게 가정을 아직 많이 해본적은 없어서 좀 더 식으로 서술 하는 법을 배웠다.

||문제 이해

유저는 여러명에게 신고할 수 있지만 한명의 유저에 대해 신고 스택을 1만 쌓을수 있다.

k번 이상 신고 된 유저는 정지당하고 그 유저를 신고한 사람들에게 정지 완료 처리 메일을 보내려고 한다.

각 사람들마다 정지 완료 처리 메일을 받은 개수를 구해라

||해결 계획

1.

report를 순차로 돌면서 map<"신고 당한 사람", set<"신고를 한 사람들">> 형식으로 저장한다.

여기서 vector<"신고를 한 사람들">.size( )가 곧 신고 받은 횟수이다.

2.

위에 저장한 map을 돌면서 신고 횟수가 k개 이상인지 확인한다.

이용 정지 조건에 충족한다면 set<"신고를 한 사람들">을 모두 탐색하면서

map<"처리 메일을 받을 사람", 그 개수>에 저장한다.

3.

위에서 id_list를 순차 탐색하면서 위에서 새로 저장한 map에서 찾아본다.

위에서 저장되지 않았으면 0이니, 0을 answer에 넣어주고

따로 개수가 저장되어있으면 그 개수를 answer에 넣어준다.

||계획 검증

중요한 입력에는 id_list와 report가 있는데

id_list < 1'000, report <= 200'000 이고

id_list는 3번에 순차탐색하는 것이라 가볍게 넘어갈 수 있고

가장 입력값이 큰 report에 관련있는 1번만 검사 해보려한다.

1번에서 중요했던건 신고자와 신고당한자를 나눈것이였다.

substr은 O(n) = 21

n은 원본 문자열의 길이인데 최대 21이다.

find는 O(nm) = 21

n은 원본 문자열의 길이인데 최대 21이다.

m은 찾으려는 문자열의 길이인데 나는 공백을 찾을것이므로 1이다.

이를 총 두번씩할 예정이기에 42 + 42 = 84

그리고 이는 report개수만큼 반복된다.

84 * 200'000 = 16'800'000 로 충분한것 같다!

||구현

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

map <string,set<string>> m;
map <string,int> mm;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    //1. <신고당하는자, 신고한자들> 저장
    int idx;
    string a, b;
    for (const auto & d : report)
    {
        a = d.substr(0, idx = d.find(" "));
        b = d.substr(idx = d.find(" ") + 1);
        m[b].insert(a);
    }
    //2.정지 이용자 찾고 찾으면 map<신고한자들,처리메일개수>에 개수를 올린다.
    for(auto d: m)
    {   
        if(k <= d.second.size())
        {
            for(auto e : d.second) ++mm[e];
        }
    }
    //3.id_list의 사용자들의 개수를 answer에 넣는다.
    for(auto d: id_list)
    {
        if (mm[d] == 0) answer.push_back(0);
        else answer.push_back(mm[d]);
    }
    
    return answer;
}

||되돌아보기

해결 방법을 써 놔도 정리가 안돼서 저장해야할 것을 적어봤었다.

처음에는 신고 당한자, 신고를 한자들, 신고 당한자의 횟수

근데 여기서 신고 당한자의 횟수는 즉 신고를 한자들의 개수와 동일했다!

그래서 나는 사실 이 두개를 하나로 저장할 수 있었다!

이 때문에 좀 구현하기 수월했다.

||개선 코드

이번에 어디서 개선시킬수 있을까 생각했는데

아마 report의 문자열을 나누는 지점이 아닐까 싶었다.

그래서 고민도 해보고 여러 사람들의 코드도 보았는데

코드는 간단한게 있었지만 시간은 내게 조금더 빨랐거나 비슷했다.

1. 이렇게 stringstream을 사용 하여 편하게 나눌 수 있었다.

for (const auto& s : report) {
        stringstream in(s);
        string a, b; in >> a >> b;
        v.push_back({ Conv[a], Conv[b] });
}

이러한 스트림을 이용한건 정말 편하지만

substr와 find를 이용하여 나눈것이 미세하게 빨랐다.

2. sort 후 unique로 중복제거.

sort(s.begin, s.end);
s.erase(unique(s.begin(), s.end()), s.end());

나는 이러한 중복제거를 예외처리하려고 set에 저장하여 중복을 회피했다.

||문제 이해

숫자와 영문이 섞인 문자열을 숫자로 변경하여 리턴해라.

||해결 계획

pair<int , int> p라는 변수에 first는 인덱스, second는 해당 숫자를 저장할 것이다.

1번 for문에는 단어만을 검색하여 p에 저장,

2번 for문 에는 숫자만을 검색하여 p에 저장

그 후 인덱스(fisrt)를 기준으로 오름차순 sort 하여 순서대로 합쳐 리턴한다.

||계획 검증

1번 for문에는 string::find를 사용할 것이기 때문에 가장 큰 문자 길이 eight의 5를 곱했다.

find : 시간 복잡도는 찾으려는 문자 길이 * 원본 문자열 길이

단어 개수 * find = 10 * n * 5 = O(50 * n)

2번 for문에는 문자열 길이만큼 반복하여 저장한다 = O(n)

즉, O(50 * n + n) 이므로 최대 50 * 50 + 50 = 2550 번 연산으로 끝낼 수 있다.

||오답 원인

1. while과 find의 환장의 조합 - 1

이는 무한 루프다.

find가 계속 인덱스 0 부터 찾는 것을 막기 위해 j + 1을 했었는데 사용하지 않은 어리석은 케이스

find는 항상 인덱스 0 부터 찾을 것이다. one을 찾아도 다음에도 같이 ond을 찾을 것이다.....

이 때문에 많은 시간 소모를 했다...

2. while과 find의 환장의 조합 - 2

찾지 못하면 npos를 반환하는 find로 못 찾을 때까지 반복하여

반복문 내부에서 찾은 영어단어를 숫자로 변환하여 저장하려고 했다.

근데 만약 s가 "one4zerotwo"라 한다면 이 코드는 one을 저장할 수 없다.

왜냐면 처음 찾은 one이 인덱스 0을 반환한다, 이는 즉 false와 같으므로 반복문 내부에 들어가지 못하여 저장할 수 없다.

2. 내 착각

어찌어찌 저 for문은 넘어가고 

처음에는 문자열을 순차적으로 탐색하여 문자와 숫자 한 번에 변환하여 저장하려고 했다.

string s = "one4twozero";

for(int i = 0; i < s.size(); ++i)
{
	if(s[i] 가 문자면)
    {
    	for( 0 ~ 10 )
        {
        	if(s.find(모든 문자) != npos)
            {
            	찾으면 저장 후 break
            }
        }
    }
    if(s[i] 가 숫자면)
    {
    	숫자 - '0' 후 저장
    }
}

근데 여기서 웃긴 게 처음 탐색인 i가 0일 때 찾는 문자는 'o'이다.

그러면 이 i부터 one인지, two인지, three인지 탐색하여 맞는 것으로 저장한다.

여기서 나는 one을 변환했으니까 다음 탐색은 4겠지??라고 무의식 속에 사로잡혀있었다.

근데 다음 탐색은 놀랍게도 'n'이다.

그러면 n부터 탐색된 two가 나와 1 다음 2가 나오게 된 것 ㅋㅋㅋ

좀 더 자세히 생각해야겠다..

||구현

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

const string num[10] = { "zero","one","two","three","four","five","six","seven","eight","nine" };

typedef pair<int, int> pii;
vector<pii> v;

int solution(string s) {
	int answer = 0;

	//문자만 변환하는 곳
	int i, j;
	size_t t;
	for (i = 0; i < 10; ++i)
	{
		t = 0;
		do
		{
			t = s.find(num[i], t);
			if (t != string::npos)
			{
				v.push_back({ t++, i });
			}
			else break;
		} while (true);
	}
	//숫자만 변환하는 곳
	for (i = 0; i < s.size(); ++i)
	{
		//숫자가 영어보다 아스키코드가 작음
		if (s[i] <= '9')
		{
			v.push_back({ i,s[i] - '0' });
		}
	}
	sort(v.begin(), v.end());

	for (const auto & d : v)
	{
		answer = answer * 10 + d.second;
	}

	return answer;
}

||되돌아보기

처음에 한 번에 저장하려는 풀이가 정확하게 그려지지 않음에도 쉬워 보인다고코드를 작성하여

이것저것 시간을 많이 소모했고 find도 내가 자세히 알지 못하여 시간을 소모했다..

많은 반성을 하게 됐다..

이번에 풀게 될 수 있었던 핵심은 통일이다.

문자 먼저 모두 pair<인덱스(int),해당 숫자(int)>형으로 저장하고

그다음 숫자도 따로 모두 pair<인덱스(int),해당 숫자(int)>형으로 저장하여 통일했다.

 그 후에는 sort 하고 출력하면 끝!

다른 타입이 섞여있다면 한 번에 하려 하지 말고 하나의 타입씩 연산하는 것도 괜찮았다

||개선 코드

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

int solution(string s) {
    s = regex_replace(s, regex("zero"), "0");
    s = regex_replace(s, regex("one"), "1");
    s = regex_replace(s, regex("two"), "2");
    s = regex_replace(s, regex("three"), "3");
    s = regex_replace(s, regex("four"), "4");
    s = regex_replace(s, regex("five"), "5");
    s = regex_replace(s, regex("six"), "6");
    s = regex_replace(s, regex("seven"), "7");
    s = regex_replace(s, regex("eight"), "8");
    s = regex_replace(s, regex("nine"), "9");    
    return stoi(s);
}

저 regex는 처음 보는데 대강 보니까 유용하게 쓸 수 있을 것 같다.

다음에 좀 공부해야겠다.

||문제 이해

수학을 정말 못하는 상수, 수학을 어릴때 열심히 공부할걸 이라는 생각이 또 드는 문제였다

단순 두 수를 거꾸로 돌려 비교하는 문제.

||해결 계획

String으로 받아 마지막 인덱스부터 비교해 찾으면 된다.

||계획 검증

734, 893

마지막 인덱스부터 비교

4 > 3 

그럼 437 출력

351, 531

마지막 인덱스부터 비교

1 = 1

5 > 3

그럼 351 출력

||구현

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	string a, b, c; cin >> a >> b;
	for (int i = a.size() - 1; 0 <= i; --i)
	{
		if (a[i] == b[i]) continue;

		a[i] > b[i] ? c = a : c = b;
		break;
	}

	for (int i = a.size() - 1; 0 <= i; --i)
	{
		cout << c[i];
	}
	return 0;
}

||되돌아 보기

처음에 이러한 정수의 자리를 가지고 비교하는건 문자열로 다루는게 쉽지 않을까 생각이 가장 먼저 들어서

문자열을 사용했다.

이번 문제 뿐만 아니라 다른 문제도 그랬지만

대부분 항상 정수로 해결하는 나이스한 방법이 존재했다.

이런 방법이 있을때는 보통 이렇게 세자리수 고정. 이런 고정자리수가 많았던거 같다.

다음에는 정말 정수방법 하나와 문자열 방법 하나를 비교해보면서 해야겠다.

특히 고정자리수가 나올때는!!

||개선 코드

내가 반복문을 하나 줄인 코드이다.

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	string a, b, c = ""; cin >> a >> b;
	for (int i = a.size() - 1; 0 <= i; --i)
	{
		if (c == "")
		{
			if (a[i] == b[i])
			{
				cout << a[i];
				continue;
			}
			a[i] > b[i] ? c = a : c = b;
		}
		cout << c[i];
	}
	return 0;
}

그리고 다른 정수로 풀이하는 나이스한 방법이다.

#include <bits/stdc++.h>
#define CAL(x) x = 100 * (x % 10) + 10 * (x / 10 % 10) + x / 100;
using namespace std;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b; cin >> a >> b;
	
	CAL(a);
	CAL(b);

	cout << (a > b ? a : b);
	return 0;
}

||문제 이해

각 문제들의 최소 패널티 총합을 구하는 문제

각 문제는 D(풀이 시간), V(오답판정 개수) 가 있다.

풀이 시간 : 시간은 누적된다!

각 문제의 패널티는 D + (20 * V) 로 구해진다.

||해결 계획

처음은 마땅히 좋은 방법이 생각안나서 시간이 작은것 부터 해볼까라는 생각으로 무작정 시작했다.

이 처럼 같은 전략의 반복은 Greedy가 어울려 Greedy를 사용한다.

||계획 검증

두가지 경우가 있다.

시간의 비교, 오답판정의 비교

어떤 경우를 먼저 해야 하는지 검증해본다.

시간의 비교

두개의 문제가 있다 생각한다.

1번 : D = 10, V = 1

2번 : D = 20, V = 1

시간이 작은것부터 할 경우

1. 10 + 20 = 30

2. 30 + 20 = 50

= 30 + 50 = 80

시간이 큰것부터 할 경우

1. 20 + 20 = 40

2. 30 + 20 = 50

= 40 + 50 = 90

즉, 시간은 작은것부터 해야 최소가 나온다.

오답판정의 비교

두개의 문제가 있다 생각한다.

1번 : D = 10, V = 1

2번 : D = 10, V = 2

오답판정이 작은것부터 할 경우

1. 10 + 20 = 30

2. 20 + 40 = 60

= 30 + 60 = 90

오답판정이 큰것부터 할 경우

1. 10 + 40 = 50

2. 20 + 20 = 40

= 50 + 40 = 90

즉, 오답 판정은 상관 없다.

그럼 시간을 오름차순으로 정렬만 해주고 계산해주면 정답이 나온다.

||구현

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

typedef pair<int, int> pii;
#define Time first
#define Verdict second

//시간을 오름차순으로 정렬
bool comp(const pii & a, const pii & b)
{
	return a.Time < b.Time;
}

pii p[MAX];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	for (int i = 0; i < MAX; ++i)
	{
		cin >> p[i].Time >> p[i].Verdict;
	}
	sort(p, p + MAX, comp);

	int result = 0;
	int time = 0;
	for (auto data : p)
	{
		time += data.Time;
		result += time + (data.Verdict * 20);
	}

	cout << result;
	return 0;
}

||되돌아 보기

일단 숨겨진 조건을 찾기 어려웠다ㅠ (영어라 내가 해석을 잘 못해서 그런걸 수도 있다...)

그 조건은 시간이 누적된다는 점이다.

처음에는 어 그냥 각 문제마다 D + 20 * V 하면 되는거 아니야? 하고 테스트 케이스를 보고 비교했지만

어림도 없었다.

그러다 생각나게 시험이니까 시간이 누적된 시간으로 계산 하는 것인가? 하고 테스트케이스와 비교해서 알아냈다.

영어도 공부 많이 해야겠다..ㅜ

||문제 이해

무한한 자를 수 없는 테이프를 가지고 구멍을 메꿔라

||해결 계획

물이 새는 위치를 오름차순으로 정렬하고 - O(n log n)

순차적으로 탐색하면서 구멍의 위치와 테이프의 길이를 더하여 그 안에 속한 구멍은 패스한다. - O(n)

= O(n log n + n) = O(n log n)

||계획 검증

1000 * log 1000 이므로 1초내에 충분히 끝날것이다.

||구현

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

int arr[1001];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int n, l; cin >> n >> l;
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + n);

	int cnt = 0;
	int end = 0;
	for (int i = 0; i < n; ++i)
	{
		end = arr[i] + l;
		++cnt;
		while(arr[i + 1] < end && arr[i + 1] != 0)
		{
			++i;
		}
	}

	cout << cnt;
	return 0;
}

||되돌아 보기

먼저 겹치는 부분은 의미가 없어서 생각에서 제외했고

해결 방법은 테이프는 자를수 없기 때문에 한번 붙일 때 최대한 많은 구멍을 메꾸는 것이다.

이러한 전략을 반복적으로 취해도 문제가 없다면 그리디를 사용하는게 좋을것 같아 그리디를 선택했다.

||개선 코드

#include<cstdio>
int main() {
	bool a[1001] = { 0 };
	int n, l;
	scanf("%d%d", &n,&l);
	while (n--)
	{
		int x;
		scanf("%d", &x);
		a[x] = 1;
	}
	int cnt = 0;
	for (int i = 1; i <= 1000; i++)
	{
		if (a[i])
		{
			cnt++;
			i += l-1;
		}
	}
	printf("%d", cnt);
}

다른 분의 코드이다.

시간 복잡도도 O(N)이며 공간 복잡도도 int형 배열이 아닌 bool형 배열을 사용하여 반으로 낮췄다.

위치를 int배열로 저장하는게 아닌 bool형 배열에 있다 없다로 저장하여 sort연산을 생략하였다!

bool형 배열을 하나의 파이프로 본것이다! 약간 지렸다...

그리고 다음 반복문에서 구멍을 찾는다면 카운팅 후 탐색 인덱스를 테이프 길이만큼 추가해

그 후에 나오는 구멍을 찾게하여 많은 불필요한 연산을 생략했다!

굉장히 배울게 많은 코드였다.