뚝딱뚝딱

https://www.acmicpc.net/problem/1032

💡 명령 프롬프트

시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.
dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.
이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 "." 그리고 "?"만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

=> 주어지는 파일들을 한번의 패턴 명령으로 모두 조회할 수 있도록 만드는 것이다.

✅ 풀이 방법

• 이 문제를 풀기 위해 "두 가지"를 생각했다.
• 한가지는 , 첫 번째로 받는 문자열을 "기준"으로 잡아야 겠다는 것
• 또 다른 한가지는, 인덱스 정보를 저장할 자료 구조로 중복을 허용하지 않는 "set"을 이용해야겠다는 것

이 두가지를 유념해 두고 풀이를 보자.

• 첫번 째 문자열을 먼저 받고, 만약 입력 받은 문자열이 하나가 끝이라면, 패턴은 그 문자열 자체가 될 수 있다.
  따라서 그 문자열 자체를 출력하고 return 0을 통해 프로그램을 종료한다.
• 문자열의 길이와, 인덱스를 저장할 set 자료구조를 생성해 놓는다.
• 만약 입력 받는 문자열이 하나가 아니라면, T-1번 문자열을 받는다.
• 문자열을 받을 때마다, 받고 난 뒤, 기준 문자열인 첫번째 문자열과 한 글자씩 비교한다.
• 문자가 다르면, 해당 문자 위치인 인덱스를 set에 넣는다.
• 문자열을 모두 받고 나면, set에는 패턴에서 ?가 되어야 할 인덱스들이 들어 있는 것과 같다.
• set을 순회하면서, 첫번 째 문자열에 replace함수를 사용하여, set에 있는 인덱스의 문자는 모두 ?로 대체해준다.
• 최종 패턴 문자열이 된 첫번 째 문자열을 출력해준다.

전체 코드는 아래와 같다.

#include<iostream>
#include<string>
#include<set>

using namespace std;

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

	int T;
	cin >> T;

	string str;//기준이 되는 str
	cin >> str;

	if (T == 1) {
		cout << str;
		return 0;
	}

	int len = str.length();

	//중복값을 넣지 않는 set을 선언해서, 값이 다른 인덱스를 넣는다
	set<int> index;

	for (int i = 1; i < T; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < len; j++) {
			if (str[j] != s[j]) {
				index.insert(j);
			}
		}
	}

	for (auto it = index.begin(); it != index.end(); it++) {
		str.replace(*it, 1, "?");
	}
	//replace(인덱스, 몇글자, "대체문자")

	cout << str;

	return 0;
}

✏ c++ 문법 알고 넘어가기

• set : 자료 구조 중 하나로, 중복 값을 허용하지 않는다.
  <set> 헤더에 정의되어 있다.
  insert로 값을 넣는다.
  set에 있는 값을 가져올 때는 iterator를 반환하기 때문에, 앞에 *을 붙혀서 값을 가져온다.
• string.replace() : string의 문자열 대체 함수이다.
  replace(인덱스, 문자개수, "대체 문자")의 인자를 갖는다. 

소프티어 lv2 "금고 털이" 문제 풀이 중 pair vector와 sort사용이 익숙치 않아 정리하는 글이다.

pair vector

vector<pair<int, int>> v;

vector에서는 한 요소에 두가지 값을 함께 넣으려면, 위와 같이 pair로 묶어서 정의해 주어야 한다.

"금고 털이" 문제에서 첫번째 int 요소에는 금속의 무게를 , 두번째 int 요소에는 금속의 가치를 저장해주었다.

각각의 값에 접근하려면, v.first, v.second로 접근할 수 있다.

sort

algorithm에서 정의한 정렬 함수 sort이다.

기본적으로 오름차순 정렬이고, pair vector의 경우 첫번째 값을 기준으로 오름차순 한다.

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

이렇게 하면 vector v를 첫번째 값인 금속 무게에 대해서 오름차순 정렬해준다.

그런데 나는 금속의 가치인 두번째 값에 대해서 내림차순 정렬하고 싶었다.

그래서 sort함수에, 따로 정의한 비교함수를 인자로 넣어, 이 기준으로 정렬해 주세요~라고 요청했다.

bool compare(const pair<int, int> &a, const pair<int, int> &b){
	return a.second>b.second;
}

 위와 같은 compare 함수를 정의해 주었다.

내가 헷갈렸던 점은, 부등호의 방향이다. 

처음에는 b쪽에 크다고 했는데, 이유는 정렬할 때 뒤에 있던게 컸었다..라고 생각한 것이다. 아무튼 나의 착각이고..

내림차순이 앞이 큰거니까, 먼저 위치한 a가 클 때 true로 정의해 주는 것이다.

반대로 오름차순이면? b쪽으로 부등호가 향해야 할 것이다.

이렇게 해서 기본 of 기본인 pair vector와 sort함수에 대해 정리해보았다.

다음에는 버벅거리지 않고 바로 구현하길~

https://www.acmicpc.net/problem/2559

💡 수열

• 이 문제는 무지성으로 풀이하면 [시간초과]가 당연히 발생하는 문제이다.
• 입력 크기가 최대 10^6이므로 O(n^2)으로 풀 시 시간초과가 발생한다.
• 결론적으로 이 문제는 "누적합"="부분합"을 이용하여 풀이할 수 있다.
• 누적합을 저장할 크기가 N+1인 벡터를 생성하고, 0으로 초기화한다.
• N+1개를 생성한이유는 0번 인덱스를 0으로써 활용하기 위함이다.
• 누적합 배열을 v라고 할 때, 만약 K=2이면 v[2]-v[0]은 두번째 값까지 더한 값에서 0번째 값까지 더한 값을 빼준 것이고, 이 값은 첫번째값과 두번째값을 더한 것이므로, 단순히 빼기를 통해 구간의 합을 구할 수 있고, 이로써 중복적인 더하기 연산을 피할 수 있으므로 시간을 단축할 수 있다.
• 예시
  
  

• 주어진 예시에서 5개만을 가져와 보았다.
• 주어진 5개의 숫자값들이 위의 배열과 같을 때, 아래 v배열은 각 값들의 누적합을 차례로 1번 인덱스부터 채워넣는다.
• 하나씩 살펴보면, v[1]에는 첫번째 값인 3을, v[2]에는 두번째값까지 더한 값(3+(-2))인 1을, v[3]에는 세번째값까지 더한...
• 이제 K가 2이므로, 연속한 두 값씩 더한 값을 구해보자. 이는 이미 구해둔 v[K]-v[0] 연산만을 통해 구할 수 있다.
• 첫번째 연속합을 max로 지정해주고, for문을 통해 K+1부터 N까지 진행하면 된다.
• 이 방법은, cin으로 숫자값들을 받을 때, 동시에 배열에도 누적합을 더해 놨기 때문에, 이 값을 이용해 차 연산만 해주고, 그 연산 결과가 가장 큰 값을 반환하면 되므로, 시간효율이 아주 좋다! 

• 아래는 전체 코드이다.

#include<iostream>
#include<vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N,K;
    cin>>N>>K;
    
    vector<int> v(N+1,0);
    
    for(int i=1; i<N+1; i++){
        int temp;
        cin>>temp;
        v[i]=v[i-1]+temp;
    }
    
    int max=v[K];
    for(int i=K+1; i<N+1; i++){
        max=(max<v[i]-v[i-K])?v[i]-v[i-K]:max;
    }
    
    cout<<max;
    
    return 0;
}

이전에 유사한 누적합 문제를 풀어봐서 문제를 보자마자 바로 "누적합!!!"하며 풀 수 있었다.

코딩테스트를 준비하면서 여러 문제를 풀다보니, 점점 문제의 유형이 눈에 보이기 시작한 것 같다.

그래도 아직 갈길이 멀다...!!!

https://softeer.ai/practice/6293

💡 징검다리

• 징검다리 문제는 입력이 3*1000까지 이기 때문에 n^2으로 풀이할 수 있다.
• 계수 정렬을 이용하여 풀이한다.
• 각 돌의 계수를 저장하기 위한 크기가 N인 vector를 생성하고, 값을 1로 초기화해준다.
• 1로 초기화 해주는 이유는, 어떠한 돌을 밟더라도 하나의 돌은 밟은 것이므로 1로 시작한다.
• 0번째를 제외하고, 1번째 돌부터 N-1번째 돌까지 순회하면서, 현재 돌이 이전 돌 보다 큰지를 확인한다.
• 0번째 돌부터 현재 돌의 이전 돌까지 중, 현재 돌보다 작은지 확인하고, 작은 돌들 중에서도 가장 큰 계수를 가져오고, 그 값에 1을 더하여 현재 돌의 계수를 설정하는 방식이다.
• 이런식으로 모든 돌의 계수를 설정하고 나서, 가장 큰 계수를 반환하면 그것이 답이 된다.

• 원리
  예시1
  
  

• n=5일때 위와 같이 돌의 높이가 주어졌다고 하자.
• 3은 시작이고, 이전 돌이 없으며 첫 돌이므로 본인을 포함한 1의 값을 갖는다.
• 2를 보면, 앞의 돌인 3보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 1역시, 앞의 돌인 3,2보다 작기 때문에, 본인을 포함한 1의 값을 갖는다.
• 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
• 5는 앞의 돌인 3,2,1,4보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
• 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

• 예시2
  
  

• • n=7일때 위와 같이 돌의 높이가 주어졌다고 하자.
  • 1까지 앞의 내용과 같다.
  • 6는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 7은 앞의 돌인 3,2,1,6보다 크고, 이 중 가장 큰 계수 값이 2이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 4는 앞의 돌인 3,2,1보다 크고, 이 중 가장 큰 계수 값이 1이므로, 1에 본인을 포함한 1을 더해 2의 값을 갖는다.
  • 5는 앞의 돌인 3,2,1,4 보다 크고, 이 중 가장 큰 계수 값이 2 이므로, 2에 본인을 포함한 1을 더해 3의 값을 갖는다.
  • 따라서 최종적으로 가장 큰 계수인 3이 최대로 건널 수 있는 돌의 개수와 같다.

이런식으로 동작하는 것이고, 2줄 for문을 거치기 때문에 n^2의 시간 복잡도가 발생한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int N;
  cin>>N;

  vector<int> h(N);//높이를 담을 벡터
  for(int i=0; i<N; i++){
    cin >> h[i];
  }
  
  vector<int> cnt(N,1);//계수를 담을 벡터
  for(int i=1; i<N; i++){
    int cnt_max=0;//이전 계수 중, 돌의 높이가 현재 돌보다 작으면서, 계수가 가장 큰 것을 저장하기 위함
    
    for(int j=0; j<i; j++){
      if(h[i]>h[j]){//이전 돌이 현재 돌보다 작으면
        cnt_max = max(cnt_max, cnt[j]);
      }
    }

    cnt[i]=cnt_max+1;//이전 계수에 현재 돌까지 합쳐서 계수 설정
  }

  cout<<*max_element(cnt.begin(), cnt.end());

   return 0;
}

***참고로 vector의 max값을 반환하기 위해 vector에서 제공하는 max_element() 메서드를 사용했는데, 이 함수는 iterator 즉, 벡터의 요소를 가리키기 때문에, 그 값을 가져오려면 앞에 *를 붙여야 한다. 

소프티어에 있는 lv3 연습 문제 "성적 평균"에 대한 풀이 방법이다.

풀이 날짜는 2023.11.01로, 최근에 소프티어 페이지가 리뉴얼 되었다.

그런데 리뉴얼 후 문제인지, 아니면 이렇게 업데이트 된 것인지 모르겠는데..

어제 다른 문제를 풀 때, 답이 틀리면, 제출 이력에 틀린 답도 뜨고, 왜 틀렸는지(그 문제의 경우 시간초과였음) 표시도 되어있었다.

그런데 오늘 아침부터 풀고 있던 이문제.. 문제 자체에만 틀렸다고 표시되어 있고, 내가 제출한 이력은 전혀 보이지 않는다.

분명 예시 테케도 맞았고, 혹시나 하여 다른 사람들의 풀이랑 내 풀이도 비교해보았는데, 접근 방식이 동일하다.

그런데, 제출만하여 계속 틀렸다고만 뜨고, 제출 이력에는 표시조차 되어 있지 않다. 왜 틀렸는지는 알려줘야지....

거의 20번은 넘게 제출을 한 것 같은데.. 그래서 일단 개발자 톡에 문의를 넣어놓았고, 내 풀이상의 문제일 수 도 있을것 같아 코드도 함께 게시해 놓았다.

부분합 사용

이 문제는 부분합을 사용하면 아주 쉽고 간단하게 풀이할 수 있다.

부분합??

예를 들어서 5명의 학생이 있고, 각각의 점수는 20, 40, 10, 80, 30 이라고 하자.

그러면 크기가 5인 배열에 1명까지 더한 값, 2명까지 더한 값...이렇게 저장하는 것이다.

즉 arr이라는 크기가 5인 배열이 있으면

arr[0] =20

arr[1] = 20+40 = arr[0]+40

arr[2] = 20+40+10 = arr[1]+10

...

이렇게 이전에 저장해둔 값에 새로운 값을 추가로 저장해 총합을 구해 가는 것이다.

배열의 인덱스는 학번과도 같고(문제에서는 1부터 시작하지만, 예시로는 0부터 해도 무방), 만약 1번 학생부터 3번 학생까지의 점수 평균을 구한다면..

3번학생까지의 부분합-0번학생까지의 부분합 = 1번 학생부터 3번학생까지의 점수 합

이기 때문에, 구간이 주어지면 이미 구해진 합을 이용해 구간 합을 쉽게 구할 수 있다.

그리고 1번 학생부터 3번 학생까지 니까 (3-1+1)로 나누어 주면 평균은 바로 구할 수 있다.

따라서 아래와 같은 순서로 진행한다.

1. 학생 수인 N과 구간 수인 K를 먼저 받아서 저장한다.

2. 1부터 i번(1<=i<=N)까지의 학번을 갖는 학생 들의 점수 합을 저장하는 크기가 N+1인 벡터(또는 배열)를 생성한다 => 0번은 0으로 초기화 할 것이다.

3. 입력으로 학생들의 점수를 받을 때, 벡터에 합을 저장해준다.

4. 입력으로 K개의 구간 정보를 입력 받을 때, 앞에서 구한 부분합을 이용해서 평균을 바로 출력한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
  int N,K;
  
  cin>>N>>K;

  vector<double> prefixSum(N+1);

  prefixSum[0]=0;
  
  for(int i=1; i<N+1; i++){
    int S;
    cin>>S;
    prefixSum[i] = prefixSum[i-1]+(double)S;
  }

  int A,B;
  for(int i=1; i<K+1; i++){
    cin>>A>>B;
    printf("%.2f\n", (double)(prefixSum[B]-prefixSum[A-1])/(double)(B-A+1));
  }

  return 0;
}

다른 사람들의 코드랑 비교해보아도, 이상이 없, 예제도 통과하는데, 틀린 이유를 모르겠으나.. 일단은 올려둔다.

예외를 발견한다면 알려주세요!!!