본문 바로가기
반응형

Problem Solving242

백준 1697번 숨바꼭질 - 스위프트(Swift) 풀이 현재 상황을 그래프로 치환할 수 있음을 떠올리면 그 뒤로 구현은 쉽다. 1. 각 점을 정점이라고 생각한다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. 3. 정점 N에서 K까지의 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS로 쉽게 구할 수 있다. 1. 각 점을 정점이라고 생각한다. 현재 상황을 그래프로 나타낼 수 있다. 0부터 100,000번까지 총 100,001개의 정점이 있다. 2. 모든 정점에 대해서 [X+1, X-1, X*2]로 가는 방향 간선 3개를 추가한다. X번 정점에서 1초 만에 다이렉트로 갈 수 있는 정점은 X+1, X-1, X*2이다. 그래프에 X에서 저 세 정점으로 가는 방향 간선을 추가해준다. 방향 간선이라는 것을 주의해야 한다.. 2022. 1. 15.
백준 7662번 이중 우선순위 큐 - C++(cpp) 풀이 문제 제목에서부터 알 수 있듯이 우선순위 큐를 써야 하는데, 스위프트에는 라이브러리로 우선순위 큐를 제공하지 않아서 C++로 풀었다. 1. 최댓값은 최댓값 큐에서 찾는다. 2. 최솟값은 최솟값 큐에서 찾는다. 3. 반대쪽 큐에서 제거된 값인지 구별하기 위해, map에 해당 숫자가 현재 몇 개 남아있는지 기록한다. 먼저 최대값과 최솟값을 모두 알아내야 하므로 우선순위 큐를 2개 운영해야 한다. 하나는 최댓값용, 하나는 최솟값용으로. 근데 이렇게 되면 삭제를 할 때 문제가 된다. 최솟값을 삭제하라는 쿼리가 들어오면, 최솟값 큐에서 pop을 할 것이다. 근데 이 최솟값이 최댓값 큐에는 남아있게 된다. 따라서 반대 큐에서 삭제 여부를 알 수 있도록, 어떤 수 x가 현재 몇 개 남아 있는지를 기록해두어야 한다. .. 2022. 1. 14.
백준 1966번 프린터 큐 - 스위프트(Swift) 풀이 배열로 환형 큐를 구현하면 된다. front를 현재 맨 앞에 있는 문서를 가리키는 포인터라고 하면, 1. 앞에서 뽑은 것을 다시 맨 뒤에 넣기 : 그냥 front를 하나 뒤로 옮기면 저절로 된다! 2. 인쇄하기 : 해당 자리에 인쇄 표시를 하고 front를 뒤로 하나 옮긴다. (다음에 front가 이 자리에 오면 없는 셈 치고 스킵하면 됨) 3. 인쇄해야할 대상인지 판단 : 우선순위들을 정렬한 배열을 따로 둬서 남은 문서 중 우선순위 최댓값을 알 수 있도록 한다. 1. 앞에서 뽑은 것을 다시 맨 뒤에 넣기 front를 하나 뒤로 옮기면, 그 다음 문서가 front가 되고, 현재 문서는 front의 바로 왼쪽으로 가게 된다. front를 계속 우측으로 한 칸씩 이동시킬 것이므로, front의 바로 왼쪽에 .. 2022. 1. 13.
백준 2292번 벌집 - 스위프트(Swift) 풀이 자료형 범위 신경 안 써서 틀려버린 문제.......ㅎㅎ 브론즈라 방심했다. 중심인 1을 기준으로 한 겹(?)씩 늘어나면서 육각형 모양이 점점 커지는데, 한 겹 늘어날 때마다 전체 육각형의 한 변의 길이는 1씩 늘어난다. 따라서 최초를 0겹이라 하면, n겹 차에는 n*6개(모든 변의 길이의 합만큼)가 새로 추가된다. 예를 들어서 설명하면 처음에 1만 있는 상황은 0겹차고, 이제 1겹 차에는 1*6 = 6개, [2, 3, 4, 5, 6, 7]가 추가된다. 2겹차에는 2*6 = 12개, [8, 9, 10, 11, ..., 19]이 추가된다. 이렇게 n겹 차에 추가되는 수 중 가장 작은 수를 lo라고 하고 가장 큰 수를 hi라고 두어서, 이번 겹 차에 N이 들어가는지 체크해주는 방식으로 구현했다. 방금 예로 .. 2022. 1. 13.
백준 1436번 영화감독 숌 - 스위프트(Swift) 풀이 먼저 브루트포스로 가능한 지부터 고려해야 한다. 1, 2, 3... 이렇게 1부터 차례로 666이라는 수를 포함하는지 체크해서 N번째로 666을 포함하는 수를 만나면 출력하고 break 해주면 간단하게 구할 수 있을 것이다. 이 방법이 제한 시간 안에 통과되는지 계산해보자. 일단 N의 최대값이 10,000이다. N = 10,000일 때 답이 몇 일지 예상해야 한다. (예상 못하겠으면 그냥 N=10,000으로 두고 위에 반복문 돌려서 기다려보면 알 수 있긴 하다.) 대충 666이 맨 끝에 오는 경우만 생각해줘 봤는데, 10,000가지가 되려면 채우려면 666 앞에 4자리가 더 붙어야 한다. _ _ _ _ 666 이렇게 되면 각 자리마다 0-9가 들어갈 수 있으니까 10,000가지가 될 것이다. 따라서 N .. 2022. 1. 13.
반응형

티스토리툴바