문제 링크 전화번호 목록 풀이 해시 문제라고 했는데 정렬로 풀었다. a 번호가 b 번호의 접두어라고 한다면, 정렬을 했을 때 반드시 a 번호가 b 번호 앞에 나오게 된다. 임시 string인 tmp에는 접두어라고 가정할 번호를 넣는다. tmp가 비어있으면 tmp를 해당 번호로 갱신. 해당 번호에서 접두어를 뽑았는데 tmp와 같지 않아도 갱신. 같으면 해당 번호는 tmp를 접두어로 가진다는 것을 의미하므로 answer를 false로 한다. 코드 #include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); s..
문제 링크 입국심사 풀이 이분탐색으로 푸는 문제.. 떠올리는 게 어렵다.. 기준은 제일 빠르게 처리하는 1분과 가장 느리게 처리하는 심사관 * n이 될 것이다. 이 둘을 left와 right로 잡는다. 여기서 주의할 것은 long long 타입이기 때문에 right를 만들 때 int * int형으로 곱해져 int형이 나오기 때문에 형변환을 해주어야 함 mid는 left와 right의 중간 값을 잡고 이분 탐색을 시작할텐데, 이 기준은 mid시간에서 몇 명의 사람이나 처리할 수 있느냐로 본다. cnt가 n보다 크거나 같으면 right의 범위를 줄여주고 answer를 갱신해주고, 작으면 left의 범위를 키워준다. left의 위치가 right보다 작거나 같을 때까지 반복해준 뒤 answer를 출력한다. 코드..
문제 링크 롤케이크 자르기 풀이 set으로 풀었는데 시간 초과가 나서 힌트를 얻은 문제 굳이 기준을 잡아서 할 필요 없이 둘로 나누는 것이기 때문에 기준에서 하나씩 빼면 된다. set1에 toppings를 다 넣는다. 이 때 토핑의 개수를 생각해야하기 때문에 cnt 벡터로 토핑의 개수를 세준다. 이제 토핑을 하나씩 빼서 set2에 넣어줄텐데, 하나 뺀 토핑의 개수가 0일 경우 set1에서 지워준다. set1과 set2의 사이즈를 비교해서 같다면 answer++ 해준다. 코드 #include #include #include using namespace std; int solution(vector topping) { int answer = 0; set set1, set2; vector cnt(topping...
문제 링크 배달 풀이 다익스트라로 푸는 문제인데 최소신장트리로 헷갈려서 약간 돌아갔다. 입력받은 road를 이용해 인접리스트를 만들어준다. 거리가 갱신될 dist는 최댓값으로 초기화해준다. 우선순위 큐로 최단 거리를 갱신해준다. 거리 순으로 정렬 되도록 pair를 {cost, end} 형태로 만들어준다. 그리고 오름차순 정렬한다. dist[next]>dist[cur]+nextCost라면 거리가 갱신된다는 것이므로 갱신해준 뒤 pq에 push한다. 그렇게 만들어진 dist를 돌면서 k보다 작거나 같다면 1 더해준다. 코드 #include #include #include #define INF 20000001 using namespace std; int solution(int N, vector road, in..
문제 링크 미로 탈출 풀이 BFS를 이용하는 문제 미로를 만들면서 출발 지점인 stt와 도착 지점인 end를 만들어준다. BFS를 돌리는데 시간이 갱신될 time을 3차원 배열로 만들어준다. 원래 2차원 배열의 BFS는 방문한 지점을 다시 방문하지 않는데, 이 문제는 레버를 누르고 도착 지점으로 가야하기 때문에 왔던 길을 다시 방문할 수도 있다. 구조체 Cell을 정의한다. 위치가 담길 y와 x, 레버가 당겨졌었는지 확인할 flag로 구성되어 있다. 도착지점부터 q에 넣고 상하좌우를 탐색한다. 범위 밖이거나 벽이거나 방문 했었다면 continue, 레버라면 해당 지점에서 차원이 옮겨지게 된다. time을 갱신하고 q에 새로운 위치를 넣어준다. time[end.first][end.second][1]을 re..
문제 링크 아이템 줍기 풀이 BFS문제인데, 좌표를 두 배 확대하는 아이디어로 풀 수 있는 문제 2배하게 되면 각 영역의 점과 점을 잇는 선을 따로 구할 수 있어 겹치는 문제를 해결할 수 있다. 각 좌표는 50이하로 들어오므로 배열은 원래 51 사이즈로 만들어야하는데, 두 배이기 때문에 102 크기로 만든다. 사각형을 돌면서 각 좌표는 두 배해주고 1로 영역을 만들어준다. 좌표의 시작+1부터 끝-1까지는 안쪽이기 때문에 0으로 만든다. 외곽선을 BFS로 탐색하면서 거리를 구해주고, 답은 /2해줘야 나온다. 코드 #include #include #include #include using namespace std; int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; int ..
