본문 바로가기

나는 오늘,

 (371)
[Programmers] 호텔 방 배정 #include #include #include using namespace std; typedef long long ll; vector solution(long long k, vector num) { vector answer; map roomMap; map ::iterator it; for (int i = 0; i < num.size(); i++) { if (roomMap[num[i]] == 0) { roomMap[num[i]] = i+1; //0을 피하기 위해 answer.push_back(num[i]); } else { //원하는 방이 이미 배정된 경우 ll idx = num[i]+1; while(1) { if (roomMap[idx] == 0) break; idx++; } roomMap[idx] ..
[Programmers] 불량 사용자 #include #include #include #include #include using namespace std; set s; bool chk[9]; int answer = 0; bool check(string id, int idx, vector &ban) { if (id.size() != ban[idx].size()) return false; for (int i = 0; i < id.size(); i++) { if (ban[idx][i] == '*' ) continue; if (id[i] != ban[idx][i]) return false; } return true; } void dfs(int idx, int cnt, vector&user, vector&ban, vector &res) { if (c..
[Programmers] 크레인 인형뽑기 게임 #include #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; //시뮬레이션 //같은 숫자가 2개 쌓이면 없어짐 stack st; int size = board[0].size(); //인형이 없더라도 0으로 차있기 때문에 사이즈는 같음 //중간에 0인 부분은 밑으로 끌어내려야 한다. // for (int i = 0; i 0 && !board[i][idx] && board[i][id..
[BOJ] 9470. Strahler 순서 + TC * 위상정렬을 이용 * 큐에서 방문하는 노드로 들어오는 가진 강의 순서가 가장 큰 값을 maxCost[] 에 저장한다. (이 값은 항상 최대값만 저장) * cost[]에는 가장 큰 값을 maxx라고 가정한다면 maxx가 1번 들어오면 maxx값을 그대로 저장하고 2번이상 들어오면 maxx+1 을 저장한다. * maxCost와 cost를 따로 두어야 한다. 같은 배열에 저장한다면 maxCost[] 의 값이 변경되면서 정답이 달라지기 때문이다. 간단하게 예를 든다면 3 4 2 4 1 4 이렇게 간선이 주어져있다고 가정하자. 1,2,3 번 노드는 강/호수 또는 바다와 인접한 노드이므로 1의 값을 가진다. 4번이 Strahler순서가 되는 값을 가질 텐데, indegree[4] = 3이다. 처음 1의 인접리스트..
[Programmers] 여행경로 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 풀이 1) 1번 TC만 시간이 328.93ms 으로 다른..
[Programmers] 정수 삼각형 문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 풀이 1) 2차원 배열 dp[501][501]에는 내가 있는 높이에서 가장 최대값을 담는다. 2) 정답은 가장 바닥에 있는 숫자 중 가장 큰 값이다. (위에서 거..
[BOJ] 1280. 나무심기 *세그먼트 트리를 사용한다. *현재 나무의 좌표가 [pos]라고 가정한다. pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 큰 좌표의 합 = sumUpper 개수 = a pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 작은 좌표의 합 = sumLower 개수 = b 3 2 0 4 1 이렇게 다섯 개의 나무가 심어질 것이다. 3의 관점에서 sumUpper = 0/ sumLower = 0 / a = 0 / b = 0 => cost = 0 2의 관점에서 sumUpper = 3 / sumLower = 0 / a = 1 / b = 0 => 좌표 사이의 거리를 구하는 것이기 때문에 sumUpper - pos*a를 해줘야 한다. (각 좌표에서 기준 좌표를 빼주는 것과 같다)..
[BOJ] 2636. 치즈 * 치즈가 없는 좌표(0)에서 탐색할 수 있는 곳에 (상하좌우) 치즈가 있는 좌표(1)가 있다면 -> 이번 타임에 녹는 치즈이다. * 큐를 돌고 있는 상황에서 치즈를 바로 없애버리면 (1-> 0) 한 타임에 모든 치즈가 녹아버린다. * 위 상황을 방지하기 위해 이번 타임에 녹은 치즈는 map에 -1로 표시한다. * 치즈의 개수를 셀 때 -1인 좌표를 0으로 바꾼다. (벡터에 넣어주고 그 좌표들만 0으로 바꿔줘도 되지만, 어차피 치즈 개수 셀 때 모든 맵의 좌표를 탐색하기 때문에 이 때 바꿔주는 것으로 했다.) * 치즈가 모두 녹아 없을 때까지 (check() == True) 반복한다. * 치즈가 모두 녹기 한 시간 전에 있는 치즈의 개수를 세야 하기 때문에 howmanyCheese()를 만들었다. 더 효..

티스토리툴바