알고리즘 문제풀이전에 할것. 자료구조 선택하기 - 백준 알고리즘 오답노트 1012

https://www.acmicpc.net/problem/1057

1057번: 토너먼트

 

 

#알고리즘 문제풀이전에 반드시 생각 할것. 자료구조 선택하기 

 

 

#1. 문제 풀이 자료구조 선택

 

처음에는 자료구조를 배열로 해서 복잡한 코드를 구상했다.

배열과 check 배열을 이용해서 해당 범위를 점차 늘려가면서 한명을 뽑는 과정을 생각함. 그러나 3중 for문을 이용하게 되고, 복잡하게 엉킹 반복변수 i는 고뇌하며 피를 토하기 시작함.

 

그리고 코드를 싹 지우고 다시 다른 방법을 생각했다.

스택이나 큐 등의 기본적인 STL 컨테이너를 생각해서 시뮬레이션 과정을 대폭 줄임,
간단하고 이해하기 쉽게 ~ 

 

 

#2. 논리 실수 

 

 

 

아직도 저런 경우에는 어떻게 해야 될 지 모르겠다. 특히나 이번경우에는 예시의 testcase는 잘 통과해서

왜 틀렸는지 몰라서 앞이 캄캄해 졌다. 빈혈인가. 

 

제일 힘든 상황이 주어진 Testcase을 통과했고 내 코드는 계속 틀려있는 경우다 .

내 코드가 통과하지 못하는 TestCase을 내가 만들어 내야 되니까.

x = q.front(); q.pop();
y = q.front(); q.pop();
// cout<<"x : "<<x<<" y : "<<y<<"\n";
if(x == 'A' && y == 'B' || x == 'B' && y == 'A'){ // FB2. A,B가 순서가 바뀔수도 있잔항...
cout<<round<<"\n";
return 0;
}
else if( x == 'A' || y =='A'){ // FB2. y가 B일 수도 있잖아
tmp.push('A');
}
else if( x == 'B' || y == 'B'){
tmp.push('B');
}
else{
tmp.push('.');
}

 

 

 

//1057 


#include 
#include 
#include 
#include 

using namespace std; 
bool state[100002]; 
int main(){ 
//입력 처리 
int n; cin>>n; int a,b; cin>>a>>b; 
int round = 1; 
queue q; 
for(int i = 1; i <= n ; i++){ 
if(i == a){ 
q.push('A'); 
} 
else if(i == b){ 
q.push('B'); 
} 
else{ 
q.push('.'); 
} 
} 
// while(!q.empty()){ 
//  cout<<q.front()<<" "; q.pop(); 
// } 
//cout<<"\n"; 
while(true){ 

int countoffight = q.size() / 2; 
bool isodd = (q.size() % 2 == 1) ? true : false; 
queue tmp; 

for(int i = 1 ; i<= countoffight; i++){ 
char x,y; 
x = q.front(); q.pop(); 
y = q.front(); q.pop(); 
// cout<<"x : "<<x<<" y : "<<y<<"\n"; 
if(x == 'A' && y == 'B' || x == 'B' && y == 'A'){ // FB2. A,B가 순서가 바뀔수도 있잔항... 
cout<<round<<"\n"; 
return 0; 
} 
else if( x == 'A' || y =='A'){ // FB2. y가 B일 수도 있잖아 
tmp.push('A'); 
} 
else if( x == 'B' || y == 'B'){ 
tmp.push('B'); 
} 
else{ 
tmp.push('.'); 
} 
} 

if(isodd){ 
tmp.push(q.front()); q.pop(); 
} 

round++; 
q = tmp; 
// cout<<"size : "<<q.size()<<"\n"; 
if(q.size() == 1)break; 
} 
return 0; 

} 

//FB1. 문제 풀이 자료구조 선택 
/* 
처음에는 자료구조를 배열로 해서 복잡한 코드를 구상했으나, 
스택이나 큐 등의 기본적인 STL 컨테이너를 생각해서 시뮬레이션 과정을 대폭 줄임, 
간단하고 이해하기 쉽게 ~  
*/ 

//FB2. 논리 실수 ,  
/* 
x = q.front(); q.pop(); 
y = q.front(); q.pop(); 
// cout<<"x : "<<x<<" y : "<<y<<"\n"; 
if(x == 'A' && y == 'B' || x == 'B' && y == 'A'){ // FB2. A,B가 순서가 바뀔수도 있잔항... 
cout<<round<<"\n"; 
return 0; 
} 
else if( x == 'A' || y =='A'){ // FB2. y가 B일 수도 있잖아 
tmp.push('A'); 
} 
else if( x == 'B' || y == 'B'){ 
tmp.push('B'); 
} 
else{ 
tmp.push('.'); 
} 


*/

 

 

 

 

 

 

 

 

 

플라즈마 IT 블로그 - 코딩 공부 정리, IT 정보 공유

 

https://plasmacodeing.tistory.com/

 

조금이라도 도움이 되었다면 공감 및 댓글 주세요~~