Programmers [2020 KAKAO BLIND RECRUITMENT]: 외벽 점검(C++, Python)/Simulation

https://programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

2020 카카오 공채 문제 중 1개인 외벽 점검 문제이다(정답률 0.6%)

원형으로 이루어진 취약 지점들과, 임의 숫자의 사람들이 이동 가능한 거리를 주어주고

벽을 수리할 수 있는 최소 인원을 구해야 한다

대부분의 문제들과 같이 범위는 작아서 완전탐색으로 코딩 가능하다 ❗

물론 나는 완탐인건 알았지만 효율을 망쳐버려서 시간초과때문에 애를 먹엇ㄷㅏ..

 

처음에는 모든 dist 경우의 수에 대해, 모든 weak 조합에 대해, 시계/반시계 방향으로 전부 검사를 했는데 32점짜리 코드였다 ^^

 

하지만 시계/반시계를 나눌 필요가 없었고(방향이 없는 정답이기 때문에)

또, weak의 permutation은 오름차순(한 방향)으로만 진행해도 된다

 

이 두 가지 경우를 고려해줘서 코드에 반영해주니 바로 solve할 수 잇엇다 !!

pickpeople()에서는 limit개의 사람을 뽑아 permutation을 만들고, 해당 조합에 대해 checkArea를 생성한다

checkArea()에서는 한 방향의 모든 조합(15610, 561013 ..)에 대해 인자로 넘겨받은 dist배열이 모든 weak에 대해 점검을 완료할 수 있는지 확인한다

 

C++

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

using namespace std;
int N;
vector<int> di, map;
int answer;

int func(vector<int> dist) {
	vector<int> v=map;
	for (int j = 1; j < v.size(); j++) {
		int cur = 0;
		for (int i = 0; i < dist.size(); i++) {
			int k = v[cur] + dist[i];

			while (cur < v.size() && v[cur] <= k)cur++;

			if (cur == v.size())
				return dist.size();
		}
		vector<int>::iterator it = v.begin();
		int fi = v[0]+N;
		v.erase(it); v.push_back(fi);
	}
	return -1;
}

int people(vector<int> p, int dep, int limit) {
	if (dep > limit) {
		vector<int> v;
		for (int i = 1; i <= limit; i++)
			for (int j = 0; j < p.size(); j++) {
				if (p[j] == i)v.push_back(di[j]);
			}
		return func(v);
	}
	int min = p.size() + 1;
	for (int i = 0; i < p.size(); i++) {
		if (p[i])continue;

		p[i] = dep;
		int k=people(p, dep + 1, limit);
		if (k>0&&k < min)min = k;
		p[i] = 0;
	}
	return min;
}

int solution(int n, vector<int> weak, vector<int> dist) {
	N = n; map = weak; di = dist;
	answer= dist.size() + 1;

	vector<int> v(weak.size()), p(dist.size());

	for (int i = 1; i <= dist.size(); i++) {
		int k = people(p, 1, i);
		if (k>=0&&k < answer)answer = k;
	}
	if (answer == dist.size() + 1)return -1;
	return answer;
}

Python

from itertools import permutations

def solution(n, weak, dist):
    for p in range(1,len(dist)+1):
      
      perm = list(permutations(dist, p))
      
      for friends in perm:
        
        for i in range(len(weak)):
          cur=0
          w=0
          d=friends[0]
          
          while cur<p and w<len(weak):
            sub = (n+weak[(w+i+1)%len(weak)]-weak[(w+i)%len(weak)])%n
            
            if d>=sub:
              w+=1
              d-=sub
            else:
              cur+=1
              w+=1
              if cur<p: d=friends[cur]
          
          if w==len(weak): return p
    
    return -1

 

시간복잡도: O(D!*W*D)

weak의 길이를 W, dist의 길이를 D라고 한다면

dist 조합의 최대항이 DPD(=P!)이고, 모든 weak지점에서 start하는 경우를 고려하며,

각각의 사람이 점검하는 연산을 하기 때문이다

dist의 최대값은 8이고, weak의 최대값은 16이기 때문에 최대 연산 횟수는 약 5,160,960정도라고 할 수 있다 🤗