queue4 [Swift][프로그래머스][Queue] 다리를 지나는 트럭 요구능력 큐 문제풀이 큐를 따로 구현해줘야하니 이글을 먼저 읽고오시는걸 추천드립니다. 트럭이 정해진 순서대로 다리를 건넌다고한다. 다리를 건너는 트럭의 경우에는 뒤에서 들어와서 앞으로 나가니까 큐를 생각하게된다. 예제 1번으로 설명을하면 다리를 건너는 트럭의 큐(contiQueue)는 처음에 다리의 길이가 2이기 때문에 아래와 같이 생성된다. 0초 [0, 0] 1초 [0, 7] 2초 [7, 0] 3초 [0, 4] 4초 [4, 5] 5초 [5, 0] 6초 [0, 6] 여기까지돌고 마지막에 들어온 6은 맨 마지막에 따로 다리의 길이만큼 더해줘서 마지막 트럭이 다리를 건너는 시간을 처리해줬다. 후기 쉬운문제이지만, Swift의 경우에는 큐를 따로 구현해줘야 최적화되기 때문에 난이도가 있는편이다. 코드 stru.. 2022. 4. 12. [Swift][Programmers][Queue] 프린터 요구능력 큐에대한 이해 문제풀이 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 위의 문제의 조건을 보면 맨앞에서 꺼내서 맨뒤로 넣는다. 전형적인 큐를 이야기 하고있다. 나의 경우 귀찮아서 문제를 지저분하게 풀었지만 튜플을 이용해서 큐를 사용하면 더욱 깔끔하게 문제를 해결 할 수 있다. ABCD를 넣어서 푸는사람도 있겠지만 이 역시 귀찮아서 identy배열에 0부터 queue의 개수만큼 넣어줘서 고유한 숫자로 적용해줬다. priorities가 [2, 1, 3, 2]라면 identy는 ["0", "1", "2", "3"]이렇게.. 2022. 4. 12. [Swift][알고리즘][꿀팁] Queue 구현하기 Queue 따로 구현해야 하는 이유? 보통 우리가 Swift에서 Queue를 구현 할 때는 하나의 배열에서 removeFirst()를 이용해 앞에서 빼고 append()를 이용해 뒤로 넣는 방식으로 구현합니다. 하지만, removeFirst()의 경우에는 O(n)의 시간복잡도를 갖기 때문에 많은 양의 원소가 왔다갔다하는 Queue에서 아주 비효율적입니다. (저는 초반에 큐를 이용하는 BFS문제들에서는 시간초과가 안나오다가 갈수록 모든 문제에서 시간초과가 발생하더라구요!) 자, 우선 전체 코드를 한번 읽어보세요! 보통 일반적인 경우에는 큐를 push, pop, empty()정도만 사용하는 것 같아서 저는 3가지만 간단하게 구현해보았습니다. 아래 코드를 완벽하게 이해하기 위해서 Swift Generic T와.. 2022. 3. 21. [Swift][BFS] 백준 7576번 (토마토) 요구능력 : BFS에 대한 이해 코드설명 : 이 문제의 핵심 1. 인접한 왼쪽, 오른쪽, 앞, 뒤 네방향에 있는 토마토에 영향을 준다. 2. 익은 토마토가 있는 지점부터 시작해야한다.(여러개가 있을경우 여러군데에서 시작한다. 예제3번 참조) 3. 토마토를 다익히지 못했을 경우를 생각해야한다.(예제2번같은경우) 4. 따로 Queue관련해서 지원되는게 없는 언어의 경우 시간초과에 유의한다.ㅠ 1. 1로 시작하는 시작지점들을 찾아서 Queue에 넣어둔다. for i in 1...m{ for j in 0.. 0 && nx = 0 && ny < n{ if arr[nx][ny] == 0{ arr[nx][ny] = 1 depth[nx][ny] = depth[pop.0][pop.1] + 1 queue.append((.. 2021. 11. 9. 이전 1 다음