뚝딱뚝딱

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(인덱스, 문자개수, "대체 문자")의 인자를 갖는다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42862

💡 체육복

• 단순 구현 문제
• lost_num이라는 int형 변수에 lost배열의 크기를 저장해두고, 최대로 빌려준 후 남은 학생 수를 저장하도록 하여, n에서 lost_num을 빼 답을 구할 것이다.
• n+1 크기의 배열 arr을 생성해서, reserve를 참고해 여벌을 가진 번호에 1을, 아니면 0으로 초기화한다.
• 근데, 여벌을 가져온 학생 중 도난을 당할 경우 자신의 옷을 입어야 한다. 따라서 lost배열과 arr배열을 비교해서, lost에 있는 번호가 arr배열에서 값이 1이면 0으로 만들고, lost_num을 1 빼준다.
  만약 해당하지 않으면 stack에 lost값을 넣는다.
• stack이 비워질 때까지, 하나씩 빼가면서 arr배열에서, 현재 peek값+1 또는 peek값-1 번호가 1의 값을 가질 때 둘 중 하나 먼저 해당되는 것을 빌리도록 하고, 그 arr값을 0으로, lost_num을 1 빼준다. 그리고 pop한다.
• 최종 answer는 n에서 lost_num을 뺀 값이다.
• 여기서 주의할 점은, lost 배열을 사용하기 전에, 오름차순 정렬해야 한다는 점이다.
  로직은 동일했는데, 두 테케에서 자꾸 실패가 떠서 왜 그런가 하고, 정렬을 해봤더니 해결됐다.
  항상 입력 배열이 정렬되어 주어질 것이라 장담하지 말고, 정렬하고 시작하는 습관을 기르자.
• 그리고 나의 풀이 방식의 경우, lost를 오름차순 정렬한 후에, lost 크기만큼 순회하면서 stack에 넣었다.
  stack에 넣으면 작은 값부터 들어가고, 나올때는 큰 값부터 나오기 때문에, lost+1번호가 여벌이 있는지를 먼저 확인하도록 하였다.
  만약 작은 값부터 나오게 짰다면, lost-1번호가 여벌이 있는지를 먼저 확인하도록 해야, 최대의 값을 가질 수 있을 것이다.
• 전체 코드는 아래와 같다.
  
  

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        int[] arr = new int[n+1];
    
        Arrays.fill(arr,0);
        
        for(int i=0; i<reserve.length; i++){
            arr[reserve[i]]++;
        }
        
        int lost_num=lost.length;
        
        Stack<Integer> st = new Stack<>();
        
        Arrays.sort(lost);
        
        for(int i=0; i<lost.length; i++){
            if(arr[lost[i]]==1){
                arr[lost[i]]--;
                lost_num--;
            }else{
                st.push(lost[i]);
            }
        }
        
        while(!st.isEmpty()){
            if(st.peek()<n&&arr[st.peek()+1]==1){
                arr[st.peek()+1]--;
                lost_num--;
            }
            else if(st.peek()>1&&arr[st.peek()-1]==1){
                arr[st.peek()-1]--;
                lost_num--;
            }
            st.pop();
        }
        
        answer=n-lost_num;
        return answer;
    }
}