[알고리즘] 백준15662 톱니바퀴(2)

문제

백준15662 톱니바퀴(2)

구상

• 톱니바퀴가 조건에따라 연결되어 회전한다.
• 제일 처음 회전시키는 톱니바퀴를 기준으로 왼쪽과 오른쪽을 확인하여 회전조건을 만족할 경우 하나의 자료형에 해당 톱니바퀴의 인덱스와 회전방향을 저장하여 한번에 회전시키면 되지않을까??

코드

#include<bits/stdc++.h>
using namespace std;
int t,k;
string a[1001];
void rotateGear(int idx, int d){
	if(d==1){ // 시계방향 회전 
		int temp = a[idx][7]; 
		for(int i=7; i>0; i--){ 
			a[idx][i]=a[idx][i-1];
		}
		a[idx][0]=temp;
	}
	if(d==-1){ // 반시계 방향 회전 
		int temp = a[idx][0];
		for(int i=0; i<8; i++){
			a[idx][i]=a[idx][i+1];
		}
		a[idx][7] = temp;
	}
}
int countS(){ //S극인 톱니바퀴 개수 count 
	int cnt = 0;
	for(int i=0; i<t; i++){
		if(a[i][0]=='1'){
			++cnt;
		}
	}
	return cnt;
} 
void go(int idx,int d){
	vector<pair<int,int>> v;
	v.push_back({idx,d});
	int now = idx;
	int nowd = d;
	while(now>0){ //왼쪽 맞닿은 톱니바퀴 
		if(a[now][6]!=a[now-1][2]){
			--now;
			nowd*=-1;
			v.push_back({now,nowd});
		}
		else{
			break;
		}
	}
	now = idx;  //입력받은 index 기준으로 초기화 
	nowd = d;
	while(now<t-1){ //오른쪽 맞닿은 톱니바퀴
		if(a[now][2]!=a[now+1][6]){
			++now;
			nowd*=-1;
			v.push_back({now,nowd});
		}
		else{
			break;
		}
	}
	for(int i=0; i<v.size(); i++){ //회전  
		rotateGear(v[i].first,v[i].second);
	}
}
int main(){
	cin >> t; // 톱니바퀴 개수 
	for(int i=0; i<t; i++){//톱니바퀴 입력
		cin>>a[i];
	}
	cin >> k; //회전 횟수 
	for(int i=0; i<k; i++){//회전 방법 입력 (톱니바퀴 번호, 방향) 
		int idx,d;
		cin>>idx>>d;
		go(idx-1,d);
	}
	// 12시 방향이 s극인 톱니바퀴의 개수 출력
	cout<< countS(); 
	return 0;
}

1. 가장 처음 회전하려는 톱니바퀴의 인덱스를 기준으로 왼쪽을 탐색한다.
   1.1. 왼쪽의 2번째 톱니바퀴와 현재의 6번째 톱니바퀴를 비교하여, 다르다면 벡터에 저장
   1.2. 왼쪽으로 계속 진행하다가 끝에 다다르거나 같은 값이라면 break (종료조건)
2. 같은 방식으로 오른쪽을 탐색한다.
3. 벡터에 든 톱니바퀴들을 회전방향에 맞게 회전시킨다.

하지만 회전하는 부분을 rotate 함수를 사용해 구현한다면 더 쉽게 구현할 수 있다!

---

rotate

rotate 함수는 값들을 왼쪽, 오른쪽으로 지정한 값만큼 회전시킬 수 있다.

Parameters

rotate(first,seocnd,third);

Parameters	description
first	회전할 범위의 시작 iterator
second	회전하여 첫번째 요소가 될 범위 내 iterator
third	회전할 범위의 마지막 iterator

활용 예시

vector<int> v = {10,20,30,40,50};

//왼쪽으로 1칸 이동
rotate(v.begin(),v.begin()+1,v.end());
-> 20,30,40,50,10

//왼쪽으로 3칸 이동
rotate(v.begin(),v.begin()+3,v.end());
-> 40,50,10,20,30

//오른쪽으로 1칸 이동
rotate(v.begin(),v.end()-1,v.end());
-> 50,10,20,30,40

//오른쪽으로 3칸 이동
rotate(v.begin(),v.end()-1,v.end());
-> 30,40,50,10,20

rotate 활용하여 수정한 코드

#include<bits/stdc++.h>
using namespace std;
int t,k;
string a[1001];
void rotateGear(int idx, int d){
	if(d==1){ // 시계방향 회전 
		rotate(a[idx].begin(),a[idx].end()-1,a[idx].end()); 
	}
	if(d==-1){ // 반시계 방향 회전 
		rotate(a[idx].begin(),a[idx].begin()+1,a[idx].end());
	}
}
int countS(){ //S극인 톱니바퀴 개수 count 
	int cnt = 0;
	for(int i=0; i<t; i++){
		if(a[i][0]=='1'){
			++cnt;
		}
	}
	return cnt;
} 
void go(int idx,int d){
	vector<pair<int,int>> v;
	v.push_back({idx,d});
	int now = idx;
	int nowd = d;
	while(now>0){ //왼쪽 맞닿은 톱니바퀴 
		if(a[now][6]!=a[now-1][2]){
			--now;
			nowd*=-1;
			v.push_back({now,nowd});
		}
		else{
			break;
		}
	}
	now = idx;  //입력받은 index 기준으로 초기화 
	nowd = d;
	while(now<t-1){ //오른쪽 맞닿은 톱니바퀴
		if(a[now][2]!=a[now+1][6]){
			++now;
			nowd*=-1;
			v.push_back({now,nowd});
		}
		else{
			break;
		}
	}
	for(int i=0; i<v.size(); i++){ //회전  
		rotateGear(v[i].first,v[i].second);
	}
}
int main(){
	cin >> t; // 톱니바퀴 개수 
	for(int i=0; i<t; i++){//톱니바퀴 입력
		cin>>a[i];
	}
	cin >> k; //회전 횟수 
	for(int i=0; i<k; i++){//회전 방법 입력 (톱니바퀴 번호, 방향) 
		int idx,d;
		cin>>idx>>d;
		go(idx-1,d);
	}
	// 12시 방향이 s극인 톱니바퀴의 개수 출력
	cout<< countS(); 
	return 0;
}