23.09.14. 풀었던 문제들
프로그래머스 Lv. 2 최댓값과 최솟값, 4분 30초
c++에서 delimiter를 사용해 string을 파싱할 줄 알면 바로 풀리는 문제. iss 쓰고 while getline으로 풀면 된다!
string solution(string s) {
int min_v = INT_MAX;
int max_v = INT_MIN;
istringstream iss(s);
string buffer;
while(getline(iss, buffer, ' ')){
int v;
if(buffer[0] == '-'){
v = stoi(buffer.substr(1));
v *= -1;
}
else{
v = stoi(buffer);
}
min_v = min(min_v, v);
max_v = max(max_v, v);
}
return to_string(min_v) + " " + to_string(max_v);
}
시간복잡도
s를 파싱하고 최대/최소값을 갱신하는 데 O(n)이 걸린다.
프로그래머스 Lv. 2 최솟값 만들기, 1분 40초
수학 규칙을 알면 되는 문제. A는 오름차순, B는 내림차순으로 정렬한 후 곱한 것을 더한 것이 답이다.
int solution(vector<int> A, vector<int> B)
{
sort(A.begin(), A.end(), less<int>());
sort(B.begin(), B.end(), greater<int>());
int answer = 0, len = A.size();
for(int i = 0; i<len; i++){
answer += A[i] * B[i];
}
return answer;
}
시간복잡도
정렬에 O(nlogn), 순회에 O(n)
프로그래머스 Lv. 2 올바른 괄호, 2분
stack 쓰면 매우 쉽게 풀리는 문제. 사실상 예제문제다. 이런 건 1레벨로 낮춰줬으면.
bool solution(string s)
{
stack<char> stk;
for(char c : s){
if(c == ')'){
if(stk.empty() || stk.top() != '(') return false;
stk.pop();
}
else if(c == '('){
stk.push('(');
}
}
return stk.empty();
}
시간복잡도
순회에 O(n)
프로그래머스 Lv. 2 이진 변환 반복하기, 6분 40초
주어진 대로 변환하면 되는 문제. 뭐.. 10진수를 n진수로 변환할 때 % 이후 /를 한다는 것만 기억하면 된다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int num_removed_zeros = 0;
int num_binary_translation = 0;
string removeZero(string x){
int total = (int) x.length();
string result = "";
for(char c : x){
if(c == '1') result += "1";
}
int num_ones = result.length();
num_removed_zeros += total - num_ones;
return result;
}
string decimalToBinary(int x){
num_binary_translation++;
string result = "";
while(x){
result += to_string(x % 2);
x /= 2;
}
reverse(result.begin(), result.end());
return result;
}
vector<int> solution(string s) {
while(s != "1"){
int len = (int) removeZero(s).length();
s = decimalToBinary(len);
}
return {num_binary_translation, num_removed_zeros};
}
프로그래머스 Lv. 3 숫자의 표현, 13분
첫 접근
아래 느낌으로 nested loop로 돌렸다. n이 1만이니.. 그러나 당연히 TLE. 다른 방법이 필요했다.
vector<int> dp(10001, 0); // dp[i] : 연속된 자연수로 i를 표현하는 방법의 개수
int INF = 10001;
int solution(int n) {
for(int i = 1; i<=n; i++){
for(int len = 1;)
for(int j = i; j<=5000; j++){
int sum = (j - i + 1) * (i + j) / 2;
if(sum >= INF) continue;
dp[sum]++;
}
}
return dp[n];
}
두 번째 접근
sliding window가 딱 생각이 났다. sum을 계산하고, 작으면 e를 늘이고, 크면 s를 늘이는 방식으로.
int getSum(int s, int e){
return (e - s + 1) * (s + e) / 2;
}
int solution(int n) {
// dp 실패했으니 sliding window로 해 볼까? two pointer로.
int s = 1, e = 1, answer = 0;
while(s <= n){
if(s > e){
e = s;
continue;
}
int sum = getSum(s, e);
if(sum == n){
answer++;
s++;
continue;
}
if(sum < n) e++;
else if(sum > n) s++;
}
return answer;
}
시간복잡도
s의 sliding에 O(n)이, e의 sliding에 O(n)이 걸린다.
프로그래머스 Lv. 3 숫자 게임, 17분 40초
greedy 문제이다. 일단, 기본 전제: 이길 수 있으면 이기되 최대한 작은 수로 이기고, 지는 경우에는 최대한 작은 수로 져야 한다.
첫 접근
최대한 작은 수로 이긴다 -> binary search, 특히 upper bound로 풀었다. 처음에 놓친 점은, multiset을 하지 않은 것.
int solution(vector<int> A, vector<int> B) {
multiset<int> s(B.begin(), B.end());
int answer = 0;
set<int>::iterator iter;
for(int point : A){
iter = upper_bound(s.begin(), s.end(), point);
if(iter == s.end()){ // point보다 큰 것이 없는 경우
s.erase(s.begin());
}
else{ // 존재 : point보다 큰 것중 제일 작은 것
s.erase(iter);
answer++;
}
}
return answer;
}
그러나 TLE가 난다! input size가 10만이고, set의 연산은 O(logn)이므로 O(nlogn)으로 풀릴 줄 알았는데, set 연산이 생각보다 느린갑다.
두 번째 접근
그래서 A는 내림차순으로, B는 오름차순으로 정렬한 후 B가 이기지 못하는 경우라면 B의 제일 작은 점수를 희생시키고, 이길 수 있으면 이기는 방식으로 선택했다.
int solution(vector<int> A, vector<int> B) {
sort(A.begin(), A.end(), greater<int>());
sort(B.begin(), B.end(), less<int>()); // 오름차
int start = 0, end = B.size()-1;
int answer = 0;
for(int point : A){
if(point >= B[end]){ // B가 못이기는 경우
start++;
}
else{
end--;
answer++;
}
}
return answer;
}
시간복잡도
정렬에 O(nlogg), 순회에 O(n)이므로 O(nlogn)이다.
후기
왜 set으로는 안풀릴까.
프로그래머스 Lv. 3 기지국 설치, 27분
전파가 닿지 않는 부분을 알면, w의 /와 % 연산을 이용해서 쉽게 답을 낼 수 있다.
그러면 전파가 닿지 않는 부분을 알아야 하는데,
- 전파가 닿는 구간을 찾음
- 전체에서 위 구간을 뺌
위 방식으로 구현했다.
N이 작으면 bitmap 형식으로 풀어도 되는데, 2억이므로 시간 내에 풀 수 없다. 따라서 [시작 좌표, 끝 좌표]로 어떻게든 풀어야 한다.
- 전파가 닿는 구간 찾기
- 겹치는 부분만 잘 처리해 주면 된다.
- 전파가 닿지 않는 구간 찾기
- 전체에서 전파가 닿는 구간을 빼면 된다.
typedef pair<int, int> pii; // .first : 시작 지점, .second : 끝 지점. (included)
int solution(int n, vector<int> stations, int w)
{
int s = stations[0] - w, e = stations[0] + w;
s = max(s, 1); e = min(e, n);
pii p = {s, e};
vector<pii> overlaps(1, p);
// 겹쳐 있는 구간을 찾을 것임.
for(int station : stations){
s = station - w, e = station + w;
s = max(s, 1); e = min(e, n);
int prev_e = overlaps.back().second;
if(prev_e + 1 < s){ // 아예 새로운 구간이 시작되는 경우
overlaps.push_back({s, e});
}
else{ // 이어지거나, 겹치는 경우
overlaps.back().second = e;
}
}
overlaps.push_back({n+1, n+1});
// overlapping 결과 테스트
// for(pii p : overlaps){
// cout<<p.first<<", "<<p.second<<endl;
// }
// sum of ceil(겹쳐 있지 않은 구간 / w)가 답.
int answer = 0;
s = 1;
w = 2 * w + 1;
for(pii overlap : overlaps){
e = overlap.first - 1;
answer += (e - s + 1) / w;
answer += ((e - s + 1) % w != 0);
s = overlap.second + 1;
}
return answer;
}
/*
비어있는 공간만 찾으면 됨. 구현 문제 같음.
stations들이 겹쳐 있는 구간을 찾는 문제로 바꾸면 쉬울 것 같은데?
*/
시간복잡도
overlaps를 만드는 데 O(n), 이후 overlaps를 순회할 때 O(n)이므로 O(n)이다.
후기
이 문제는 구현에서 조금 절었다. 실수한 점은, 첫 값을 넣을 때도 s와 e가 [1, n] 사이에 있게 filtering 했어야 했는데 그러지 않아서 문제가 생겼다.