티스토리 뷰
https://school.programmers.co.kr/learn/courses/30/lessons/1835
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이번 문제는 각 프렌즈가 줄을 서기를 원하는 조건들이 주어졌을 때, 적절한 줄의 개수를 구하는 문제이다. 이 문제를 풀기 위해서는 순열이라는 개념을 알아야 한다. 만약 1번 사람, 2번 사람, 3번 사람을 줄을 세웠을 때, 1번-2번-3번 순으로 줄을 서는 것과 2번-3번-1번 순으로 줄을 서는 것을 다르게 취급하는 경우를 순열이라 한다. 즉, 이 문제에서는 어피치부터 튜브까지 줄을 세울 수 있는 모든 경우를 검사해야 하는데, 이를 순열을 이용해서 구할 수 있다. 문제를 해결하기 위해 구상한 절차는 다음과 같다.
- 모든 값들을 초기화한다.
- 순열 개념을 이용해 줄을 세운 후, 줄이 세워졌을 때 검사한다.
- 모든 사람들을 한 번씩 검사하면서, 줄을 서지 않았다면 줄을 세운다.
- 만약 모든 사람들이 줄을 섰다면, 이 줄이 가능한 줄인지 확인한다.
- 현재 각 사람들의 줄 위치를 저장한다.
- 모든 조건들을 하나씩 검사하면서, 가능한 줄인지 확인한다.
- 만약 불가능한 줄이라면, return으로 빠져나간다.
- 만약 가능한 줄이라면 답을 +1 한다.
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define MAX 8
// 문제에서 주어지는 조건들의 타입형
typedef struct
{
int person1;
int person2;
char type;
int distance;
} Condition;
int answer = 0; // 답을 젖아할 변수
bool checked[MAX]; // i번 사람이 줄을 섰는지를 저장할 변수
int personPos[MAX]; // i번 사람의 현재 줄 위치
vector<int> line; // 사람들이 선 줄
vector<Condition> conditions; // 주어진 조건들을 저장할 배열
map<char, int> personIdx; // A 등의 사람 이름을 숫자로 바꾸기 위함
void Check()
{
// 2-2, 만약 모든 사람들이 줄을 섰다면, 이 줄으 기능한 줄인지 확인한다.
if (line.size() >= MAX)
{
bool success = true; // 현재 줄이 가능한 줄이라면 true
// 2-2-1. 현재 각 사람들의 줄 위치를 저장한다.
for (int i = 0; i < line.size(); ++i)
{
int curPerson = line[i];
personPos[curPerson] = i;
}
// 2-2-2. 모든 조건들을 하나씩 검사하면서 가능한 줄인지 확인한다.
for (int i = 0; i < conditions.size(); ++i)
{
Condition condition = conditions[i];
int person1Pos = personPos[condition.person1];
int person2Pos = personPos[condition.person2];
switch(condition.type)
{
case '=':
if (abs(person1Pos - person2Pos) != condition.distance)
success = false;
break;
case '>':
if (abs(person1Pos - person2Pos) <= condition.distance)
success = false;
break;
case '<':
if (abs(person1Pos - person2Pos) >= condition.distance)
success = false;
break;
}
// 2-2-3. 만약 불가능한 줄이라면 return으로 빠져나간다.
if (success == false)
return;
}
// 2-2-4. 만약 가능한 줄이라면 답을 +1 한다.
++answer;
return;
}
// 2-1. 모든 사람들을 한 번씩 검사하면서, 줄을 서지 않았다면 줄을 세운다.
for (int i = 0; i < MAX; ++i)
{
if (checked[i] == false)
{
checked[i] = true;
line.push_back(i);
Check();
line.pop_back();
checked[i] = false;
}
}
}
int solution(int n, vector<string> data)
{
// 1. 전부 초기화한다.
answer = 0;
for (int i = 0; i < MAX; ++i)
{
checked[i] = false;
personPos[i] = -1;
}
line.clear();
conditions.clear();
personIdx['A'] = 0;
personIdx['C'] = 1;
personIdx['F'] = 2;
personIdx['J'] = 3;
personIdx['M'] = 4;
personIdx['N'] = 5;
personIdx['R'] = 6;
personIdx['T'] = 7;
for (int i = 0; i < data.size(); ++i)
{
string curData = data[i];
Condition condition;
condition.person1 = personIdx[curData[0]];
condition.person2 = personIdx[curData[2]];
condition.type = curData[3];
condition.distance = curData[4] - '0' + 1;
conditions.push_back(condition);
}
// 2. 순열 개념을 이용해 줄을 세운 후, 줄이 세워졌을 때 검사한다.
Check();
return answer;
}
'알고리즘 문제' 카테고리의 다른 글
프로그래머스 - 카카오프렌즈 컬러링북 (C++) (0) | 2023.03.21 |
---|---|
프로그래머스 - 택배 배달과 수거하기 (C++) (1) | 2023.03.20 |
프로그래머스 - 기둥과 보 설치 (C++) (0) | 2023.03.18 |
프로그래머스 - 불량 사용자 (C++) (0) | 2023.03.13 |
프로그래머스 - 입국심사 (C++) (1) | 2023.03.11 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 타입스크립트
- 비트마스킹
- 카카오맵
- 동적계획법
- SQL
- aws
- 알고리즘
- themoviedb
- CSS
- 다이나믹프로그래밍
- NextJS
- BFS
- Redux
- Next.js
- 넥스트js
- react
- 자바스크립트
- 백준
- typescript
- 구현
- 햄버거버튼
- 브루트포스
- 완전탐색
- 프로그래머스
- 스택
- C++
- 코드스테이츠
- 순열
- 리액트
- async
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함