옛날 옛적, 1996년에 출시된 "바람의 나라"에선 플레이어들이 이런 메세지를 외치곤 했다.
사냥터에 다람쥐가 모두 사냥당하는 동안에도 새로운 다람쥐가 생성되지 않으면, 어서 생성되기를 재촉하면서 플레이어들은 저런 메세지를 썼다.
2038년, 바람의 나라 출시 4242년이 지나, 주모 왈숙은 사냥터에 다람쥐를 생성하는 규칙을 바꾸기로 하였다. DoD(DaramG on Demand)라 불리는 최첨단 기술을 통해 다람쥐가 적어도 플레이어 수보다 두 배가 되도록 유지해서 사람이 많을 때도 충분한 양의 다람쥐가 있게끔 하기로 했다.
가로 �N칸, 세로 �N칸으로 구성된 게임 화면에서 칸마다 캐릭터 또는 다람쥐가 있는지 주어질 때, 다람쥐가 모자란 지 판단해 모자란다면 필요한 다람쥐를 생성할 위치를 출력하는 프로그램을 작성하여라.
입력
첫 줄에 게임 화면의 크기 �N이 주어진다. �N은 55 이상 2020 이하이다. 다음 �N 줄에 걸쳐 �N개의 문자가 공백 없이 주어진다. 문자는 다음 중 하나이다:
D: 다람쥐가 있음
C: 플레이어 캐릭터가 있음
.: 빈칸임
출력
입력 형식에서 게임 화면을 출력한 것과 동일하게, 먼저 첫 줄에 N을 출력하고 그 다음 N줄에 걸쳐 N개의 문자를 공백 없이 사용하여 임의로 정한 다람쥐의 배치 상태를 출력한다. 문자는
D, C, . 중 하나가 되어야 한다.새로운 다람쥐는 같이
D문자를 사용하며, 위치는 수만 만족하면 아무 곳이나 지정하여도 무방하다.다람쥐가 모자라지 않으면 새로운 다람쥐를 생성하지 않고 입력된 내용을 그대로 출력해야 한다. 반면 다람쥐가 모자라다면 출력된 다람쥐의 수가 적어도 플레이어 수보다 두 배가 되도록 하여야 한다. 다람쥐 및 플레이어 캐릭터들은 서로 겹쳐있을 수 없다. 입력은 필요로 하는 다람쥐를 항상 생성할 수 있음이 보장된다.
예제 1
입력
5 ..... ..... .C... ..... .....
출력
5 D.... ..D.. .C... ..... .....
예제 2
입력
5 DD... .D... .D... .DD.. .....
출력
5 DD... .D... .D... .DD.. .....
다람쥐만 있는 경우에는 플레이어 수가 00이므로, 다람쥐가 모자라지 않다. 따라서 새로운 다람쥐를 만들어서는 안 된다.
풀이
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include <list> using namespace std; #define MAX 21 int N; char map[MAX][MAX]; int playerCount = 0; int DCount = 0; queue<pair<int, int>> emptyqueue; void Input() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; if (map[i][j] == 'C') { playerCount++; } else if (map[i][j] == 'D') { DCount++; } else if(map[i][j] == '.') { emptyqueue.push({i,j}); } } } } void printMap() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << map[i][j]; } cout << '\n'; } } void Solution() { if (playerCount == 0) { printMap(); return; } while (DCount < playerCount * 2) { if (emptyqueue.empty() == true) break; pair<int, int> idx = emptyqueue.front(); emptyqueue.pop(); map[idx.first][idx.second] = 'D'; DCount++; } printMap(); } void Solve() { Input(); Solution(); } int main() { Solve(); }
우선 맵의 최대 사이즈가 20이하 이기 때문에 MAX를 21로 디파인 해주었다.
vector 컨테이너를 통해, 사이즈를 먼저 입력 받아서 동적으로 할당해줄 수 도 있었겠지만.
오버헤드로 인한 시간 차이가 이전 코테를 할 때 마다 경험했기 때문에 이중배열로 Map을
만들어주었다.
Input
일단 처음 input() 메서드가 실행되면 N을 입력받고 N의 크기 만큼 2중 포문을 돈다.
이후 입력 받은 것을 map에 넣어두고, 곧 바로 입력 받은 게 ‘C’ ,‘D’ ,’.’ 인지 구분한 뒤
Player와 다람쥐는 각각의 카운터를 1씩 증가 시켜주었다.
여기서 ‘.’ 즉 비어있는 곳은 일부러 queue에 넣어두었는데, 나중에 찾을 때 .의 위치를 찾기 위해 탐색하는 오버헤드를 줄이기 위해서다.
Solution
Player Count가 0이라면 곧 바로, Map을 출력해주고 종료한다.
아니라면, while문을 돌건데, 다람쥐 카운터가 Player Count의 2배 보다 작을 때 까지
반복한다.
이 때 emptyqueue 즉, 빈 공간이 없을 땐 반복문을 강제로 빠져나온다.
그게 아니라면 queue에서 하나하나 데이터를 뽑아서 map에 저장된 .을 ‘D’로 바꿔주고
DCount를 증감 시켜주었다.
이 후, 맵을 출력함으로써 끝이 난다.
IO결과
랜덤으로 뽑아보자
문제에선 따로, 순서에 상관없이 뽑아도 괜찮다고 했지만 그럼에도 출력 예시가 랜덤으로 나왔다 보니 이에 맞춰 랜덤으로도 한 번 뽑아보고자 한다.
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include <list> #include<ctime> using namespace std; #define MAX 21 int N; char map[MAX][MAX]; int playerCount = 0; int DCount = 0; vector<pair<int, int>> emptyvector; void Input() { cin >> N; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; if (map[i][j] == 'C') { playerCount++; } else if (map[i][j] == 'D') { DCount++; } else if(map[i][j] == '.') { emptyvector.push_back({i,j}); } } } } void printMap() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << map[i][j]; } cout << '\n'; } } void randomIdx() { srand(time(0)); std::random_shuffle(emptyvector.begin(), emptyvector.end()); } void Solution() { if (playerCount == 0) { printMap(); return; } randomIdx(); while (DCount < playerCount * 2) { if (emptyvector.empty() == true) break; pair<int, int> idx = emptyvector.back(); emptyvector.pop_back(); map[idx.first][idx.second] = 'D'; DCount++; } printMap(); } void Solve() { Input(); Solution(); } int main() { Solve(); }
바뀐 부분은 queue가 vector로 바뀌었고, randomidx라는 메서드가 추가 되었다.
일단 std::random_shuffle는 Visual C++에서 표준 템플릿 라이브러리에서 제공해주는
함수이며, 인자로 이터레이터의 시작과 끝을 받는다.
queue는 이터레이터가 없기 때문에, 랜덤 배치를 하려면 vector를 사용하면 편하다.
