1. 방의 개수
1) 문제
문제 설명
제한 사항
배열 arrows의 크기는 1 이상 100,000 이하 입니다.
arrows의 원소는 0 이상 7 이하 입니다.
방은 다른 방으로 둘러 싸여질 수 있습니다.입출력 예
arrows return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3
2) 문제 분석 및 풀이
1) 설계, 분석
탐색시 경로가 상태를 저장하게 해야하는 문제
2) 풀이
#include <string> #include <vector> #include <set> #include <algorithm> #include <map> using namespace std; map<pair<int,int>, vector<bool>> visited; int dy[] = {-1,-1,0,1,1,1,0,-1}; int dx[] = {0,1,1,1,0,-1,-1,-1}; int solution(vector<int> arrows) { int answer = 0; int cx = 0; int cy = 0; int cdir = 0; visited[{cx, cy}].resize(8,false); for (auto& dir : arrows) { for (int i=0; i< 2; i++) { int nx = cx + dx[dir]; int ny = cy + dy[dir]; if (visited.find({nx, ny}) == visited.end()) { visited[{nx, ny}].resize(8,false); } else { if (visited[{nx, ny}][dir] == false) answer++; } visited[{nx, ny}][dir] = true; visited[{cx, cy}][(dir+4)%8] = true; cx = nx; cy = ny; } } return answer; }
2. 순위
1) 문제
문제 설명
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
선수의 수는 1명 이상 100명 이하입니다.
경기 결과는 1개 이상 4,500개 이하입니다.
results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
모든 경기 결과에는 모순이 없습니다.입출력 예
n results return
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
2) 문제 분석 및 풀이
1) 설계, 분석
줄을 세울 수 있는 조건을 알아내면 간단한 문제
이긴횟수+패배횟수 = 나를 제외한 사람수 이면
모든 사람과 경기를 했다는 뜻으로 순위를 알 수 있다.
2) 풀이
#include <string> #include <vector> #include <climits> #include <unordered_map> #include <queue> using namespace std; unordered_map<int, vector<int>> winList; unordered_map<int, vector<int>> loseList; int N; int bfs(int start, unordered_map<int, vector<int>> adjList) { vector<bool> visited(N+1, false); queue<int> q; q.push(start); visited[start] = true; while(!q.empty()) { int u = q.front(); q.pop(); for (auto& v : adjList[u]) { if (visited[v]) continue; visited[v] = true; q.push(v); } } int cnt=0; for (int i=1; i<N+1; i++) { if(visited[i]) cnt++; } return cnt - 1; } int solution(int n, vector<vector<int>> results) { int answer = 0; N = n; for (auto& result : results) { int A = result[0]; int B = result[1]; winList[A].push_back(B); loseList[B].push_back(A); } for (int i=1; i<N+1; i++) { int iWinCnt = bfs(i, winList); int iLoseCnt = bfs(i, loseList); if ((iWinCnt + iLoseCnt) == N-1) answer++; } return answer; }
3. 합승 택시 요금
1) 문제
문제 설명
2) 문제 분석 및 풀이
1) 설계, 분석
합승없이 가는 경로, 합승 후 가는 경로를 나누면 간단한 문제
합승을 어디까지 하는지 순회하며 최솟값 넣기
2) 풀이
#include <string> #include <vector> #include <climits> using namespace std; vector<vector<int>> cost; int solution(int n, int s, int a, int b, vector<vector<int>> fares) { int answer = 0; cost.resize(n+1, vector<int>(n+1, INT_MAX)); for(auto& fare : fares) { int from = fare[0]; int to = fare[1]; int weight = fare[2]; cost[from][to] = weight; cost[to][from] = weight; } for (int k=1; k<n+1; k++) { for (int i=0; i<n+1; i++) { for (int j=0; j<n+1; j++) { if (i==j) { cost[i][j] = 0; continue; } int i2j = cost[i][j]; int i2k = cost[i][k]; int k2j = cost[k][j]; if (i2k == INT_MAX) continue; if (k2j == INT_MAX) continue; if (i2j > i2k + k2j) { cost[i][j] = cost[i][k] + cost[k][j]; } } } } answer = INT_MAX; for (int i=1 ; i<n+1; i++) { if (i == s) continue; int stoi = cost[s][i]; int itoa = cost[i][a]; int itob = cost[i][b]; answer = min (answer, stoi + itoa + itob); } return answer; }
