Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 위상정렬
- 동적계획법
- 문자열
- Network
- java
- Kotlin
- 에라토스테네스의 체
- 구현
- swea
- 시뮬레이션
- 스택
- Effective Java
- 완전탐색
- JUnit 5
- 그리디
- 알고리즘
- BFS
- 유니온 파인드
- 플로이드-와샬
- CS
- 투 포인터
- mst
- dfs
- 세그먼트 트리
- 이분탐색
- 수학
- 백트래킹
- 프로그래머스
- 백준
- 후니의 쉽게 쓴 시스코 네트워킹
Archives
반갑습니다!
[프로그래머스] 기둥과 보 설치 본문
풀이
시뮬레이션 문제이다. 구조물을 추가하거나 제거해도 문제에 주어진 규칙을 만족시켜야 한다. 아래의 코드에서는 구조물을 추가하거나 제거할 때마다 모든 구조물들이 규칙을 만족시키는지 확인했다. 그렇게 함으로써 구조물을 추가하거나 제거하는 로직이 간단해진다. 구조물을 추가할 때는 우선 구조물을 추가했을 때 모든 구조물들이 규칙을 만족시키지 못한다면 구조물을 제거하면 되고, 반대로 구조물을 제거할 때는 일단 구조물을 제거하고 모든 구조물이 규칙을 만족하지 못한다면 다시 구조물을 추가하면 된다. 구조물의 설치 여부는 set
을 사용해서 확인했다.
코드
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
set<pair<pair<int, int>, int>> build;
// 해당 위치에 구조물이 설치되어있는지 확인
bool is_builded(int x, int y, int a) {
if (build.find({ {x, y}, a }) != build.end()) return true;
return false;
}
// 첫 번째 규칙
bool rule1(int x, int y) {
if (y == 0 || is_builded(x, y, 1) || is_builded(x - 1, y, 1) || is_builded(x, y - 1, 0)) return true;
return false;
}
// 두 번째 규칙
bool rule2(int x, int y) {
if (is_builded(x, y - 1, 0) || is_builded(x + 1, y - 1, 0) || (is_builded(x - 1, y, 1) && is_builded(x + 1, y, 1))) return true;
return false;
}
// 설치된 모든 구조물이 규칙을 만족시키는지 확인
bool checkAll() {
for (auto it : build) {
int x = it.first.first, y = it.first.second, a = it.second;
if (a == 0) {
if (!rule1(x, y)) return false;
}
else {
if (!rule2(x, y)) return false;
}
}
return true;
}
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
vector<vector<int>> answer;
for (vector<int> v : build_frame) {
int x = v[0], y = v[1], a = v[2], b = v[3];
if (b == 1) { // 구조물 설치
build.insert({ {x, y}, a });
if (!checkAll()) build.erase({ {x, y}, a }); // 규칙을 만족시키지 않으면 제거
}
else { // 구조물 삭제
build.erase({ {x, y}, a });
if (!checkAll()) build.insert({ {x, y}, a }); // 규칙을 만족시키지 않으면 다시 추가
}
}
for (auto it : build) {
answer.push_back({ it.first.first, it.first.second, it.second });
}
sort(answer.begin(), answer.end());
return answer;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 이중우선순위큐 (0) | 2020.09.02 |
---|---|
[프로그래머스] 3 x n 타일링 (0) | 2020.09.02 |
[프로그래머스] 단속카메라 (0) | 2020.08.31 |
[백준] 11005 진법 변환 2 (0) | 2020.08.31 |
[프로그래머스] 행렬의 곱셈 (0) | 2020.08.31 |