✅ 한 것들

---

• 프로그래머스
• 백준

⚔️ 프로그래머스

---

기능개발

// 100 - progresses에 speeds를 나누고 딱 떨어지면 몫, 안 떨어지면 몫+1이 남은 날
// 앞에 있는 모든 기능이 완성돼야 뒤에 있는 기능들이 배포 가능하므로,
// 앞쪽부터 지난 날짜를 기록하면서 이미 지났다면 바로 통과, 아니라면 해당 날짜까지 기다리기
// 날짜가 아니라 각 배포마다이므로, vector에 바로바로 더해주면 됨
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    for (int i = 0; i < progresses.size(); i++)
    {
        int pp = progresses[i];
        if ((100 - pp) % speeds[i] == 0) progresses[i] = (100 - pp) / speeds[i];
        else progresses[i] = (100 - pp) / speeds[i] + 1;
    }
    int day = 0;
    for(int i=0; i<progresses.size(); i++)
    {
        int d = (100 - progresses[i]) / speeds[i];
        if (d > day) {
            day = d;
            answer.push_back(1);
        }
        else {
            answer.back()++;
        }
    }
    
    return answer;
}

내 풀이

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int day = 0;
    for(int i=0; i<progresses.size(); i++)
    {
        int d = (99 - progresses[i]) / speeds[i] +1;
        if (d > day) {
            day = d;
            answer.push_back(1);
        }
        else {
            answer.back()++;
        }
    }
    
    return answer;
}

다른 풀이 참고

• 1 빼두고 +1 하면 몫을 올림한 것과 같은 결과

Monito 사전 테스트 문제

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<vector<int>> v) {
    vector<int> ans;
    // 첫 점과 같게 초기화
    int xmin = v[0][0], xmax = v[0][0], ymin = v[0][1], ymax = v[0][1];
    for (vector<int> vi : v) {
        xmin = min(xmin, vi[0]);
        xmax = max(xmax, vi[0]);
        ymin = min(ymin, vi[1]);
        ymax = max(ymax, vi[1]);
    }

    int xminC = 0, xmaxC = 0, yminC = 0, ymaxC = 0;
    for (vector<int> vi : v) {
        if (vi[0] == xmin) xminC++;
        else xmaxC++;
        if (vi[1] == ymin) yminC++;
        else ymaxC++;
    }

    if (xminC < xmaxC) ans.push_back(xmin);
    else ans.push_back(xmax);

    if (yminC < ymaxC) ans.push_back(ymin);
    else ans.push_back(ymax);

    return ans;
}

내 풀이

#include <vector>
using namespace std;

vector<int> solution(const vector<vector<int>>& v) {
    int x = 0, y = 0;
    for (const auto& p : v) {
        x ^= p[0];
        y ^= p[1];
    }
    return {x, y};
}

gpt가 다듬어준 풀이

• xor은 배타적 논리합. 둘이 다르면 1, 같으면 0인 연산.
• a ^ a = 0, a ^ 0 = a, a ^ b ^ a = a ^ a ^ b
• 짝수 번 나온 값은 날아가고, 홀수 번 나온 값만 남는다

⚔️ 백준

---

N과 M (1)

#include <vector>
#include <iostream>

using namespace std;

int N, M;
vector<bool> visited;

void NnM(vector<int> &res)
{
	if (res.size() == M) {
		for (int r : res) cout << r << ' ';
		cout << endl;
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		res.push_back(i);
		visited[i] = true;
		NnM(res);
		visited[i] = false;
		res.pop_back();
	}
}

int main()
{
	cin >> N >> M;
	visited = vector<bool>(N + 1, false);
	vector<int> res;
	NnM(res);
}

시간 초과 풀이

#include <vector>
#include <iostream>

using namespace std;

int N, M;
bool visited[9];
int res[9];

void NnM(int idx)
{
	if (idx == M) {
		for (int i = 0; i < M; i++) cout << res[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		res[idx] = i;
		visited[i] = true;
		NnM(idx+1);
		visited[i] = false;
	}
}

int main()
{
	cin >> N >> M;
	NnM(0);
}

개선 + 맞은 풀이

• 배열 쓰는게 코테에 한해서는 훨씬 풀이 짧아지긴 한다.
• endl이 아니라 '\n' 써야 했음. 시간 초과의 원인이 이거 하나였음.

2304 창고 다각형

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;

int N;
int res = 0;
int maxPIdx = 0;
vector<pii> pillar;

// 실수 1 : pillar들이 정렬돼있지 않다는 걸 놓침
// 실수 2 : 왼쪽에서 오른쪽으로 빔 쏠땐 x가 더 작다는 걸 놓침

void Beam()
{
	// 왼쪽에서 최고기둥까지 빔 쏘면서 넓이 재기
	int prei = 0;
	int preh = pillar[0].second;
	for (int i = 1; i <= maxPIdx; i++)
	{
		// p[i]보다 작으면 무시, 크거나 같으면 합산하고 갱신
		if (pillar[i].second >= preh) {
			res += (pillar[i].first - pillar[prei].first) * preh;
			prei = i, preh = pillar[i].second;
		}
	}
	
	// 최고 기둥 추가
	res += pillar[maxPIdx].second;

	// 오른쪽에서 최고기둥까지
	prei = pillar.size() - 1;
	preh = pillar[prei].second;
	for (int i = pillar.size() - 1; maxPIdx <= i; i--)
	{
		if (pillar[i].second >= preh) {
			res += (pillar[prei].first - pillar[i].first) * preh;
			prei = i, preh = pillar[i].second;
		}
	}
}

void FindMaxValIdx()
{
	for (int i = 0; i < pillar.size(); i++) {
		if (pillar[maxPIdx].second < pillar[i].second) {
			maxPIdx = i;
		}
	}
}

void Input()
{
	cin >> N;

	while (N--)
	{
		int x, h;
		cin >> x >> h;
		pillar.push_back({x,h});
	}
	sort(pillar.begin(), pillar.end());
}

int main()
{
	// 처음엔 맨 왼쪽 기둥부터 왼->오 빔 쏴서 기둥 맞으면 면적을 곱해
	// 빔이 안 맞았으면 높이만큼 더한 다음 빔 방향 바꿔
	// 맨 오른쪽 기둥부터 오->왼 빔 쏴서 기둥 맞으면 면적을 곱해
	// 이걸 최고 기둥 (빔 안 맞은 놈) 전까지 계속해
	Input();
	FindMaxValIdx();
	Beam();
	cout << res;
}

• 좀 더 변수명들을 간단하게도 적어보기. 의미 전달 하는 거 좋은데, 시간이 너무 많이 소요되는 것 같기도. 코테식 사고방식을 조금은 받아들여야 할 거 같다.
• 해당 문제에 한정된 풀이로는 위치 별로 띄엄띄엄 보는게 아니라 모든 가로 칸을 전부 체크할 수도 있긴 했다. 그럼 코드 좀 더 간단해짐.

14719 빗물

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

int H, W;
bool B[501][501];
int res = 0;

void SumRain()
{
	// 0부터 500까지 해당 높이에 있는 칸들을 전부 점검
	// 블럭 만날때마다 res에 rain_temp 더하기
	for (int j = 0; j < H; j++) {
		int rain_temp = 0;
		bool metFB = false;
		for (int i = 0; i < W; i++) {
			if (!metFB) { 
				if(B[i][j])	metFB = true; 
			}
			else if (B[i][j]) { res += rain_temp; rain_temp = 0; }
			else { rain_temp++; }
		}
	}
}

void Input()
{
	cin >> H >> W;
	for (int i = 0; i < W; i++) {
		int h;
		cin >> h;
		for (int j = 0; j < h; j++) {
			B[i][j] = true;
		}
	}
}

int main()
{
	Input();
	SumRain();
	cout << res;
}

• 세로로 접근하는 것도 가능하긴 했다. 더 복잡해지지만
• metFB를 이중 if로 안 나누고 &&으로 하니 틀렸습니다 떴었음.