22.06.28

45. 공주 구하기

문제 설명: 배열에서 순서대로 k번째에 있는 수를 제거해서 마지막에 남은 수를 출력하는 문제였다.

int main(){
	//freopen("input.txt","rt",stdin);
	
	int n,k;
	cin>>n>>k;
	
	
	vector<int> prince;
	for(int i = 1; i<=n; i++){
		prince.push_back(i);
	}
	
	int pos = 0;
	while(prince.size()>1){
		int left = k%n;
		
		int eraseIdx = pos+left-1;
		
		if(eraseIdx>= prince.size()){
			eraseIdx%=prince.size();
			
		}
		
		prince.erase(prince.begin()+eraseIdx);
		pos = eraseIdx;		
		
	}
	cout<<prince[0];
	return 0;
	
}

강의를 보면 직접 배열을 계속 돌면서 수를 0으로 바꿔서 마지막에 0이 아닌 수를 출력하는데, 나는 배열의 크기를 이용해서 몇번째 수를 지워야하는지 구한 후 erase 함수를 이용해 진짜로 지워버렸다. erase함수 특성을 고려했을 때 좀 비효율적일 것 같다.

처음에 풀었을 땐 eraseIdx를 그냥 두고 지울 때 eraseIdx-1 로 조정을 해줬고 조건문도 eraseIdx>prince크기 일 때로 했었는데, 테스트케이스 2개가 오류가 났다 계속 고민해봐도 아직은 왜 답이 똑바로 안 나왔는지 모르겠다.

46. 멀티태스킹

문제 설명:

int main(){
	//freopen("input.txt","rt",stdin);
	
	int n,k,tmp,sum;
	cin>>n;
	
	vector<int> task;
	for(int i =0; i<n;i++){
		cin>>tmp;
		task.push_back(tmp);
		sum+=tmp;
	}
	cin>>k;
	
	if(k>=sum){
		cout<<-1;
		return 0;
	}
	
	int pos=-1, sec=0;
	while(1){
		pos++;
		if(pos>task.size()){
			pos=0;
		}
		if(task[pos]!=0){
			task[pos]--;
			sec++;
		}
		if(sec>k)
			break;
		
	}
	
	cout<<pos+1;
	return 0;
	
}

45번 문제와 거의 유사해서 45번 강의에서 나온 코드를 이용해서 풀었다. 문제는 다 처리했을 경우에는 -1을 출력하는 것이었는데, 그냥 작업 소요시간 총합 < k 이면 -1을 출력하는 걸로 1차 검증을 했다.

47. 봉우리

문제 설명: 2차원 배열이 주어졌을 때 해당 위치의 수가 상하좌우의 수보다 크면 봉우리로 판단, 봉우리의 갯수를 구하는 문제

int main(){
	//freopen("input.txt","rt",stdin);
	
	int n,tmp;
	cin>>n;
	vector<vector<int>> hight(n+2,vector<int>(n+2,0));
	
	for(int y=1; y<=n; y++){
		for(int x=1; x<=n; x++){
			cin>>tmp;
			hight[y][x]=tmp;
		}
	}

	int answer = 0;
	int mid, top, left, right, bottom;
	for(int py=1; py<=n; py++){
		for(int px=1; px<=n; px++){
			mid = hight[py][px];
			top = hight[py-1][px];
			left = hight[py][px-1];
			right =hight[py][px+1];
			bottom = hight[py+1][px];
			if(mid>top&&mid>left&&mid>right&&mid>bottom){
				answer++;
			}
		}
	}
	cout<<answer;
	return 0;
	
}

이차원 배열을 오랜만에 봐서 초기화 하는 방법을 찾아봤다. 그냥 정직하게 다 돌면서 확인하는 방식으로 푸니 쉽게 풀렸다.

48. 각 행의 평균과 가장 가까운 값

int main(){
	//freopen("input.txt","rt",stdin);
	
	int avg, n, tmp, answer, min;
	double sum;
	vector<int> nums(9,0);
	
	for(int i =0; i<9 ;i++){
		sum=0;
		min=INT_MAX;
		for(int j=0; j<9; j++){
			cin>>tmp;	
			nums[j]=tmp;
			sum+=tmp;
		}
		avg = round(sum/9);
		cout<<avg<<' ';
		
		for(int j=0; j<nums.size(); j++){
			n=abs(nums[j]-avg);
			if(n<min){
				min = n;
				answer = nums[j];
			}
			else if(n==min&&nums[j]>answer){
				answer = nums[j];
			}
		}
		cout<<answer<<endl;
	}

	return 0;

}

49. 블록의 최댓값

문제 설명: 정면, 측면의 도면을 보고 최대로 쌓을 수 있는 블럭의 개수를 구하는 문제

int main(){
	//freopen("input.txt","rt",stdin);
	
	int n, answer=0, h, tmp;
	cin>>n;
	
	vector<vector<int>> shape(2,vector<int>(n,0));
	for(int i =0; i<2; i++){
	
		for(int j=0; j<n; j++){
			cin>>tmp;
			shape[i][j] =tmp; 
		}
	}
	
	for(int i=0; i<n; i++){
		h = shape[0][i];
		for(int j =0; j<n; j++){
			if(shape[1][j]>h){
				answer += h;
			}
			else{
				answer+=shape[1][j];
			}
		}
	}
	cout<<answer;
	return 0;

}

• 프로그래머스 : 징검다리 건너기(LEVEL3)

  

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

int solution(vector<int> stones, int k) {
    int answer = 0;
    int limt = 1;
   
    int right = 200000000;
    int left= 0;
    int mid = (right+left)/2;
    while(left<=right){
        
        bool fail = false;
        for(int i =0; i<stones.size();i++){
            
            if(stones[i]>=mid){
                limt = 1;
            }
            else if(stones[i]<mid&&k>limt){
                limt++;
            }
            else{
                fail = true;
                break;
            }
        }
        if(fail){
            right=mid-1;
        }
        else{
            left =mid+1;
        }
        limt =1;
        mid = (right+left)/2;
        
    }
    answer = mid;
    return answer;
}

유형님이 추천해줘서 풀게 됐다.
LEVEL3라서 겁 먹었다가 읽어보니 되게 단순해서 쉽게 풀었는데, 효율성 테스트가 계속 0이 나왔다.. LEVEL3인 이유는 효율성 문제 때문이었나보다. 계속 고민하다가 조금 힌트를 얻고자 질문하기를 봤고, 이분탐색을 이용해야한다는 것을 알았다. 왜 추천해줬는지도 이때 알았다.
이분탐색을 이용해 코드 짜는 건 금방 했는데, 이전에 풀었던 코드에서 계속 stones vector를 조작하는 방식으로 코드를 짜놨어서 그것때문에 오답이 나왔다.
또 처음에 right값을 뭘로 설정해야할지 헤메다가 그냥 큰 수 때려박아서 풀었었는데, 다시 보니 문제에 요소 하나의 최댓값이 주어져 있었다.

- 결론

어떤 조건의 최댓값, 최솟값을 결정할 때는 이분탐색이 방법이 될 수 있다.
조건문을 반복하며 배열을 다룰 때에는 그 과정에서 배열이 조작되는지, 그게 결과에 영향을 끼치는지 확인하기.