chaetudy

(6/23 - 세모)

https://programmers.co.kr/learn/courses/30/lessons/42578

처음에 set과 재귀를 이용해서 순서가 없는 조합을 구하며 풀었는데, 계속 시간 초과가 떴다. 모든 경우의 수를 재귀로 다 따지고 들어가서 구하니까 시간 초과가 떠 버리지.. 알고 보니 해법이 엄청 간단했다.

구현

안경인 안A, 안B가 있고, 모자 모A, 모B, 모C가 있다고 치자. 이때 나올 수 있는 경우의 수는 3 * 4이다.

아무것도 안 입은 경우, 안A, 안A모A, 안A모B, 안A모C, 안B, 안B모A, 안B모B, 안B모C, 모A, 모B, 모C. 이렇게. 쉽게 말하면 해당 종류의 옷을 안 입는 경우도 같이 세어 주면 된다. 문제 조건 중에 아무것도 안 입는 경우는 없다고 했으니 -1 해 주면 된다.

해싱이 가능한 map을 이용해서 m[안경]=안A, 이런 식으로 저장한다.

코드

// 프로그래머스 고득점 Kit - 위장
#include <string>
#include <vector>
#include <map>
using namespace std;

map<string, string> m;
map<string, int> cnt;
int solution(vector<vector<string>> clothes) {
    int answer = 1;

    // 0:name 1:type
    for (auto& i : clothes) {
        m.insert({ i[0], i[1] });
        cnt.insert({ i[1], 1 });
    }

    for (auto& i : m) {
        cnt[i.second]++;
    }


    for (auto& i : cnt) {
        answer *= i.second;
    }

    answer--;
    return answer;
}

int main() {
    vector<vector<string>> c(3);
    //c[0].push_back("yellowhat");
    //c[0].push_back("headgear");
    //c[1].push_back("bluesunglasses");
    //c[1].push_back("eyewear");
    //c[2].push_back("green_turban");
    //c[2].push_back("headgear");

    c[0].push_back("aa");
    c[0].push_back("A");
    c[1].push_back("bb");
    c[1].push_back("B");
    c[2].push_back("cc");
    c[2].push_back("C");

    //c[0].push_back("yellowhat");
    //c[0].push_back("headgear");
    //c[1].push_back("bluehat");
    //c[1].push_back("headgear");
    //c[2].push_back("green_turban");
    //c[2].push_back("headgear");

    solution(c);
}

(6/21 - O)

첫 번째 시도에는 string을 써서 priority+location 이런 식으로 priority_queue에 담아서 compare 함수도 직접 쓰고.. 별 짓을 다 해서 어찌저찌 제출은 가능하게 했는데, 결국 나머지 테스트 케이스들에서 시간 초과였다. 썼던 코드들을 초기화하고 새로운 마음으로 다시 풀어 봤더니 두 번째 시도에 해결할 수 있었다.

https://programmers.co.kr/learn/courses/30/lessons/42587

구현

priority를 가진 문서들을 첫 번째부터 차례대로 인쇄를 시도한다. front에 있는 문서의 priority가 뒤의 문서들의 priority보다 낮다면, 이 문서는 뒤로 push된다. 이때 내가 지정한 location에 있는 문서가 몇 번째로 인쇄되는지 구한다.

1. 기본적으로 FIFO 형태이므로 queue를 선택한다.

2. queue<pair<int, int>>에 first:priority, second:location 형태로 원소를 차례대로 넣는다. (이하 q)

3. priority_queue<int>에 priority들을 모두 넣는다. (이하 pq)

4. q를 순회하면서, q.front().first가 pq.top()과 같은지 검사한다. 같다면 문서를 출력하는 것이므로 cnt를 증가시키고, p를 pop, pq도 한 번 pop 한다. 다르다면 q.front()를 다시 push 하고 q를 pop 한다.

코드

// 프로그래머스 고득점 Kit - 프린터

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    // vector[location] = priority
    // pq에 우선순위들을 쭉 넣는다.
    int size = priorities.size();
    queue<pair<int, int>> q;
    priority_queue<int> pq;
    int loc = 0;
    for (const int& i : priorities) {
        q.push({ i, loc++ });
        pq.push(i);
    }

    int cnt = 0;
    while (true) {
        int max = pq.top();

        pair<int,int> pi = q.front();
        if (pi.first == max) {
            cnt++;
            pq.pop();
            if (pi.second == location) {
                answer = cnt;
                break;
            }
        }
        else {
            q.push(pi);
        }
        q.pop();
    }

    return answer;
}

int main()
{
    vector<int> v{ 2,1,3,2 };
    solution(v, 2);
}

(6/21 - X, 풀이 방법 자체를 못 떠올림)

https://programmers.co.kr/learn/courses/30/lessons/43238

구현

각자 심사 시간이 다른 심사관들이 있을 때, n명을 검사하는 데 걸리는 최소 시간을 구해야 한다.

1. 임의의 시간(mid) 동안 최대 몇 명이 입국 심사를 받을 수 있는지(imm_sum) 구하고, 이 시간의 최솟값을 찾는다.

2. 탐색하는 범위가 1,000,000,000이므로 이분 탐색을 선택한다.

3. 최솟값(mid)을 찾기 위해 최소(start), 최대(end) 범위를 구해 가면서 n명을 검사할 수 있는 시간 값을 찾는다.

3.1 start는 times[0], end는 times[times.size() - 1] * n이다.

실수

케이스 테스트 6,9에서 막혔었다.

n과 imm_sum 값이 꼭 맞아떨어지지 않는 경우에 대해 처리를 해 주지 않았었다.

예를 들어, {6, 8, 10}이고 n=10일 때를 생각해 보면, mid 값이 30일 때 n이 10이고 imm_sum은 11이 나온다. 만약 탐색을 더 해서 mid 값을 29로 줄인다면 n은 10인데 imm_sum이 9가 되어 조건 자체를 만족하지 못 하는 상황이 될 것이다. mid 값이 30일 때가 가장 최적의 경우이다.

따라서, n <= imm_sum일 경우에 answer에 값을 저장하고 범위를 줄여서 다음 탐색을 하면 된다.

구현 과정: {6, 8, 10} n=10

코드

// 프로그래머스 고득점 kit - 입국 심사
#include <string>
#include <vector>

using namespace std;

long long binary_search(vector<int>& times, int n, long long start, long long end) {
    long long answer = 0;
    long long mid = -1;
    while (start != end -1) {
        mid = (end + start)/2;
        long long imm_sum = 0; // mid 시간 동안 times의 심사원들이 각각 몇 명이나 검사할 수 있는지
        for (auto& i : times) {
            imm_sum += (mid / i);
        }
        if (imm_sum >= n) {
            end = mid;
            answer = mid;
        }
        else {
            start = mid;
        }
    }
    return answer;
}

long long solution(int n, vector<int> times) {
    long long answer = 0;

    answer = binary_search(times, n, times[0], times[times.size() - 1] * n);

    return answer;
}

int main() {
    vector<int> v{ 6, 8, 10 };
    solution(10, v);
}

도움 된 글

https://born2bedeveloper.tistory.com/40

https://happy-obok.tistory.com/10

(6/20 - △)

https://programmers.co.kr/learn/courses/30/lessons/42839

구현

두 가지를 고민해야 한다.

1. 숫자들의 조합을 빠짐없이 구해서 저장하기.

 - 예를 들어 "013"일 경우, next_permutation으로 조합을 만들면 {013}, {031}, {310}, {301}만 구할 수 있고 {0}, {1}, {3}, {01} 등의 경우가 누락된다. -> 재귀를 이용한 next_permutation. 아래 코드 참고!

 - 중복되지 않게 담으려면 어디에 담을 것인가 -> set

2. 소수인지 판별하기.

 - n이 소수인지 판별한다면, n에다 2부터 n까지의 수를 나누어서 나머지가 0이 나온 경우가 있다면 소수가 아님으로 판정.

실수한 부분

next_permutation으로 조합을 구할 때 오름차순으로 정렬한 후 해야 한다. 이거 때문에 세모 표시 했다.

코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>


using namespace std;

set<int> s;

bool isPrime(int num) {
    int cnt = 0;
    for (int i = 1; i < num; i++) {
        if (num % i == 0) {
            cnt++;
        }
    }
    if (cnt == 1)
        return true;
    else
        return false;
}

void recurs(vector<int>& v, int size, int cnt, string& st) {
    if (cnt >= size) return;
    st.push_back(v[cnt++]);
    s.insert(stoi(st));
    recurs(v, size, cnt, st);
}

int solution(string numbers) {
    int answer = 0;
    int len = numbers.length();
    vector<int> v(len);
    for (int i = 0; i < len; i++) {
        v[i] = numbers[i];
    }

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

    do {
        string st = "";
        recurs(v, len, 0, st); // 0
    } while (next_permutation(v.begin(), v.end()));
    
    set<int>::iterator i_b = s.begin();
    set<int>::iterator i_e = s.end();

    for (; i_b != i_e; i_b++) {
        if (isPrime((*i_b))) answer++;
    }

    return answer;
}

(6/20 - X)

https://programmers.co.kr/learn/courses/30/lessons/42895

구현

1. N을 1개 사용하여 만든 집합을 N1, N을 2개 사용하여 만든 집합을 N2, N을 3개.. 박스에 넣는다고 생각하자. (중복되지 않는 원소를 갖는 unordered_set을 사용)

2. N1을 만들면서 컨테이너에 number와 값이 같은 수가 있는지 확인한다. 있으면 1을 return하는 식. 없다면 N2를 만들고, 또 없다면 N3을 만들고.. N7까지 만들어도 없다면 -1을 return한다.

1번을 구현하는 게 어렵다. 수 조합을 어떻게 만드냐 싶은데, 아래와 같이 그림을 그리면서 보면 패턴이 나온다.

코드

// [프로그래머스 코테 고득점 Kit] dynamic programming - n으로 표현
#include <string>
#include <vector>
#include <unordered_set>
#include <cmath>

using namespace std;

int make(int N, int p){//i=2일때 NN = N * 10 + N, i=3일때 NNN = N * 100 + N * 10 + N, i=4일때 NNNN..
    int value = 0;
    for (int i = 1; i <= p; i++) {
        value += N * pow(10, i - 1);
    }
    return value;
}

int solution(int N, int number) {
    int answer = 0;

    if (N == number) return 1;

    vector<unordered_set<int>> box(9);
    
    box[1].insert(N); // N1에는 N 하나만
    for (int i = 2; i < 9; i++) { //i3
        box[i].insert(make(N, i)); 
        for (int j = 1; j < i; j++) { //j=1,1<3,i-j==2 // j=2,2<3,i-j==1 //
            for (auto& num_first : box[j]) {
                for (auto& num_second : box[i - j]) {
                    box[i].insert(num_first + num_second);
                    box[i].insert(num_first - num_second);
                    box[i].insert(num_first * num_second);
                    if(num_second != 0)
                        box[i].insert(num_first / num_second);
                    box[i].insert(num_second + num_first);
                    box[i].insert(num_second - num_first);
                    box[i].insert(num_second * num_first);
                    if (num_first != 0)
                        box[i].insert(num_first / num_first);
                }
            }
        }
        if (box[i].end() != box[i].find(number)) {
            answer = i;
            return answer;
        }
    }

    return -1;
}

int main() {
    solution(5, 12);
}

(6/17 - X)

https://programmers.co.kr/learn/courses/30/lessons/42860

#include <string>
#include <vector>

using namespace std;

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

    int size = name.size();
    int updown = 0, leftright = size - 1;

    vector<char> v(size);
    int i = 0;
    for (auto& s : name) {
        v[i++] = s;
    }

    // left-right
    for (int start_idx = 0; start_idx < size; start_idx++) {
        updown += min(abs('A' - v[start_idx]), abs('Z' - v[start_idx]) + 1);

		int end_idx = start_idx + 1;
		while (end_idx < size && v[end_idx] == 'A') {
			end_idx++;
		}
		leftright = min(leftright, 2 * start_idx + (size - end_idx));
		leftright = min(leftright, 2 * (size - end_idx) + start_idx);
	}

    answer = leftright + updown;
    return answer;
}

1. updown

조이스틱 상하(A-Z)로 이동하는 횟수. 아스키코드를 이용하여 'A'와 문자, 'Z'와 문자의 차이 값을 구하고, 그 중 가장 적게 움직일 수 있는 횟수를 선택한다.

2. leftright

조이스틱을 좌우로 움직이는 횟수. (여기에서 많이 애먹었다)

비교할 경우는

• 순방향으로 이동 시 : name.length() - 1
• > 방향으로 먼저 이동 후 A를 만났을 때 <로 방향 전환 : 2 * start_idx + (size - end_idx)
• < 방향으로 먼저 이동 후 A를 만났을 때 >로 방향 전환 : 2 * (size - end_idx) + start_idx

문자열 중간에 많은 수의 A가 있다면 >로 가다가 다시 유턴해서 <로 가는 방법이 더 이동 횟수가 적다. 그 반례로 'ABABAAAAAAABA'가 있다. 따라서 경우가 위처럼 세 가지.

3. answer

updown, leftright를 더해 주면 된다.

효율성

아주 미세한 차이지만, string에 직접 접근하는 방식보다 vector<char>에 name의 원소를 하나하나 넣어서 그 벡터에 접근하는 방식이 조금 더 메모리를 덜 잡아 먹는다. (테케5나 테케25에서 특히)

출처

https://inuplace.tistory.com/1091

이 분의 글을 보고 많은 도움을 얻었다.

https://programmers.co.kr/learn/courses/30/lessons/43165

구현

재귀 DFS를 이용해서 쉽게 풀 수 있다.

{1, 1, 1, 1, 1}이라면 [0]을 +로 하는 가지, -로 하는 가지로 나누어서 그 안에서 또 +[1]로 하는 가지와 -[1]로 하는 가지로 나누어서 벡터를 끝까지 순회하면 된다. 끝까지 순회하면 더한 값과 target을 비교하여 판단하면 된다.

// [프로그래머스 코테 고득점 Kit] BFS/DFS - 타겟 넘버
#include <string>
#include <vector>

using namespace std;
int result = 0;
void dfs(vector<int>& v, int sum, int target, int cnt) {
    if (cnt == v.size()) {
        if (sum == target) {
            result++;
        }
        return;
    }
    dfs(v, sum - v[cnt], target, cnt + 1);
    dfs(v, sum + v[cnt], target, cnt + 1);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int cnt = 0;
        // 매개 변수로 들어가는 cnt를 cnt++로 넣어 줬는데, 이렇게 하면 안 된다.
		// 이 줄에서의 cnt는 solution 지역에서의 cnt이기 때문에, 
		// cnt++는 solution 지역에서의 cnt가 증가될 뿐, 매개변수로 들어가는 cnt에는 아무런 영향을 주지 않는다. 
	dfs(numbers, -numbers[0], target, cnt + 1);
	dfs(numbers, +numbers[0], target, cnt + 1);
	answer = result;
    return answer;
}

int main() {
    vector<int> v = { 1,1,1,1,1 };
    solution(v, 3);
}

문제 5-10. 음료수 얼려 먹기

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
예시) 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.

입력 조건
첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.
(1 <= N, M <= 1,000)
두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력 조건
한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

아이디어

얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 한다. DFS를 이용하면 간단히 해결 가능하다.

물을 흘려 보낸다는 느낌으로 bool형 배열인 visited를 선언하여 방문 처리를 하고, 한 번 방문했으면 카운팅을 하지 않는 식으로 푼다.

#include <iostream>
#include <string>
using namespace std;

int arr[1001][1001];
bool visited[1001][1001];
int n, m;

bool dfs(int row, int col){
	if (row < 0 || row >= n || col < 0 || col >= m) return false;
	if (arr[row][col] == 1) return false;
	if (visited[row][col] == true) return false;
	visited[row][col] = true;

	dfs(row - 1, col);
	dfs(row + 1, col);
	dfs(row, col - 1);
	dfs(row, col + 1);

	return true;
}

int main() {
	cin >> n >> m;

	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		int size = s.size();
		for (int j = 0; j < size; j++) {
			arr[i][j] = (s[j] - '0');
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (true == dfs(i, j)) {
				cnt++;
			}
		}
	}

	cout << cnt << "\n";
}