Heecheol's blog

문제 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..

문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 처음 방법(비효율적) 처음에 풀었던 방법은 입력된 문자열에서 removeLast()로 원소를 스택에 추가한 뒤, 스택의 size가 폭발 문자열의 count와 동일할 때 매번 검사를 해주도록 구현하였다. removeLast()로 받다보니 reversed()를 이용해서 다시 뒤집어야했고, 관련이 없는 문자열이 들어올때도 size만 맞으면 검사를 해야했다. 시간초과가 나오지는 ..