[백준] 2374 같은 수로 만들기 c++ 구현

 

목차

 

 

 

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

2374번: 같은 수로 만들기

문제

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

 

 

 

 

 

문제 구현 방향

c++에 있는 스택 라이브러리를 이용하여 가독성 있게 구현 해 보았다.

 

 

 

 

문제 풀이 시 주의점

나는 처음에 연결리스트로 되지 않을 까 하는 생각에 연결리스트의 중복을 제거한 뒤
가장 작은 값을 증가시킨 후 종료 조건을 검사하는 식의 로직을 짯다 하지만 이 방식은
이중 순회를 하기 때문에 빅오가 n^2이 나와 시간 초과가 난다..
 
아래는 잘못된 풀이법이다.

#include <list>  
#include <algorithm>
#include <iostream>
using namespace std;
// => 빅오때문에 해결x
int main() {
	list<long long int> numberList;
	for (i = 0; i < num; i++) {   
		cin >> n;
		numberList.push_back(n);
	}
	while (numberList.size() != 1) {
		numberList.unique(); //원본 배열에서 연속된 수 제거
		auto minIterator = min_element(numberList.begin(), numberList.end());
		data = *minIterator+1;
		count++;
		
		numberList.insert(minIterator, data);
		numberList.erase(minIterator);
	}
	cout << count-1;





}

 

 

 

 

 

문제 풀이

설명하기 전에 몇가지 예를 들겠다.
예시:10, 8, 8
여기서 8이 증가하면 옆에 있는 수도 증가하기 때문에 10 8로 봐도 무방하다.
 
예시: 10, 8, 5, 12, 3
10 8 5 | 12 3 -> 나누어진 것을 기준으로 가장 큰 수의 오른쪽 수들은 결국 가장 큰 수를 따라간다.
 

구성

tack<pair<long long int, long long int>> numberStack => 쌍으로 입력 받음
head => 가장 큰 수를 저장
count => 각 수의 더할 수를 저장
sumcount => 최종 더한 수
 

설명

예시: 10 8 7 8 2 11 3 3 => 18
10(0)
count =0          head = 10 
 
10(0) 8(2)
count = 10-8 = 2      head = 10 
 
10(0) 8(2) 7(1)
count = 8-7 = 1      head = 10
 
10(0) 8(2) 7(1) 8(0)    head = 10
스택 top보다 큰 수가 들어오고 head보다는 작은 수 일때
0으로 추가해야함 => 왼쪽 8, 7의 증가 합산을 결국 따르기 때문이다.
 
10(0) 8(2) 7(1) 8(0) 2(6)   
count = 8-2 = 6   head = 10
 
10(0) 8(2) 7(1) 8(0) 2(6) 11(1)   head = 11
스택 top보다 큰 수가 들어오고 head보다는 큰 수 일때
head값 갱신을 해준다.
11은 1로 추가해주었는데 그 이유는 왼쪽의 수들은 이제 11로 가기때문이다.
count = 11-10 = 1
 
10(0) 8(2) 7(1) 8(0) 2(6) 11(1) 3(8)
count = 11-3 = 8      head = 11
 
10(0) 8(2) 7(1) 8(0) 2(6) 11(1) 3(8) 3
마지막 3은 옆 값과 같기 때문에 추가하지 않음
 
=> 0+2+1+0+6+1+8 = 18

 코드 구현

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


int main() {
	ios::sync_with_stdio(0);  //C 표준 입출력의 동기화를 끄는 코드로 C++에서 입출력 속도를 높이기 위함.
	cin.tie(0);
	cout.tie(0);
	stack<pair<long long int, long long int>> numberStack;  
	long long int num, n, i=0, count =0, sumcount=0;
	long long int head;
    
	cin >> num;
	for (i = 0; i < num; i++) {
		cin >> n;
		if (numberStack.empty()) {  //처음이므로 값 그냥 추가
			numberStack.push({ n, 0 });
			head = n;    //가장 큰수 = 처음 수
		}
		else {
			if (numberStack.top().first< n) {  // top보다 큰 수가 들어올 경우
				if (head <= n) {      // 가장 큰 수인 head보다 n이 클 경우 head 초기화 
					count = n - head;    
					head = n;
					numberStack.push({ n, count });      //값과 n-head를 추가 
				}
				else {
					numberStack.push({ n, 0 });   //가장 큰 수인 head보다 n이 작을 경우 값과 0으로 추가
				}

			}
			else if(numberStack.top().first == n){   //같은 수가 들어올 때는 추가 x
				;
			}
			else {    // top보다 작은 수가 들어올 경우 값과 top- n 추가
				count = numberStack.top().first - n;
				numberStack.push({n, count});
			}
			
		}
		
	}
	while (numberStack.empty() == false) {   //모든 값의 차이 반환한 후 더해줌
		sumcount  += numberStack.top().second;
		numberStack.pop();
	}

	cout << sumcount;  
	

	


}

 
푸는데 안풀려서 오기가 생겨서 풀었는데 안풀린다면 깔끔하게 포기하고
다른 공부해서 시간을 효율적으로 쓰는 게 맞는 것 같다..