뚝딱뚝딱

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;
    }
}

대충 만든 자판

이제는 익숙해진 문자열과 숫자 한번에 다루기!

문제를 몇번 풀어보니, 이 문제 역시 문자열과 숫자 개념이 더해진 것임을 바로 파악할 수 있었고, map을 사용하여 쉽게 해결할 수 있었다.

자판의 등장하는 문자를 char형태의 index로 보고, 어떤 위치의 버튼이든 최소한으로 눌렀을 때를 그 알파벳의 버튼 횟수로 저장하도록 하였다.

그러니까 keymap을 순회하면서, 등장하는 문자를 map의 인덱스로 넣고, 해당 위치를 저장하였다.

그리고 같은 문자가 또 한번 등장할 때마다 기존에 저장해 두었던 위치와 비교해보아서 더 작은 위치로 갱신되도록 하였다.

이렇게 하여 문자당 최소 터치 수를 map에 저장해 두면 80 프로는 다 한 것이다!!

이제 targets을 순회하면서 해당 문자의 최소 터치 수가 저장된 map에서 값을 가져와 count시키고, 

만약 해당 문자가 map에 존재하지 않는다면, 작성할 수 없는 문자열이므로, 문제에서 요구한 것처럼 count를 -1로 하고, 해당 문자열은 넘어가도록 코드를 구현했다.

그리고 한 문자열씩 돌때마다 answer벡터에 count값을 push해주면 끝!

코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    map<char, int> m1;

	for (int i = 0; i < keymap.size(); i++) {
		for (int j = 0; j < keymap[i].size(); j++) {
			if (m1.find(keymap[i][j]) == m1.end()) {//map에 존재하지 않은 문자면 입력
				m1.insert(pair<char, int>(keymap[i][j], j+1));
			}
			else {
				if (m1[keymap[i][j]] > j + 1) {
					m1[keymap[i][j]] = j + 1;//더작은 값으로 바꾼다
				}
			}
		}
	}

	int cnt;

	for (int i = 0; i < targets.size(); i++) {
		cnt = 0;
		for (int j = 0; j < targets[i].size(); j++) {
			if (m1.find(targets[i][j]) == m1.end()) {
				cnt = -1;
				break;
			}
			auto temp = targets[i][j];
			cnt += m1[temp];
		}
		answer.push_back(cnt);
	}

    
    return answer;
}

n칸의 벽 중 덧칠해야 할 칸 번호가 적힌 벡터를 참고하여, 한번에 m칸 칠할 수 있는 페인트 롤러를 이용해 최소의 페인트칠 횟수 구하는 문제.

문제의 조건을 보면 section 벡터의 크기가 무조건 1이상이므로, 최소 한번은 칠해야 한다는 점을 기억하자.

section[0]에서 시작해서 한번 칠할 때 section[0]+m-1번 칸 까지는 칠해진다.

그리고 한번 칠했으므로, 칠한 횟수(answer)를 1 증가시켜준다.

temp에 section[0]+m에 대한 값을 저장해두고, for문을 통해 section[1]부터 section의 크기만큼 순회한다.

그래서, 다음 칠해야 할 칸이, 이전에 한번 칠했던 범위에 포함이 되는지를 살펴보고, 포함이 된다면 현재 회차는 넘어가도록 한다.이는 현재 section[i]의 값이 temp보다 작은지를 보면 된다.

만약 현재 section[i]의 값이 temp와 같거나 더 크다면 이전에 칠했을 때, 같이 칠해지지 못한 것이므로, temp를 다시 section[i]+m으로 갱신해주고, 이를 기준으로 한번 더 칠하는 것이므로 answer를 1 증가 시킨다.

위 과정을 모든 section벡터 값에 대해 순회해주면 최소 페인트 칠 횟수를 반환할 수 있다! 

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    
    int temp = section[0] + m;
	answer++;
	
	for (int i = 1; i < section.size(); i++) {
		if (section[i] < temp) {//한번 칠한것에 같이 포함이 되면
			continue;//넘어간다
		}
		else {
			temp = section[i] + m;
			answer++;
		}
	}
    
    return answer;
}