문제해결기법 3주차) 움직이는 하노이의 탑

-> 똑같은 두 문제를 내주고 실행시간을 다르게주었던 상당히 짜증나는 문제;; 내가 푼 코드는 1단계는 통과하는데 2단계를 통과하지 못했다. 그래서 다르게 푼 분한테 설명을 받았는데 너무 간단해서 좌절했다ㅜㅜ 나는 언제 이렇게 풀까?

 

1) 내가 푼 방식- MAX부터 완전 탐색으로 내려온다. 실행시간이 easy는 되는데 hard에서 막혔다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


int main() {
	std::ios::sync_with_stdio(false);
	int T;
	cin >> T;

	while (T--) {
		int num;
		cin >> num;
		vector<int>sorting;//sorting 된 배열 저장
		vector<int>original;//원래 배열 저장

		while (num--) {
			int a;
			cin >> a;
			sorting.push_back(a);
			original.push_back(a);
			
		}
		
		sort(sorting.begin(), sorting.end());

		int rotatenum = 0;
        int max = sorting.back();
		int size = original.size();
		while (true) {
			
			for (int i = 0; i <size; i++) {
				if (max == original[i]) {
					sorting.pop_back();
					original[i] = -1;
					
					if ( sorting.size()==0 ) {
						break;
					}
					max = sorting.back();
				}

			}
		     
			rotatenum++;
			if (sorting.size() == 0) {
				break;
			}
		}
		cout << rotatenum << endl;
		
	}

}

 

 

2) 다른 방식- 계수정렬을 이용해서 풀었다. 하노이의 탑이므로 정수가 연속된 크기로 되어있음을 이용해 앞 배열이 차있으면 한번 회전한 것으로 간주한듯. 완전 쉬운 문제였네ㅠㅠ

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	int T;
	cin >> T;

	while (T--) {
		int num;
		cin >> num;
		int sorting[10000];//sorting 된 배열 저장
		int original[10000];//원래 배열 저장

		memset(sorting, 0, sizeof(sorting));
		memset(original, 0, sizeof(original));

		for(int i=0;i<num;i++){
			cin >> original[i];
		}
       
		int max = 10000;
		
		int count = 1;//이미 내림차순 정렬되어있어도 기본으로 한번은 돌아감
		
		for (int p = 0; p < num; p++) {
			if (original[p]) {
				sorting[original[p]]++;
				if (sorting[(original[p] - 1)] == 1) {
					//하노이의 탑이므로 연속된 정수의 배열을 갖고있음
					//앞 배열의 인덱스가 차있으면 그때 한번 회전해서 돌아간 것으로 간주함
					count++;
				}
			}
		}
		cout << count << endl;

	}

}

 

 

덧. 문해기 동안 계수정렬이 뭔지는 확실히 알고가는거같다ㅋㅋㅋㅋㅋㅋ