Heecheol's blog

문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 BFS로 해결할 수 있는 문제였고, 익숙하지가 않아서 어려웠다. 반복문을 통해 보드를 하나씩 이동하며 방문하지 않은(visited가 false) 자리이고, paper[i][j]가 1인 경우에 BFS를 통해 그림을 확인하였다. BFS를 수행하는 과정은 다음과 같다. 우선, 큐에 해당 위치인 [i][j]를 넣어준다. 다음으로 [i][j]를 방문했으므로 visited[i][j]를 true로 바꿔준..

문제 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에서도 ..