문제 이해 단계
https://www.acmicpc.net/problem/15787
입력으로 N개의 열차와 M개의 명령이 주어진다.
각 열차에는 한 줄로 20개의 좌석으로 구성되어 있다.
명령은 총 3마디로 주어지는데,
첫 번째는 명령의 종류 두 번째는 명령을 받을 기차, 세 번째는 좌석을 뜻한다.
명령의 종류는 다음과 같다.
1. 해당 기차의 해당 좌석에 인원 추가
2. 해당 기차의 해당 좌석에 인원 제거
3. 해당 기차 모든 인원 1칸 뒤쪽으로 이동
4. 해당 기차 모든 인원 1칸 앞쪽으로 이동
이러한 명령이 끝났을 때,
좌석의 인원 배열이 중복을 제외하고선 몇 개인지 계산하는 문제
문제 접근 단계
해당 문제에서 중요하게 봐야 하는 점은
각 기차가 모두 20개의 좌석으로 이루어져 있고,
한 줄로 나열되어 있다는 점이다.
그리고 찾아야 할 것은 중복되지 않는 것,
즉 중복되는 것을 찾으라는 말이다.
그리고 1,2번 명령에서 말하는 것은
한 좌석을 지정해서 채우거나 비우는 것이라서 쉽게 할 수 있다.
하지만, 3번과 4번 명령인 모든 칸을 1칸씩 미루는 것
은 생각보다 많이 귀찮다.
해당 문제에서 기차 수 N과 명령 M이
최대 100000까지라 3번, 4번인데
좌석이 차있는 상태에서 3번, 4번만 들어온다면?
하나하나 옮기기에는 엄청나게 귀찮은 반복을 요구할 것이다.
그리고 구현도 복잡해지는 것 같다.
그래서 이를 좀 더 쉽게 구현할 생각 해보려고
그림을 그려봤다.
좌석에 앉히는 것을 빨간색으로 표시하면 이런 식으로 될 것인데,
이를 다르게 표시 가능할 것 같다.
좌석이 차있는 상태를 1,
좌석이 빈 상태를 0이라고 한다면 해당 상태는
00000010010000000000
이 될 것이다.
이 모양을 보니까 해당 문제는
이진법으로 표현이 가능하다.
그리고 3번, 4번 명령을
시프트연산으로 처리가 가능하다는 것을 알았다.
C++ STL 중에 <bitset>을 사용하면
비트 연산을 쉽게 사용가능하다.
bitset을 이용하여
해당 문제의 네 가지 문제를 구현해 보도록 한다.
문제 구현 단계
bitset<20> bits[100000];
void solution(int command, int train, int chair){
switch(command){
// 좌석 채우기
case 1:
bits[train].set(chair,true);
break;
// 좌석 빼기
case 2:
bits[train].set(chair,false);
break;
// 한 칸씩 뒤로 미루기
case 3:
{
//비트 연산을 unsigned long으로 만들어줌
unsigned long val = bits[train].to_ulong();
val = val << 1; // 왼쪽으로 시프트
bitset<20> tmp(val); // 다시 비트화
bits[train] = tmp;
}
break;
// 한 칸씩 앞으로 당기기
case 4:
{
unsigned long val = bits[train].to_ulong();
val = val >> 1; // 오른쪽으르 시프트
bitset<20> tmp(val);
bits[train] = tmp;
}
break;
}
}bitset을 이용한 명령구현이다.
bitset <20>이라고 선언하면 20개의 비트를 가지고 있는 변수를 생성한다.
이를 기차의 개수만큼 만들어준다.
좌석 채우기는 bits.set을 true를 통해 채워주고
빼기는 그 반대로 false를 통해 빼준다.
3번과 4번 연산은 비트 상태에서는 시프트연산이 안되기 때문에
정수형으로 전환해 준 다음 시프트 연산해 주고,
다시 bitset타입으로 바꿔준다.
사실 구현은 bitset을 사용하는 거 빼곤 크게 볼 것이 없다.
입력을 한 줄을 전체를 받아
띄어쓰기를 기준으로 끊어서 string으로 각 데이터를 받았다.
그리고 stoi를 이용해서 string을 int 형으로 바꾸려고 했는데,
에러가 많이 났다.
그래서 아래와 같이 수정하여 문제를 해결했다.
string line;
string input[3];
getline(cin,line);
istringstream ss(line);
ss >> input[0] >> input[1] >> input[2];
int command = atoi(input[0].c_str());
int train = atoi(input[1].c_str());
int chair = atoi(input[2].c_str());
1 libc++abi: terminating with uncaught exception of type
std::invalid_argument: stoi: no conversion
나는 위와 같은 에러가 계속 떴는데 결론으로 말하자면
string형으로 되어 있는 숫자를 int형을 만들려고 해서 그렇다.
그러니까 "76" 이렇게 되어있는 string을
76으로 바꾸려고 해서 그렇다는 것이다.
그래서 atoi를 사용했다.
atoi는 const char*을 int로 바꾸는 것이기 때문에
string을 const char*로 바꿔야 한다.
그래서 string에 c_str를 사용하여 const char*로 바꿔주었다.
이렇게 하면 정상적으로 변환이 된다.
이제 아래에 전체 코드를 올리고 설명을 끝내겠다.
#include <iostream>
#include <bitset>
#include <sstream>
#include <vector>
using namespace std;
bitset<20> bits[100000];
void solution(int command, int train, int chair){
switch(command){
case 1:
bits[train].set(chair,true);
break;
case 2:
bits[train].set(chair,false);
break;
case 3:
{
unsigned long val = bits[train].to_ulong();
val = val << 1;
bitset<20> tmp(val);
bits[train] = tmp;
}
break;
case 4:
{
unsigned long val = bits[train].to_ulong();
val = val >> 1;
bitset<20> tmp(val);
bits[train] = tmp;
}
break;
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N,M;
cin >> N >> M;
while(M-- >=0){
string line;
string input[3];
getline(cin,line);
istringstream ss(line);
ss >> input[0] >> input[1] >> input[2];
int command = atoi(input[0].c_str());
int train = atoi(input[1].c_str());
int chair = atoi(input[2].c_str());
solution(command,train-1,chair-1);
}
int ans = 1;
vector<string> visited = {bits[0].to_string()}; // 비트 자체를 문자열화
for(int i = 1; i < N; i++){
string val = bits[i].to_string();
bool overlap = false; // 중복 체크
for(string str : visited)
// 하나라도 겹치면 중복
if(str.compare(val) == 0) {
overlap = true;
break;
}
if(!overlap) {
ans++;
visited.push_back(bits[i].to_string());
}
}
cout << ans;
}
시행착오
해당 문제는 실수로 어떤 유형의 문제인지 봐버려서,
비트마스킹인걸 알고 풀었다.
아마 비트마스킹인걸 몰랐으면 못 풀었을 것 같다.
그래서 블로그에 풀이를 올리기로 했다.
이 문제를 풀면서 배우는 게 많았던 것 같다.
C++ STL에 bitset 라이브러리를 처음 사용해 봤는데,
이걸 학습하는 좋은 기회였고,
stoi에 관해 공부할 수 있는 좋은 기회가 되었다.
또한 시프트 연산을 활용을 할 수 있어서 괜찮았던 것 같다.