JArchive 프로그래밍 일기

문제

더 맵게 프로그래머스 level2

리뷰

힙 카테고리에 있는 문제다.

처음에는 내림차순으로 정렬 후, 뒤에서 첫번째, 두번째 숫자들을 pop_back, 새로 계산한 숫자를 push_back 해서 해결하려고 했었다.

하지만 자꾸 (비용이 큰 함수) sort()를 해야 해서 "실패" 떴다. 그리고 벡터 크기가 2 이상인지도 체크도 안해줬다...

실패한 코드

#include <functional> 

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int last = scoville.size()-1;

    while(scoville[last] >= K){

        sort(scoville.begin(), scoville.end(), greater<int>()); // 내림차순 
        last = scoville.size()-1;
        int new = scoville[last-1]*2 + scoville[last];
        scoville.pop_back();
        scoville.push_back(new);

        answer++;
    }

    return answer;
}

힙 을 사용해서 바꿨다.

priority_queue<int, vector<int>, less<int> > pq; // 오름차순
priority_queue<int, vector<int>, greater<int> > pq; // 내림차순

내림차순으로 정렬한 우선순위 큐를 선언하고, 벡터의 원소를 모두 넣는다.

맨 위에는 가장 작은 값이 오니까 2개 꺼내서 새 값을 계산해서 다시 푸시한다.

이 때, 2개를 꺼내야 하니까, 큐의 사이즈가 1인지 확인하여 예외처리를 해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int> > pq;
    int answer = 0;

    for(int i=0; i <scoville.size(); i++){ // 벡터 원소를 모두 큐에 넣는다 
        pq.push(scoville[i]);
    }

    while(pq.top() < K){

        if(pq.size() < 2){
            answer = -1; break;    
        } 

        int top = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();

        pq.push(second*2 + top);
        answer++;
    }

    return answer;
}

문제

전화번호 목록 프로그래머스 level2

리뷰

해시 카테고리에 있는 문제다.

입력이 [12,123,1235,567,88] 로 주어졌을 때, 12 가 123의 접두어가 된다. 그래서 답이 false가 나와야 한다.

따라서 12를 타겟으로 두고, 나머지 문자열을 검사한다.

나머지 문자열이 12를 가지고 있는 시작 인덱스가 0인지 확인하면 된다.

// 12 : first,  123 : second 문자열인 경우, 

int loc = second.find(first);
if(loc == 0 ) answer = false; break; 

코드

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

bool solution(vector<string> phone_book) {
    bool answer = true;
    int pb_size = phone_book.size();

    sort(phone_book.begin(), phone_book.end());

    for(int i = 0; i < pb_size; i++){
        for(int j = i+1; j < pb_size; j++){

            string first = phone_book[i];
            string second = phone_book[j];

            int loc = second.find(first);
            if(loc == 0 ) answer = false; break;
        }    
    }

    return answer;
}

문제

주식가격 프로그래머스 level2

리뷰

이중 for문 으로 해도 풀린다.

자신보다 큰 수가 몇 개인지 개수를 세는 것이다.

코드 1

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;

    for(int i = 0; i < prices.size(); i++){

        int cnt = 0;
        for(int j = i+1; j <prices.size(); j++){
            if(prices[i] <= prices[j]) cnt++;
            else{
                cnt++;
                break;
            }
        }
        answer.push_back(cnt); 
    }

    return answer;
}

리뷰

스택/큐 카테고리에 들어가 있으니 스택을 이용한 풀이를 찾아봤다.
스택에 인덱스를 넣는 방법이다.

prices 가 [ 1, 2, 3, 2, 3 ] 으로 주어졌을 때,
값이 계속 오르는 1, 2, 3 구간은 스택에 0 1 2 로 저장된다. 이 순간 스택의 top 은 2 라는 인덱스가 저장되어 있는 것이다.

prices[4] 는 2라는 값을 가진다.
이 때, prices[st.top()] 과 2값을 비교하면, 3 > 2 가 된다.
가격이 전보다 떨어진 것이다.
이 때, st.top()과 현재 인덱스 i 와의 차이로 answer의 값을 정해준다. 그리고 스택에서 pop 해준다.

주식 가격이 전보다 떨어지는 경우 말고는 현재 인덱스가 스택에 푸시되었을 것이다.

인덱스가 0부터 시작 됨을 감안하여 스택이 빌 때까지 꺼낸다.

코드 2

#include <stack>
#include <vector>
using namespace std;

vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st; // 인덱스를 저장하는 스택 

    for(int i = 0; i < size; i++){ 

        // 스택이 비어있지 않고, 스택 top 인덱스의 값이 현재값보다 크다면, pop 
        while(!st.empty() && prices[st.top()] > prices[i]){
            // 가격이 이전보다 떨어졌을 떄 처리 
            answer[st.top()] = i-st.top();
            st.pop(); 
        }
        st.push(i); // 현재 인덱스를 푸시 
    }

    // 인덱스는 0으로 시작함을 감안하여 size-1 에서 st.top()을 빼준다
    while(!st.empty()){ 
        answer[st.top()] = size-st.top()-1;
        st.pop();
    }

    return answer;
}

콜라츠 추측 

프로그래머스 level 1 문제 

리뷰 

문제에 테스트 케이스 3개가 나와있는데, 626331 이 제대로 답이 안나왔었다. 

이상해서 계산과정 while 문 내부를 출력해보니까,

홀수 가 된 경우에 * 3 하는 과정에서 int 표현 범위를 넘어가서 음수로 표현되고 난리가 났었다. 

long long 으로 변환하고 나서 실행해보니 626331 의 답이 -1로 잘 나왔다.

근데, 답을 제출했더니 테스트 케이스 1개가 틀렸다. 이유는 1때문이었다. 

solution 함수에 입력이 1로 들어왔을 때는, 연산할 필요가 아예 없으니 처음부터 예외처리가 필요하다고 했다. 

코드 

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    
	int answer = 0;
    int limit = 500;
    long long temp = num; // 자료형 변환 
    
    if(num == 1) return 0; // 1은 연산 필요 없다
    
    while(limit--){
      
      if(temp % 2 == 0){
        temp /= 2;

      }else{
      	temp = (temp * 3) + 1;
      }

      answer++;
      limit--;

      if(temp == 1) break;
	}

    return temp != 1 ? -1 : answer;

}

문제

하샤드 수

프로그래머스 level 1

문제 설명

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.

제한 조건

• x는 1 이상, 10000 이하인 정수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
10의 모든 자릿수의 합은 1입니다. 10은 1로 나누어 떨어지므로 10은 하샤드 수입니다.

입출력 예 #2
12의 모든 자릿수의 합은 3입니다. 12는 3으로 나누어 떨어지므로 12는 하샤드 수입니다.

입출력 예 #3
11의 모든 자릿수의 합은 2입니다. 11은 2로 나누어 떨어지지 않으므로 11는 하샤드 수가 아닙니다.

입출력 예 #4
13의 모든 자릿수의 합은 4입니다. 13은 4로 나누어 떨어지지 않으므로 13은 하샤드 수가 아닙니다.

코드

#include <string>
#include <vector>

using namespace std;


bool solution(int x) {
    bool answer = true;
    int sum = 0;
    int x_old = x;

    while(x>0){
        sum += (x % 10);
        x = x / 10;
    }

    if(x_old % sum != 0){
        answer = false;
    }

    return answer;
}

문제

핸드폰 번호 가리기 문제링크

프로그래머스 level 1

프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다.
전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자를 전부 *으로 가린 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건

• s는 길이 4 이상, 20이하인 문자열입니다.

입출력 예

리뷰

뒤에서 4번째까지만 string을 *로 바꾸면 되는 문제였다.

코드

#include <string>
#include <vector>

using namespace std;

string solution(string phone_number) {
    string answer = "";
    int i = 0; 

    for(i=0; i<phone_number.size()-4; i++){
        phone_number[i] = '*';
    }

    answer = phone_number;

    return answer;
}

문제

이상한 문자 만들기

프로그래머스 level 1

문제 설명

문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요.

제한 사항

• 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다.
• 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다.

입출력 예

입출력 예 설명

try hello world는 세 단어 try, hello, world로 구성되어 있습니다. 각 단어의 짝수번째 문자를 대문자로, 홀수번째 문자를 소문자로 바꾸면 TrY, HeLlO, WoRlD입니다. 따라서 TrY HeLlO WoRlD 를 리턴합니다.

리뷰

처음에 문제를 잘못 읽어서 완전히 틀렸었다. 문제를 똑바로 읽자...

코드

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

string solution(string s) {

    string answer = "";
     int i = 0;
     bool start_flag = 1;

     while(i != s.size()){

         if(s[i] == ' '){ // 공백 
             answer += s[i];
             start_flag = 1;
        }else{

            if(start_flag == 1){ // 첫 문자는 무조건 짝수번째
                answer += toupper(s[i]); 
                start_flag = 0; // 플래그 갱신
            }else{ // 홀수번째
                answer += tolower(s[i]); 
                start_flag = 1; // 플래그 갱신 
            }
        }
        i++;

    }

    return answer;
}