Heecheol's blog

문제 https://www.acmicpc.net/problem/15828 15828번: Router 인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 www.acmicpc.net 풀이 스위프트에서는 큐가 구현되어있지 않아서 따로 구현해야한다. 배열을 그대로 이용하는 방법도 있지만 removeFirst()때문에 O(n)이 될 수 밖에 없어 두 스택으로 구현해서 사용했다. reversed()가 O(1)이기때문에 시간복잡도가 더 낮기 때문에 시간이 더 빠를 것이다. 0인 경우, rightQueue가 비어있다면 left를 뒤집어서 넣은 뒤에 removeLast()를 이용해서 ..

문제 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 처음에는 스택에 계속 추가하다가 last값보다 새로 들어오는 값이 더 큰 경우에만 removeLast()를 하도록했다. 그러다보니 중복된 경우가 있는 상태에서 해당 값보다 큰 값이 들어올때마다 중복되는 개수만큼 반복문을 돌게되었다. 역시 시간초과 두번째로 했던 방법에서는 스택에 키만 갖는 원소를 추가하는 것이 아닌, 높이와 개수를 갖는 [Int]를 추가하도록 해주..

문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 풀이 다리를 queue라고 생각하고, 다리에 무게를 초과하지 않을때까지 트럭을 1초마다 추가하였다. 이때, end라는 배열에 트럭이 지나가는 시간을 같이 추가해주었다. 시간을 1초씩 증가시키며 end[0]와 time이 같은 경우엔 트럭이 지나간 것이므로 큐에서 맨 앞 트럭을 제거해주었다. 이렇게 구현한 경우엔 마지막 트럭이 trucks배열에서 ..

문제 https://www.acmicpc.net/problem/14713 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 풀이 당연하게 cseteram이 모든 말을 다 받아적었을거라고 생각해서 오래걸렸다. cseteram이 받아적은 단어들을 큐에 넣고 앵무새들이 말한 문장의 맨 앞 단어와 비교해서 맞을때마다 하나씩 지워주었다. 반복문이 끝나고 앵무새 문장의 배열들과 cseteram이 모두 비어있는 경우에만 Possible을 출력하도록 하였다. import Foundation let n = Int(re..

문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 큐를 이용해서 풀 수 있는 문제였다. 프린터 큐를 돌리며 가장 큰 값인 경우에 출력하고, 그 값을 큐에서 제거하는 것을 반복해주었다. 타겟이 아닌 문서가 큐에서 제거될때마다 count값을 증가시켜주었고, 타겟의 인덱스를 1씩 감소시켜주었다. 타겟의 인덱스가 0이고, 타겟이 큐에서 가장 큰 값일때의 count를 출력하였다. 배열에서 max값을 구하는 것은 O(N)인데 프린터가 될때마다 max..