코드업 4422 숫자고르기 해설. 정보올림피아드 초등 (정올 초등)

4번의 시도끝에 맞춘  재미있는 문제다.

해당 숫자가 있는지 없는지를 DFS로 탐색해서 판단했다.

 

항상 어떤 문제를 풀든  직접 따져봐야한다.

내 머릿속이 이 결과를 어떻게 만들어내는지 분석해서 번호를 메기고

그 순서대로 구현해야한다.

그렇지않으면 뻘짓하다가 시간만 날린다.

#include <stdio.h>

using namespace std;

	
bool solve(int nowNum, int startNum, int *data, int *result, int n){
	
	if(nowNum == startNum){
		result[nowNum]=1;
		return true;
	}
	
	for(int i=1;i<=n;i++){
		if(data[i] == nowNum){
			if(solve(i,startNum, data,result,n)) {
				result[nowNum]=1;
				return true;	
			}
		}
	}
	
	return false;
}

int main()
{
	int cnt=0;	
	int n;
	scanf("%d",&n);
	
	int data[101]={};
	int result[101]={};
	
	for(int i=1;i<=n;i++){
		scanf("%d",&data[i]);	
	}
	
	
	for(int i=1;i<=n;i++){
        //해당 표에 들어간 숫자랑,  인덱스가 같으면 바로 정답처리
		if(i==data[i]) {
			result[i]=1;
            continue;
		}
        //같지않으면 해당 숫자가 표에 있는지 dfs로 탐색
		solve(i,data[i],data,result,n);
	}
	
	
	for(int i=1;i<=n;i++){
		if(result[i]){
			cnt++;	
		}
	}
	
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		if(result[i]){
			printf("%d\n",i);
		}
	}
	
	
	return 0;	
}

 

 

codeup.kr/problem.php?id=4422

숫자 고르기

 

 

시행착오 과정

1차도전 :  단순히 후보숫자 명단과 정답 명단 만들어 매치시키면 될줄알았으나 테스트4에서 탈락

2차도전 : 스택이용해서  해당숫자들 담아가며 접근해봤지만 찾을 숫자를 만나면 스택에서 바로빼버렸더니 첫번째 예제에서 틀려버림.

3차도전: 다른 케이스 뜨면 분기시키는거까지 감안해서  스택이랑 벡터를 함수인자로 넘겼는데 테스트8에서 틀림.

틀린이유를 분석해보니   스택에 넣고  그 다음원소부터 보는게아니라 다시 맨처음부터 봐야했음.. 결론 dfs로 그냥 애초부터 짰으면 편함을 깨달음..

 

//1차 도전코드

#include <stdio.h>

int main()
{
	
	int n;
	scanf("%d",&n);
	
	int candidate[101]={};
	int answer[101]={};
	
	int cnt=0;
	
	for(int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		
		if(i<t){
			candidate[t] = i;
		}
		else if(i==t){
			answer[i] = t;
			cnt++;
		}
		else {
			if(candidate[i] == t){
				answer[i] = i;
				answer[t] = t;
				cnt+=2;
			}
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		if(answer[i]) 
		printf("%d\n",answer[i]);	
	}
	
	return 0;	
}

//2차 도전코드

#include <stdio.h>
#include <stack>

using namespace std;

int main()
{
	
	int n;
	scanf("%d",&n);
	
	int inputData[101]={};
	int answer[101]={};
	
	int cnt=0;
	
	for(int i=1;i<=n;i++){
		scanf("%d",&inputData[i]);
	}
	
	for(int i=1;i<=n;i++){
		printf("now i %d \n",i);
		int data = inputData[i];	
		int candidate[101]={};
		stack<int> stk;
		if(data == i){
			answer[i] = data;
			cnt++;	
		}
		else{	
			stk.push(data);
			stk.push(i);	
			for(int j=i+1;j<=n && stk.empty()==0 ;j++){
				printf("inputData[%d] == %d .. %d==%d\n",j,stk.top(), inputData[j],stk.top());
				if(inputData[j] == stk.top()){
					candidate[stk.top()] = stk.top();
					stk.pop();
					
					if(j == stk.top()) {
					stk.pop();
					candidate[j] = j;
					}
					else stk.push(j);
				}
			}
			
			if(stk.empty()){
				for(int i=1;i<=n;i++){
					if(candidate[i] && answer[candidate[i]]==0){
						cnt++;
						answer[candidate[i]]=candidate[i];	
					}
				}
			}
			
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		if(answer[i]) 
		printf("%d\n",answer[i]);	
	}
	
	return 0;	
}


//3차 도전코드
#include <stdio.h>
#include <stack>
#include <vector>

using namespace std;

//스택도 값복사 시켜서 넘기고,  candidate도 값복사시켜서 넘기고. 
bool isComplete(int start, vector<int> datas, stack<int> stk, int*answer, int *inputData, int n, int *cnt){

	for(int j=start;j<=n && stk.empty()==0 ;j++){
		printf("inputData[%d] == %d .. %d==%d\n",j,stk.top(), inputData[j],stk.top());
		if(inputData[j] == stk.top()){
			if(isComplete(j+1,datas,stk,answer,inputData,n,cnt)) {
				
				return true;
			}
			datas.push_back(stk.top());
			stk.pop();
			
			if(j == stk.top()) {
			stk.pop();
			datas.push_back(j);
			}
			else stk.push(j);
		}
	}
	
	if(stk.empty()){
		for(int i=0;i<datas.size();i++){
			
			if(answer[datas[i]]==0){
				(*cnt)++;
				answer[datas[i]]=datas[i];	
			}
		}
		return true;
	}
	
	

	return false;	
}
int main()
{
	
	int n;
	scanf("%d",&n);
	
	int inputData[101]={};
	int answer[101]={};
	
	int cnt=0;
	
	for(int i=1;i<=n;i++){
		scanf("%d",&inputData[i]);
	}
	
	for(int i=1;i<=n;i++){
		printf("now i %d \n",i);
		int data = inputData[i];	
		int candidate[101]={};
		stack<int> stk;
		if(data == i){
			answer[i] = data;
			cnt++;	
		}
		else{	
			stk.push(data);
			stk.push(i);	
			vector<int> datas;
			if(isComplete(i+1,datas, stk, answer, inputData,n,&cnt)){
					
			}
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		if(answer[i]) 
		printf("%d\n",answer[i]);	
	}
	
	return 0;	
}

//최종
#include <stdio.h>
#include <stack>

using namespace std;

int result[101]={};

	
bool solve(int next, int *data, stack<int> stk, int n){
	
	if(next == stk.top()){
		result[next]=1;
		return true;
	}
	
	for(int i=1;i<=n;i++){
		if(data[i] == next){
			if(solve(i,data,stk,n)) {
				result[next]=1;
				return true;	
			}
		}
	}
	
	return false;
}

int main()
{
	int cnt=0;	
	int n;
	scanf("%d",&n);
	
	int data[101]={};
	for(int i=1;i<=n;i++){
		scanf("%d",&data[i]);	
	}
	
	
	for(int i=1;i<=n;i++){
		if(i==data[i]) {
			result[i]=1;
		}
		stack<int> stk;
		stk.push(data[i]);
		solve(i,data,stk,n);
		stk.pop();
		
		
	}
	
	
	for(int i=1;i<=n;i++){
		if(result[i]){
			cnt++;	
		}
	}
	
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++){
		if(result[i]){
			printf("%d\n",i);
		}
	}
	
	
	return 0;	
}