youngmin.log

• [ 장르 ] Queue
• [ 문제 ]

• My Code

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

int main()
{
	int cnt,i = 0,data;
	queue<int> que;
	string str;

	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);	 // ★ 입출력속도개선선언부
	cin >> cnt;
	while (i < cnt)
	{
		cin >> str;
		if (!str.compare("push"))
		{
			cin >> data;
			que.push(data);
		}
		else if (!str.compare("pop"))
		{
			if (!que.empty())
			{
				cout << que.front() << '\n';	// ★ 개행마다 endl이 아닌 '\n'
				que.pop();
			}
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("front"))
		{
			if (!que.empty())
				cout << que.front() << '\n';
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("back"))
		{
			if (!que.empty())
				cout << que.back() << '\n';
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("size"))
			cout << que.size() << '\n';
		else
			cout << que.empty() << '\n';
		i++;
	}
}

[ CheckPoint ]

• 기본적인 큐(Queue) 기능문제이다. C++에선 <queue> container에 모든 왠만한 queue연산은 제공되 있으므로 이를 잘 인지하고 있는지
  확인하는 정도의 문제이다.
• 다만, 이 문제 역시 실행속도 문제때문에 메인 본문에 코드에 주석처리로 된 ★ 부분이 선언부를 작성해주고, 하나 더 C++의 endl개행보다 
  '\n'  을 사용하는것을 지향한다.

• [ 장르 ] 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를 피할 수 있다.

• [ 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. 함수는, 배열이나 벡터 큐 등등 (문자열도 됨) 에서 시작과 끝 사이에서 각각 최대값, 최소값을 반환한다.
   다만 값이 아닌 주소를 반환하기 때문에 함수앞에 참조연산자를 붙인다.