3주차 과제 (k번째 수, 회전하는 큐)

#1 k번째 수 https://school.programmers.co.kr/learn/courses/30/lessons/42748

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

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    for (int y = 0; y < commands.size(); ++y) {
        vector<int> vect;
        for (int x = commands[y][0] - 1; x < commands[y][1]; ++x) {
            vect.push_back(array[x]);
        }
        sort(vect.begin(), vect.end());
        answer.push_back(vect[commands[y][2] - 1]);
    }
    return answer;
}

 

 

#2 회전하는 큐 https://www.acmicpc.net/problem/1021

 

문제 이해가 한 동안 되지 않았다, 이 설명 통해 문제를 이해했다. 

https://www.acmicpc.net/board/view/65693 

글 읽기 - 문제가 이상한 것 같습니다.

 

백트랙킹으로 모든 경우의 수 중 최소 좌/우 밀어내는 횟수 값을 출력하고자 했는데, 좌/우 동시에 진행되는 경우 무한루프에 빠져 tc3, tc4를 출력하지 못하는 문제가 발생했다(tc1, tc2는 출력됬지만, 사실상 스택오버플로우 문제가 발생한거다)

 

중복발생 방지로  used 배열 사용하면 ? 구현이 복잡해질 듯 하다. 백트랙킹은 적합해보이지 않는다.

 

틀림.

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

/*
* 재귀로 모든 경우의 수 찾아서 그 중 작은 횟수를 구할 것.
con is condition meaning,   when con1_cnt == 3 , then return;
until con1_cnt ==3 , con2_cnt + con3_cnt is mini then that is result.
*/
int mini = 10e7;

int N, M;
void run(deque<int>dq, deque<int>target, int con1_cnt, int con2_cnt, int con3_cnt) {
    if (mini < con2_cnt + con3_cnt)return; // 가지치기
    if (con1_cnt == M) { // M개 모두 검사했으면 Return 
        if (con2_cnt + con3_cnt < mini) {
            mini = con2_cnt + con3_cnt;
        }
        return;
    }

    //if (target.size() == 1) {
    //    cout << "bug" << endl;
    //    return;
    //}
  //  stack over flow?  why

    deque<int>dq_backup = dq;
    deque<int>target_backup = target;

    // 0: 뽑기, 1: 왼쪽으로 한칸 이동  , 2: 오른쪽으로 한칸 이동

    //0. 뽑기
    if (dq.front() == target.front()) {
        dq.pop_front();
        target.pop_front();
        run(dq, target, con1_cnt + 1, con2_cnt, con3_cnt);
        dq = dq_backup;
        target = target_backup;
    }
    // 1. 왼쪽이동
    dq.push_back(dq.front());
    dq.pop_front();
    run(dq, target, con1_cnt, con2_cnt + 1, con3_cnt);
    dq = dq_backup;
    target = target_backup;

    //2. 오른쪽 이동
    dq.push_front(dq.back());
    dq.pop_back();
    run(dq, target, con1_cnt, con2_cnt, con3_cnt + 1);
    dq = dq_backup;
    target = target_backup;

}
int main(void) {
    cin >> N >> M;
    deque<int> dq;
    deque<int>target;
    for (int x = 1; x <= N; x++) {
        dq.push_back(x);
    }
    for (int x = 0; x < M; ++x) {
        int t;
        cin >> t;
        target.push_back(t);
    }
    run(dq, target, 0, 0, 0);
    cout << mini << endl;
}

 

 

멘토님으로부터 힌트를 얻어 중간 인덱스를 활용해 문제를 해결했다. 

 

정답.

/*
사이즈의 가운데 인덱스 와 타겟 값의 인덱스의 차이가 - 냐 +냐 즉
중간 인덱스 - 타겟 값의 인덱스 == + 면 좌측으로 밀기
-이면 우측으로 밀기.
while 이용
 while는 무한루프이나 조건문 달기, Target 벡터가 없다면 루프 끝내기
밀기 조건.

한쪽에만 치우쳐서 밀면 안됨, 
1,2,3,4,5,6,7,8,9,10
tar: 6, 8, 2 
에서 한쪽에만 치우치면 안됨, 중간인덱스 기준으로 어느쪽에 tar 인덱스가 치중됬는지 확인하고 밀어야함.. 
*/

#include<iostream>
#include<deque>
using namespace std;

int main(void) {
	int N, M, cnt = 0;
	deque<int>dq;
	deque<int>tar; //target
	scanf("%d %d", &N, &M);
	for (int x = 1; x <= N; ++x) {
		dq.push_back(x);
	}
	for (int x = 0; x < M; ++x) {
		int t;
		scanf("%d", &t);
		tar.push_back(t);
	}
	while (!tar.empty()) {
		int idx = -1;
		for (int x = 0; x < dq.size(); x++) {
			if (dq[x] == tar.front()) {
				idx = x;
				break;
			}
		}
		int dqSizeHalf = dq.size() / 2;
		if (dqSizeHalf - idx >= 0) {
		//+
			while (tar.front()!=dq.front()) { // 왼쪽으로 이동,  target 값을 찾을 때까지
				dq.push_back(dq.front());
				dq.pop_front(); // 왼쪽으로 이동 (spin)
				cnt++;
			}
			tar.pop_front();
			dq.pop_front();
		}
		else { // 0 또는 -
			while (tar.front() != dq.front()) { // 우측 이동
				dq.push_front(dq.back());
				dq.pop_back();
				cnt++;
			}
			tar.pop_front();
			dq.pop_front();
		}
	}
	cout << cnt << endl;
}

 

 

제출코드 ( print형식 c style로 통일)

#include<cstdio>
#include<deque>
using namespace std;

int main(void) {
	int N, M, cnt = 0;
	deque<int>dq;
	deque<int>tar;
	scanf("%d %d", &N, &M);
	for (int x = 1; x <= N; ++x) {
		dq.push_back(x);
	}
	for (int x = 0; x < M; ++x) {
		int t;
		scanf("%d", &t);
		tar.push_back(t);
	}
	while (!tar.empty()) {
		int idx = -1;
		for (int x = 0; x < dq.size(); x++) {
			if (dq[x] == tar.front()) {
				idx = x;
				break;
			}
		}
		int dqSizeHalf = dq.size() / 2;
		if (dqSizeHalf - idx >= 0) {
			while (tar.front() != dq.front()) { 
				dq.push_back(dq.front());
				dq.pop_front(); 
				cnt++;
			}
			tar.pop_front();
			dq.pop_front();
		}
		else {
			while (tar.front() != dq.front()) {
				dq.push_front(dq.back());
				dq.pop_back();
				cnt++;
			}
			tar.pop_front();
			dq.pop_front();
		}
	}
	printf("%d", cnt);
}