Hyun's_Devlog

https://www.acmicpc.net/problem/16926

배열에 관련된 구현문제다.

풀이

일반적인 풀이 방법은 문제에 주어진 대로 2차원 배열을 탐색하여 반시계방향으로 요소를 옮겨주면 된다.

각 그룹이 R번 회전해야 하므로 이 방법으로 구현하게 된다면 O(N*M*R)에 해결할 수 있다.

하지만 swift의 경우 다른 언어에 비해 느려서 해당 방법으로는 시간초과를 받는다.

R번 회전한다는 것은 결국 원점으로 돌아올 수 있다는 것이고 이는 곧 회전 수를 줄일 수 있는 요인이라 생각했다. 문제는 회전해야 하는 그룹의 크기가 전부 달라서 이를 어떻게 해결할까 고민하였다.

https://www.acmicpc.net/board/view/86800

질문 탭을 보니 2차원 배열을 1차원으로 접근해 보라는 힌트를 발견. 해당 힌트를 통해 문제를 해결할 수 있었다.

입력예제 1을 기준으로 설명하면 다음과 같다.

회전시켜야 할 그룹을 파악한 후 1차원 배열로 생성.

(R % 각 배열의 크기) 부분에서 분리하여 순서를 바꾼 배열을 만든다.

이어서 다시 회전시켜야 할 그룹의 자리에 1차원 배열의 요소를 담아주면 O(2*N*M)만에 결과를 얻을 수 있다.

정답 코드

https://www.acmicpc.net/problem/17144

구현문제다.

풀이

문제에 주어지는 대로 먼지를 흩뿌리는 함수 spread()와 공기청정기를 가동하는 cleanClock(), cleanAntiClock() 함수를 구현하여 접근했다. spread() 함수의 경우 한 좌표의 인접좌표에 대해서 동작을 구형했고, 배열을 모두 탐색하면서 값이 0 이상이라면 함수를 수행하는 방법으로 구현했다.

공기청정기의 경우 시계/반시계 방향으로 순회하면서 값을 옮겨주는 동작을 구현하였다. 마지막으로 배열을 탐색하여 먼지의 수치를 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/4836

문자열 문제다. 쉽게 풀 수 있지만 문제 자체가 조금 번거롭기도 하고 꼼꼼히 보지 않으면 실수하기 쉽다. 

풀이

배열에 담아 각 조건을 탐색하면 된다. 1번 조건의 "dip은 jiggle을 춘 다음이나 다다음, 또는 twirl을 추기 전에 출 수 있다." 부분에서 twril이 문장 이후 아무 데나 나오면 되는 것으로 착각했다. dip 바로 뒤에 twirl이 오는지만 확인하면 된다.

다른 조건들의 경우 배열의 contain 메소드를 사용하여 풀어내면 된다. 단 출력할 때의 문장 포맷을 잘 확인하고 출력하자. 제대로 확인 안 해서 틀린 부분을 찾아내느라 시간을 낭비했다. 문제를 꼼꼼히 읽었는지를 요하는 문제다.

정답 코드

https://www.acmicpc.net/problem/3048

문자열, 구현 문제다.

풀이

입력받은 개미의 알파벳과 우측 좌측을 나타내는 문자열로 튜플을 생성한다. 우측으로 향하는 개미와 좌측으로 향하는 개미의 알파벳을 붙여 튜플 배열을 생성 후, T번의 반복문을 통해 우측+좌측이 붙어있는 경우를 만나면 swap을 수행하였다.

정답 코드

https://www.acmicpc.net/problem/1544

문자열 구현 문제다.

풀이

주어지는 시간이 넉넉한 편이므로 모든 문자열들을 비교하여 개수를 세면 된다. 두 문자열을 매개변수로 받은 뒤 시계방향으로 모든 경우를 읽어 같은지 같은지 다른지 판별하는 isSame(a:String, b:Stirng) -> Bool 함수를 구현하여 정답을 구하였다.

정답 코드

https://www.acmicpc.net/problem/2607

문자열과 연관된 구현문제다.

풀이

비슷한 단어의 판별은 문자열의 길이에 따라 총 3가지 경우가 나온다. 

1. 기준 문자열의 길이와 입력된 문자열의 길이가 같은 경우

구성요소가 완전히 똑같거나 하나 틀린 경우 비슷한 단어로 판별한다.

2. 기준 문자열의 길이가 입력된 문자열의 길이보다 하나 긴 경우

입력된 문자열의 구성요소가 기준 문자열의 구성요소에 완전히 포함되거나, 하나의 구성요소가 다를 경우에 비슷한 단어로 판별한다.

3. 기준 문자열의 길이가 입력된 문자열의 길이보다 하나 짧은 경우

기준 문자열의 구성요소가 입력된 문자열의 구성요소에 완전히 포함된 경우에만 비슷한 단어로 판별한다.

구성요소의 판별의 경우 입력되는 문자가 대문자로 한정되어 있어 26개의 배열을 생성하여 해당 요소에 해당하는 인덱스에 개수를 저장하여 계산하였다.

정답 코드

https://www.acmicpc.net/problem/3190

문제에 주어진대로 구현하면 되는 구현 문제다. 시간 흐름에 따른 뱀의 방향 전환을 어떻게 구현할지 고민했다.

풀이

2차원 배열에 뱀은 "S", 사과는 "A"로 표시하여 구분을 지었다. 뱀이 지도에서 어느 좌표 위에 있는지를 또 다른 배열에 담아 두고, 뱀의 머리가 "S"또는 지도의 범위를 빠져나간다면 게임을 종료시키는 것으로 구현하였다. 

방향 이동의 경우 4가지 방향을 정해놓은 x배열 y배열을 생성한 뒤, 최대 시간이 10,000이기에 시간을 표현하는 10,000 크기 배열을 생성하여 입력받은 시간 인덱스에 각 회전을 하기 위한 방향 정보를 담아두어 매 반복문(시간)마다 방향을 정해주었다.

뱀의 이동은 문제에 주어진대로 앞이 빈 공간이라면 뱀의 새로운 머리 좌표를 배열의 맨 앞에 추가한 뒤, 배열의 마지막인 꼬리 좌표를 removelast()를 통해 이동을 처리하였다. 사과를 만났다면 꼬리 좌표는 그대로 두면 된다.

정답 코드

https://www.acmicpc.net/problem/15685

구현 문제다. 규칙에 대한 파악과 x축과 y축 반전, 격자 칸의 수 등 실수를 유발하기 위한 장치들이 많은 문제라고 생각한다. 드래곤 커브에 대해 파악하는 데에 시간이 오래 걸렸던 문제다. 이런 유형의 경우 시간 내로 풀이를 생각하는 게 중요하다고 생각된다.

풀이

드래곤 커브의 움직임에 대해 이해가 필요한데, 문제에 주어진 번호에 따른 방향을 보면 힌트를 얻을 수 있다. 다음 세대의 움직임은 이전 세대의 다음 인덱스의 방향으로 움직이게 된다. 단 이전 세대의 움직임의 역순으로 추가를 시켜야 한다. 정리된 표를 통해 보면 이해하기 쉽다.

일반적인 2차원 배열을 통해 풀어내려면 x축과 y축을 반대로 생각하고 풀어야 한다. 이어서 해당 문제는 격자가 100칸 즉 배열로 생성하려면 가로세로 101칸의 배열을 생성해야 100칸의 격자가 만들어진다. 본인의 경우 생각 없이 가로 세로 100칸의 배열을 생성했다가 오답 판정을 받았다. 입력되는 드래곤 커브는 격자의 범위를 벗어나지 않는다는 조건이 있으니 범위 체크는 하지 않아도 된다. 드래곤 커브로 둘러싸인 격자를 세는 방법은 인접한 4칸을 확인하며 세면 된다.

정답 코드