youngmin.log

• [ 장르 ] Heap 또는 Priority_queue
• [ 문제 ]

• Code 1 ( 힙 을 구현한 ver. )

#include <iostream>
#include <vector>

using namespace std;
vector<int> arr;
int n = 0;

void downHeap(int idx)
{
	int greater, tmp;
	if (idx * 2 <= arr.size()-1)
	{
		greater = idx * 2;
		if (idx * 2 + 1 <= arr.size()-1)
			if (arr[greater] < arr[idx * 2 + 1])
				greater = idx * 2 + 1;
		if (arr[greater] > arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;
			downHeap(greater);
		}
	}
}
void upHeap(int idx)
{
	int max;
	if (idx / 2 >= 1)
	{
		if (arr[idx] > arr[idx / 2])
		{
			max = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = max;
			upHeap(idx / 2);
		}
	}
}
void InsertItem(int data)
{
	arr.push_back(data);
	upHeap(arr.size()-1);
	//n = n + 1;
}
int removeMax()
{
	if (arr.size() >= 2)
	{
		int rootValue = arr[1];

		arr[1] = arr.back();
		arr.pop_back();
		downHeap(1);
		//n = n - 1;

		return rootValue;
	}
}

int main()
{
  	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);	// ★ C++의 입출력속도개선의 매우중요
	int opcnt,X;
	arr.push_back(0);
	cin >> opcnt;
	for (int i = 0; i < opcnt; i++)
	{
		cin >> X;
		if (X == 0)
		{
			if (arr.size() == 1)
				cout << 0 << '\n';	// ★ 개행도 endl이 아닌 '\n'을 쓸 것
			else
				cout << removeMax() << '\n';
		}
		else
			InsertItem(X);
	}
	return 0;
}

• Code 2 ( Priority_queue를 활용한 ver. ( 정확히는 힙은 아닌 것 같다. )

#include <iostream>
#include <queue>

using namespace std;
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	priority_queue<int> q;		// 우선순위 큐 ( FIFO,First In First Out )
	int opcnt,X;

	cin >> opcnt;
	for (int i = 0; i < opcnt; i++)
	{
		cin >> X;
		if (X == 0)
		{
			if (q.empty())
				cout << 0 << '\n';
			else
			{
				cout << q.top() << '\n';	// 우선순위 큐의 front 요소출력
				q.pop();	// front요소 pop
			}
		}
		else
			q.push(X);	// 우선순위 큐는 push하면서 자동으로 front에서부터 내림차순정렬
	}
	return 0;
}

[ CheckPoint ]

• 문제는 간단하다고 생각했으나 풀면서, 생각보다 몰랐던 부분, 생각해야 할 부분이 많았던 문제였다.
• 먼저, 최근에 나는 Heap에 대한 이론을 깨우쳐서 이 문제를 처음에는 힙을 만드는 과정의 삽입,삭제를 일일히 구현해서 메인에서 사용했다.
• 근데 생각해보니, 이 문제만 봤을 떈, 결국 삽입시에는 상관없고, 삭제하면서 출력시에 최대 값만 출력하면 되는 문제였다보니, 꼭 힙을 써야할까 ?
  생각이 들었다. 결론은 그러지 않아도 된다 !
• C++로 알고리즘 풀면서 이번에 queue container에 priority_queue를 쓰면
  매우 유용한 부분이 또 있다는 것을 알았다.
• 이는, queue와 기본적으로 FIFO형태라 보면 되는데, 특이점은 요소를 삽입시, default옵션이 자동으로 내림차순으로 PQ안에 요소들이 정렬된다는 것!
  문제에선 삭제시, 배열 내에 최대값을 삭제하면서 출력하는 것이 었으니
  queue.top( )을 통해서 큐에 front에 요소를 top( )하고, 후에 pop( )을하면 간단했다.
• 그리고, 무엇보다 이번에 가장 중요한 포인트는, 입출력과 관련된 시간이었다. 로직은 분명히 맞다. 맞는데. 이상하게 계속 시간초과가 뜬다. 이래저래 수를 써봤는데 변화가 없었다. 그러던 차에 구글링을 했더니 중요한 사항을 발견했다.

1. 글의 내용에서, C++기준으로 정리를 하자면, 입출력을 할때, 조금이라도 더 빠른 실행시간이 필요하다면, C++의 입출력인 cin,cout에 대해서
   cin.tie(NULL) , cout.tie(NULL) , ios_base::sync_with_stdio(false) 를 메인 문두에 선언
2. C++에서 개행 시에도 endl보다 '\n'을 사용하는 것이 속도적인 면에도 좋다.

그 외 백준알고리즘문제를 풀면서 참고해야 BOJ(Baekjoon) 참고사항 링크를 아래에 걸어둔다.
https://www.acmicpc.net/blog/view/55

• [ 장르 ] 스택

• Code 1 ( 입력 문자열 기능비교시 string.compare(string) 사용한 경우 ) 

// string.compare(string) 사용한 경우
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
	int cnt,data;
	stack<int> s;
	string str;
	//char str[5];
	cin >> cnt;
	
	for (int i = 0; i < cnt; i++)
	{
		cin >> str;
		//scanf("%s", str);
		if (str.compare("push") == 0)
		{
			cin >> data;
			s.push(data);
		}
		else if (str.compare("pop") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
			{
				cout << s.top() << endl;
				s.pop();
			}
		}
		else if (str.compare("top") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
				cout << s.top() << endl;
		}
		else if (str.compare("size") == 0)
			cout << s.size() << endl;
		else
		{
			if (s.empty())
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	
	}
}

• Code 2 ( 입력 문자열 기능비교시 strcmp(string1,string2) 사용한 경우 )

// strcmp(string,string) 사용한 경우
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main()
{
	int cnt, data;
	stack<int> s;
	//string str;
	char str[5];
	cin >> cnt;

	for (int i = 0; i < cnt; i++)
	{
		//cin >> str;
		scanf("%s", str);
		if (strcmp(str,"push") == 0)
		{
			cin >> data;
			s.push(data);
		}
		else if (strcmp(str, "pop") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
			{
				cout << s.top() << endl;
				s.pop();
			}
		}
		else if (strcmp(str, "top") == 0)
		{
			if (s.empty())
				cout << -1 << endl;
			else
				cout << s.top() << endl;
		}
		else if (strcmp(str, "size") == 0)
			cout << s.size() << endl;
		else
		{
			if (s.empty())
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	}
}

[ CheckPoint ]

• 일단, 문제는 말 그대로 스택에 기본적인 기능에 대해 구현하는 것이라서 어렵지 않다. 다만 pop이나 top을 할 때 항상 스택이 비어있는데 참조할려고 하지 않는지 empty를 통해서 사전에 방지해야한다.
  그렇지 않으면 런타임 에러가 발생한다.
• 그 외적으로, 문제를 풀면서 알게 된것은, 이 문제에서 스택에 기능을 영어 문자열로 입력을 받는데, 나는 최근까지 C언어를 많이 사용하다보니 문제가 쉬워보인다는 이유로 아무 생각없이 변수를 C++에있는 string변수로 선언하고 입력은 또 scanf( )로 받았다. 거기에 입력받은 문자는 각 "push","pop","top","size" 에 입력받은 문자열을 string container에 내장된 compare( ) 함수로 비교를 할려고 했다.
• 그러다 보니 아무리 제대로 문자열을 입력한 것 같아보여도, 결과적으론 문자열이 입력 받는거까진 좋은데, compare( ) 연산을하는데 이론상은 두 문자열이 같으면 0 을 반환하는 걸 이용해야하는게 그것이 적용이 안되는 것이다. 반대로 strcmp를 이용해 봤는데 이 역시 받아 들이질 않았다.
• 결론적으론, string변수를 쓴건 좋고, 그러면 입력과 출력을 C++의
  cout 와 cin만 이용을하거나, strcmp를 쓰면 char 형태의 배열을 선언해서 scanf printf를 만을 사용해서, scanf,printf 와 cin,cout 간의 두 입출력함수가 동시에 쓰이는 경우를 없애야한다.
• 이유는 혼동 되서 쓰이게 되면 싱크가 맞지 않아서 프로그램안에서 입력 순서가 바뀌는 참사가 발생한다고 한다.
  [ 참고자료 ]
  
  
• 추가적으로 프로그램 성능(실행시간)면에서 봤을 때, scanf,printf보다 cin,cout가 무거운 함수이다. 간단한 이유를 생각해보면, scanf,printf는 안에 형식들이 일일히 정해져서 들어가지만, cin,cout는 그냥 변수명만 넣기 때문에 컴파일러 내부적으로 이게 무슨 자료형이지 ? 등을 생각해야하기 때문에 당연히 속도적으로 느릴 수 밖에 없다.

저의 설명에 잘못됬거나 하는 것이 있다면 의견을 부탁드립니다.

• [ 장르 ] Sort

• Code

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] < i + 1) {
            return i;
        }
    }

    return citations.size();
}

" H-Index 란 무엇인가 ? "

[ CheckPoint ]

• 문제에대한 이해가 왠만한사람은 잘못된 길로 갈 가능성이 큰 문제다.
• [ 3,0,6,1,5 ] 일때 내림차순을 통해 [ 6,5,3,1,0 ] 에서 '3'일때 자기보다 크거나같은 요소는 3개, '3'보다 작은 수는 자기를 제외하고 2개니깐 답이 '3'이 ! 아니라, 이는 표를 통해 확인하자.

총 인용 수 ( 내림차순 )	순위
6	1
5	2
3	3
1	4
0	5

일때, 총 인용 수 < 순위이기 바로 직전 순위가 바로 "H-Index"이다. 애초에 Index하니깐 Index가 답이지 어떤 값이 정답이 되는게 아닌 듯하다.

다른 예로, [ 1,7,0,1,6,4 ] 가 있다 치자.

총 인용 수 ( 내림차순 )	순위
7	1
6	2
4	3
1	4
1	5
0	6

일때, 여기서 H-Index는 '3' 이다.

H-index 정의를 가져오자면, "피 인용수( Citation ) 가 논문의수( Index,No. ) 와 같아지거나 작아지기 시작하는 No.( = Index ) 가 H-Index이다.

이를 의미적으로 접근하면,예로들어 전체 논문의 수가 5편이고, H-Index가 3 이라함은 그 중, "3편의 논문은 3회이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 떄문에 H-Index는 3입니다." 이다.

• [ 장르 ] STACK
• [ 문제 ]

[#42584] 주식가격

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

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int NoDownDuring;		// 해당시점 이후, 주식가격 낮아지기까지 시간체크
    
    answer.assign(prices.size(), 0);		// 주식 수 만큼 정답 벡터 0으로 초기화
    for(int i = 0 ; i < prices.size(); i++)
    {
        NoDownDuring = 0;		// 시간측정은 현 시점부터 0부터 시작
        for(int j = i + 1; j < prices.size(); j++)	
        {
            NoDownDuring++;
            if(prices[i] > prices[j])	// 현 시점 주식에서 뒤에 주식중에 현 시점 주식보다 낮은 시점
                break;
        }
        answer[i] = NoDownDuring;		// 현 시점에서 주식이 낮아지기까지 시간 벡터에 삽입
    }
    return answer;
}

• Another Code

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices)
{
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size();

    for (int i = 0; i<size; i++)
    {
        // 스텍이 차있으면서 가격이 떨어지기 시작하면
        while (!s.empty() && prices[s.top()] > prices[i])
        {
            answer[s.top()] = i - s.top();
            s.pop();
        }

        // 가격이 올라갈때동안 스텍에 넣음
        s.push(i);
    }

    // 스텍에 남은것들을 계산해줌
    while (!s.empty())
    {
        answer[s.top()] = size - s.top() - 1;
        s.pop();
    }

    return answer;
}

[ CheckPoint ]

• 문제 의도만 파악하면, 문제는 어렵지 않은 문제다.
• 주된 장르는 스택인데, 나는 풀고나니 스택을 안았다. 스택을 써야하는 발상이 나지 않았다.
• 풀고나서보니, 최악의 상황 prices 벡터크기가 10000개이고, 모든 주식 가격이 같다면, 총 실행시간은 O(n^2)시간이 될 수 있다. 이는 굉장히 비효율적일 수 있는데, 이 문제는 이 사항은 수용하기로 했나보다.
• 다른 사람의 코드를 보면, 반복문이 2개가지만, 스택을 잘 활용해서 적어도 O(n^2)의 시간은 걸리지 않다는 것을 알 수있다.

• [ 장르 ] Queue
  [ Question ]

[#42583] 다리를 지나가는 트럭

모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0,cur_Weight = 0,truck_Count;
    queue<int> Crossed;		// 지나간 트럭
    queue<int> Passing;		// 다리위에 트럭
    vector<int> waitBridge;	// 다리위 대기중인 각 트럭당 대기시간

    truck_Count = truck_weights.size();	// 초기 트럭수 변수에 저장
    while(true)
    {
        answer++;		// 단계 카운트
        if(!waitBridge.empty())	// 다리위에 트럭이 있으면
            for(auto iter = waitBridge.begin(); iter != waitBridge.end(); iter++)
                *iter -= 1;		// 다리위에 트럭큐에 끝까지 대기시간 -1감소

        while((!waitBridge.empty()) && waitBridge.front() == 0)	// 다리위에 트럭이있고, 다리끝까지 왔다면 ( == 대기시간 다 됬다면 )
        {
            Crossed.push(Passing.front());		// 현재 다리위에 맨 앞에 트럭, 다리를 건넜음큐에 push 
            cur_Weight -= Passing.front();		// 현재 다리위에 중량무게 이제 나갈 트럭무게만큼 차감 업데이트
            Passing.pop();						// 이제서야 다리위에 맨 앞 트럭 pop
            waitBridge.erase(waitBridge.begin());	// 대기시간 벡터도 맨앞에요소 하나삭제
        }
        if(Crossed.size() == truck_Count)	// 초기의 다리건너기전 트럭수랑, 건넌 트럭수 큐의원소의 수가 같으면 탈출
            break;
        if((!truck_weights.empty()) && weight >= cur_Weight + truck_weights.front())	// 매 단계마다, 다리를 건너기 전 트럭이 존재하고, 현재 다리위에 있는 트럭의 무게의 합과 지금 들어갈
        {																				// 트럭의 무게를 합한 것이, 다리의 하중보다 작거나 같다면 
            Passing.push(truck_weights.front());	// 다리위에 트럭추가
            cur_Weight += truck_weights.front();	// 추가된 트럭 무게만큼 총 무게 증가
            truck_weights.erase(truck_weights.begin());	// 다리건너기전 트럭원소는 삭제
            waitBridge.push_back(bridge_length);	// 새로 대기시간 (다리길이만큼) 벡터에 맨뒤에 삽입
        }
    }
    return answer;
}

[ CheckPoint ]

• 문제를 풀다 마주친 첫번째 고민은, 다리위에 적재된 트럭마다 다리길이만큼 대기시간을 가지게되고, 각각 들어온 시점이 다를 수 있는데 이걸 어떻게 컨트롤 해야할까 ?
• 두번째 고민은, 오류에서 발견 됬는데, 다리위에 있던 트럭을 다리를 끝까지 다와서 건너간트럭큐에 push하거나, 다리에 적재되기전에 기존의 트럭 vector에 트럭을 다리위에 적재할때  vector에 트럭이 존재하는지를 먼저 체크를하고 뭔가를 해서 잘못된
  IndexError를 피할 수 있다.

• [ 장르 ] Stack / Queue
• [ Question ]

[#42586] 기능개발

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int CurFrontIndex = 0;	// 현재 제일 앞 우선순위 인덱스
    int releaseCount = 0;	// 현 시점 배포할 작업 수

    while(true)
    {
        while(progresses[CurFrontIndex] < 100)	// 현재 우선순위 인덱스 작업이 100% 될때까지
        {
            for(int i = CurFrontIndex ; i < progresses.size(); i++)	// 모든 작업, 스피드만큼 증가
                progresses[i] += speeds[i];
        }
        
        while(progresses[CurFrontIndex] >= 100 )	// 현재 우선순위 인덱스의 작업이 일단 100%끝난 시점에서 다음 작업으로 넘어가면서 다른 100%끝난 작업이 있는지 전진
        {
            releaseCount++;
            CurFrontIndex++;
            if(CurFrontIndex >= progresses.size())
                break;
        }
        if(releaseCount != 0)	// 한번 순회하면서 100% 완성된 작업 수 카운트를 정답 벡터에 push !
        {
            answer.push_back(releaseCount);
            releaseCount = 0;
        }
        if(CurFrontIndex >= progresses.size())	// 마지막 작업까지 끝나면 탈출
            break;
    }
    return answer;
}

• Better Code

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)		// 반복문 하나로 끝 
    {
        day = (99 - progresses[i]) / speeds[i] + 1;	// 매 작업마다 한 작업당 스피드로 나누면 몇일이 소요할 지 바로 나오겠지

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();		// 이 부분이 포인트라 했다. ++answer.back() ..

        if (max_day < day)
            max_day = day;
    }

    return answer;
}

" 나는 정작 STACK을 잘 구현할려고 한 것인가 ? "

• [ CheckPoint ]

1.  이 문제의 작은 포인트는 작업이 100프로가 되면 작업을 중단하고 배포를 해야 한다는 것. 혹시 본인의 테스트 케이스가 대부분 맞는데 1,2개가 틀린다면 이 부분을 체크 해볼 것.
2. 나의 로직은 맨 앞 작업부터 끝나기까지 맨 끝 작업까지 한번 씩 speed만큼 작업의 진도를 증가 시키는 것인데, 만약 기존 작업량이 모두 낮고
   (10% 미만 ) speed는 각각 전부 1일 경우, 나의 알고리즘은 작업시간이 오래걸릴 것이다.
3. 좀 더 좋은 방법은 Better Code의  한 작업의 단계에서
   (99-현재작업의 량) / 작업의 speed + 1 = 남은 작업 일 수가 측정 됨을 생각하면 연산 한번의 이런 과정이 끝난다.
4. 아직 ++answer.push_back(1)의 의미를 정확히 모르겠는데 이해를 해봐야 겠다. 혹시 먼저 의견을 줄 수 있다면 조언을 주길 바란다.

• [ Question ]

[ Problem ] #42746 가장큰수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

programmers.co.kr

• Version 1 ( 정렬기준을 정확히 설계해놓지 않았을 경우, 볼 필요 X )

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<int> numbers) {
    string answer = "";
    vector<int> Highest_digit;
    vector<int> priority;
    int tmpDigit,tmpNum;
    string str;
    for(int i = 0 ; i < numbers.size(); i++)
    {
        if(numbers[i] / 1000 != 0)
            Highest_digit.push_back(numbers[i] / 1000);
        else if(numbers[i] / 100 != 0)
            Highest_digit.push_back(numbers[i] / 100);
        else if(numbers[i] / 10 != 0)
            Highest_digit.push_back(numbers[i] / 10);
        else
            Highest_digit.push_back(numbers[i]);  
    }
    for(int i = 0 ; i < Highest_digit.size()-1; i++)
    {
        for(int j = 0 ; j < Highest_digit.size()-1 ; j++)
        {
            if(Highest_digit[j] < Highest_digit[j+1])
            {
                tmpDigit = Highest_digit[j];
                Highest_digit[j] = Highest_digit[j+1];
                Highest_digit[j+1] = tmpDigit;
                tmpNum = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = tmpNum;
            }
            else if( Highest_digit[j] == Highest_digit[j+1])
            {
                if(numbers[j] < numbers[j+1] && (numbers[j] / 1000 + numbers[j] / 100 % 10 + numbers[j] / 10 % 10 + numbers[j] % 10)  != (numbers[j+1] / 1000 + numbers[j+1] / 100 % 10 + numbers[j+1] / 10 % 10 + numbers[j+1] % 10) )
                {
                    tmpNum = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = tmpNum;
                }
            }
        }
    }
    for(int i = 0 ; i < numbers.size(); i++)
    {
        str = to_string(numbers[i]);
        answer += str;
    }
    return answer;
}

• 반성하고 다시 짠 코드 ( 정렬 기준을 무엇으로 !! ) 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(string a,string b)
{
    return a + b > b + a;
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> tmp;		// 숫자 벡터 요소들을 문자열로 바꾼 벡터

    for(int i = 0 ; i < numbers.size(); i++)
        tmp.push_back(to_string(numbers[i]));	// to_string()으로 숫자->문자열로
    sort(tmp.begin(),tmp.end(),compare);	// 정렬한다 ( 따로 정의한 compare()함수 기준으로 )
    for(auto i : tmp)	
        answer += i;	// 정답 문자열 변수에 정렬된 문자열벡터요소하나씩 붙이기
    if(answer[0] == '0')	// 모든 수가 "0" 일 경우
        return "0";
    return answer;
}

" 문제를 보고 !!정렬의 기준!! 을 어떻게 설정할지 고민하라. "

• [ CheckPoint ]

1.  to.string( 정수 ) 를 기억하자.
   = 정수를 문자열로 반환해주는 함수 ( #include <string> 필요 )
2. C++반복문은 ( 일반적 반복문, iterator이용, auto방식 3가지 정도는 기억 )
3. 나는 정렬의 기준을 깔끔하게 잡지 못하고, 숫자벡터의 요소들의 최고자리수를 먼저 구해서 정렬시키고, 최고자리수가 같은 경우 원래 숫자벡터끼리 모든 자리수를 구한 값이 같으면 그대로 두는 식....( 내가 설명하고도 뭔소린지 이해 못한다..) (생략)
4.  결론적으로, 숫자벡터를->문자열벡터로 변환한 벡터가지고서 각 원소들끼리 반복하면서 앞뒤 숫자끼리만 바꿔보면서 더 큰 숫자가 만들어지면 Swap하는 식으로 정렬한 다음, 정답 벡터에 넣어주면 끝나는 문제였다.

[ 참고자료 ]

• [ LEVEL 2 ] [ 스택 / 큐 ]
• [ Qusetion ]

[ LEVEL 2 ] [ 스택/큐 ] 프린터

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0,tmp,i,j;
    while(true)
    {
        for(i = 1; i < priorities.size(); i++)	// 첫번째 우선순위기준으로 그 다음인덱스부터 우선순위벡터 끝까지 조사
        {
            if(priorities[0] < priorities[i])	// 첫번째 우선수위보다 더 큰 우선순위있으면
            {
                tmp = priorities[0];	// 첫번째 우선순위 담아두고
                for(j = 0 ; j < priorities.size()-1 ; j++)	// 뒤에 원소를 하나씩 앞으로 댕김
                    priorities[j] = priorities[j+1];
                priorities[j] = tmp;	// 첫번째 우선순위는 벡터 맨 뒤에 위치
                break;
            }
        }
        if(priorities.size() == i)	// 첫 번째 우선순위가 가장 큰 우선순위일 때
        {
            answer++;	// 우선순위벡터에서 pop()개념으로 정답 우선순위 순번 1증가
            for(j = 0 ; j < priorities.size()-1 ; j++)	// q.pop()개념으로 뒤에 원소들 하나씩 댕김
                priorities[j] = priorities[j+1];
            priorities[j] = 0;	// pop()된 우선순위를 0 (의미없는 수)으로 지정
            if(location == 0)	// 중복된 수들이 있었을 때를 고려. 같은 수중에 내가 원한 우선순위를 체크
                break;
        }
        location--;	// 내가 원하는 우선순위 차례 조작
        if(location < 0)	// 맨뒤로 내가 원하는 우선순위가 벡터에 갔을때 
                location = priorities.size() - 1;	// 맨뒤 인덱스로 변경
    }
    return answer;
}

• Best Code

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<int> priorities, int location) {
    queue<int> printer;                         //queue에 index 삽입.
    vector<int> sorted;                         //정렬된 결과 저장용
    for(int i=0; i<priorities.size(); i++) {
        printer.push(i);
    }
    while(!printer.empty()) {
        int now_index = printer.front();
        printer.pop();
        if(priorities[now_index] != *max_element(priorities.begin(),priorities.end())) {
            //아닌경우 push
            printer.push(now_index);
        } else {
            //맞는경우
            sorted.push_back(now_index);
            priorities[now_index] = 0;
        }
    }
    for(int i=0; i<sorted.size(); i++) {
        if(sorted[i] == location) return i+1;
    }
}

" C++의 큐(Queue) STL 사용에 익숙해지자 "

• [ CheckPoint ]

1.  우선 <queue> STL은 <algorithm> 헤더가 필요하다.
2.  queue는 정렬이 따로 없다.
3.  사용가능한 주 함수로는 다음이 있다.

1.  문제에서 큐에서 최대값을 순회하면서 구하는 방법을 몰랐다.
2.  *max_element OR *min_element ( 객체.begin() , 객체.endl() )
   를 기억하자.
3. 함수는, 배열이나 벡터 큐 등등 (문자열도 됨) 에서 시작과 끝 사이에서 각각 최대값, 최소값을 반환한다.
   다만 값이 아닌 주소를 반환하기 때문에 함수앞에 참조연산자를 붙인다.

• [ 문제 ]

#비밀지도

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

programmers.co.kr

•  My Code

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;

    string binary1 = "";
    string binary2 = "";
    string sum = "";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr1[i] % 2 == 0)
            {
                binary1.push_back(' ');
                arr1[i] /= 2;
            }
            else
            {
                binary1.push_back('#');
                arr1[i] /= 2;
            }
            if (arr2[i] % 2 == 0)
            {
                binary2.push_back(' ');
                arr2[i] /= 2;

            }
            else
            {
                binary2.push_back('#');
                arr2[i] /= 2;
            }
        }
        for (int j = n - 1; j >= 0; j--)
        {
            if (binary1[j] == '#' || binary2[j] == '#')
                sum.push_back('#');
            else
                sum.push_back(' ');
        }
        answer.push_back(sum);
        sum.clear();
        binary1.clear();
        binary2.clear();
    }
    return answer;
}

•  Best Code

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;
    for(int i=0; i <n; i++){
        arr1[i] = arr1[i]|arr2[i];
        string ans = "";
        for(int j = 0; j<n; j++){
            if(arr1[i] % 2 == 0) ans = " " + ans;
            else ans = "#" + ans;
            arr1[i] = arr1[i] >> 1;
        }
        answer.push_back(ans);
    }
    return answer;
}

" 비트 연산자를 사용할 생각을 하였는가 !! "

• CheckPoint

1.  나는 2개의 숫자 배열에 대한 각각의 " "(0) , "#"(1) 로 전환된 이진수 문자열 배열을 만들기 위해서 따로 문자열 변수를 선언 후
2. N 번 진행하면서 매번 만들어진 두 문자열끼리 원소를 조건문을 통해서 연산을 통해 answer 문자열 벡터에 연산을 통해 만들어진 이진수문자열을 삽입하고 마지막 answer 문자열 벡터를 반환하는 식으로 작성했다.
3. 문제는 이렇게 풀어보니, 정수를 이진수를 의미하는 ' ', '#' 문자열로 만드는 과정에서 push_back 함수 가지고서만 해결하다보니 문자열이 뒤집어 지는 것도 생각을 해줘야해서 마지막에 두 이진수 문자열 간에 연산할 때
   두 문자열을 문자열 마지막부터 앞으로 후진하면서 문자간 연산한 것을
   정답 문자열 벡터에 넣어줘야했다.
   ( 이는 이진수를 -> 십진수로 전환하는데에는 내가 얻어낸 문자열이랑은 연산이 반대이니깐! )
4.  끝내 결론은 무엇인가 ! 바로 "비트연산자" 를 생각해봐야 한다.
5. [ 비트연산자 ]
   = 정수나 문자 등을 2진수로 변환한 후에 각 자리의 비트끼리 연산을 수행한다. 

 

• Qusetion

프로그래머스 #12943

콜라츠 추측 : 1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

programmers.co.kr

• My Code

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    int answer = 0;
    long long n = num;
    for(int i = 0 ; i < 500; i++)
    {
        if(n == 1)
            break;
        if(n % 2 == 1)
            n =  3 * n +1;
        else
            n /= 2;
        answer++;
    }
    if(answer >= 500)
        return -1;
    else
        return answer;
}

• Better Code

#include<iostream>
using namespace std;

int collatz(int num)
{
    int answer = 0;
  cout<< num <<"\n";
  while(answer++ <= 500){
    num = num%2 ==0 ? num/2 : num*3+1;
    if(num == 1) break;
  }

    return answer > 500 ? -1 : answer;
}

int main()
{
    int testCase = 6;
    int testAnswer = collatz(testCase);

    cout<<testAnswer;
}

" int 정수의 범위를 파악하자. "

• CheckPoint

• int 형 n의 정수형 수용범위를 확인하고, 필요할시 long이나 long long
• > 형을 사용할 생각을 하자.
• 이제는 짝수or홀수로 조건문의 조건을 작성할 때 if( n & 1 ) 형태를 기억.
  %연산자보다 비트연산자가 처리속도가 빠르다.
• 3항연산자를 잘 쓰면 코드가 짧아진다.