Heecheol's blog

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 케이스도 많지 않아 구현만 하면 되는 문제였다. 뱀의 길이를 큐의 크기로 생각하였다. 이동한 위치를 current라는 변수로 나타내고, 이 current가 사과를 먹었다면 큐에 current를 추가하고 꼬리를 지우지않는 방향으로 구현하였다. 방향은 0,1,2,3을 각각 오른쪽, 위, 아래, 왼쪽으로 생각하여 방향에 따라 current의 값을 계산해주었다. import Foundation let..

문제 https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 풀이 이전에 두 개의 배열로 구현했던 큐와 딕셔너리를 이용해 해결하였다. 등수 차이를 큐의 사이즈로 생각하고 append하다가 사이즈를 초과하게되면 등수 차이가 주어진 값보다 큰 것이므로 맨 앞의 원소를 제거하면서 진행하였다. map을 이용해 이름의 길이를 큐에 넣고, 이름의 길이를 key로 갖는 value의 값을 1 더해주었다. 마찬가지로 제거될때는 -1을 해주어 좋은 ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 reversed()의 시간복잡도가 O(1)이기 때문에 reversed()를 이용해서 구현해봤는데 시간초과가 나왔다. 찾아보니 포인터로도 할 수 있을 것 같아 head와 tail 변수를 포인터로 생각하여 구현하였다. 어차피 뽑아내는 것은 앞에서만 뽑아내므로 reversed를 나타내는 변수를 두어 뒤집어진 상태에서는 tail을 하나 감소, 기본 상태에서는 head를 1 더해주었다. 이때 생각해야할건 tail보다 head가 큰 상태에서 D가 다시 ..

문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 deque이라는 자료구조를 맛보기 위해 풀어보았다. queue와 마찬가지로 두 개의 배열로 구현할 수 있다. deque은 양쪽 모두 push와 pop이 가능하기 때문에 queue를 구현했던 코드에서 살짝만 추가해주면 된다. 이전에 queue에서 pop을 구현할때 right가 비어있으면 left를 뒤집어서 넣은 뒤에 removeLast()로 구현했었는데, deque에서도 ..

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