[Programmers] [C++] 주식가격 / 이진 변환 반복하기

 

<문제 설명>
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때,
가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

<제한사항>
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

<입출력 예>
prices		return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

<입출력 예 설명>
1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

---

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int count = 0;
    
    for (int i = 0; i < prices.size(); i++) {
        for (int j = i+1; j < prices.size(); j++) {
            ++count;
            
            if (prices[i] > prices[j]) {
                break;
            }
        }
        answer.push_back(count);
        count = 0;
    }
    
    return answer;
}

 

의외로 이중 for문으로도 풀렸다...?!

count를 전위연산자로 한 이유는, 전위연산자가 후위연산자 보다 빠르기 때문이다.

 

++전위연산자: 객체를 반환함

후위연산자++: 값을 반환함

효율성 테스트도 체점하고 있었기에 연산자까지 고려해보았다..

 

---

 

<문제 설명>
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

x의 모든 0을 제거합니다.
x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면,
x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다.
s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때,
이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아
return 하도록 solution 함수를 완성해주세요.

<제한사항>
s의 길이는 1 이상 150,000 이하입니다.
s에는 '1'이 최소 하나 이상 포함되어 있습니다.

<입출력 예>
s		result
"110010101001"	[3,8]
"01110"		[3,3]
"1111111"	[4,1]

<입출력 예 설명>
- 입출력 예 #1

"110010101001"이 "1"이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.
회차	이진 변환 이전	제거할 0의 개수	0 제거 후 길이	이진 변환 결과
1	"110010101001"	6		6		"110"
2	"110"		1		2		"10"
3	"10"		1		1		"1"
3번의 이진 변환을 하는 동안 8개의 0을 제거했으므로, [3,8]을 return 해야 합니다.

- 입출력 예 #2

"01110"이 "1"이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.
회차	이진 변환 이전	제거할 0의 개수	0 제거 후 길이	이진 변환 결과
1	"01110"		2		3		"11"
2	"11"		0		2		"10"
3	"10"		1		1		"1"
3번의 이진 변환을 하는 동안 3개의 0을 제거했으므로, [3,3]을 return 해야 합니다.

- 입출력 예 #3

"1111111"이 "1"이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.
회차	이진 변환 이전	제거할 0의 개수	0 제거 후 길이	이진 변환 결과
1	"1111111"	0		7		"111"
2	"111"		0		3		"11"
3	"11"		0		2		"10"
4	"10"		1		1		"1"
4번의 이진 변환을 하는 동안 1개의 0을 제거했으므로, [4,1]을 return 해야 합니다.

---

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    int count = 0;       //몇 번 제거?
    int remove = 0;      //제거한 0의 개수
    
    while (s.length() > 1) {   
        int length = 0;  //0 제거 후 길이
        ++count;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '0') { ++remove; }
            else { ++length; }
        }
        
        s = "";
        
        while (length > 0) {
            s += (length % 2 == 0) ? "0" : "1";
            length /= 2;
        }
    }
    
    answer.push_back(count);
    answer.push_back(remove);
    
    return answer;
}

 

두번째 while문처럼 삼항연산자에 결과를 더할 수 있음을 잊지 말자!!

s += (length % 2 == 0) ? "0" : "1"; 과

s += (length % 2 == 1) ? "1" : "0"; 의 차이는 결과값도 논리적으로 다르지 않다. +=를 함으로써 문자열 뒤에 계속해서 숫자가 붙여지기 때문이다. 풀면서 숫자가 앞에 붙는건지 뒤에 붙는건지 잠시 헷갈렸다...