Hyun's_Devlog

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

구현 문제다. 주사위의 회전 방향을 생각하면서 문제를 풀면 간단하게 풀 수 있다.

풀이

주사위를 6칸짜리 배열로 할당하여 순서대로 주사위의 윗면, 북, 동, 서, 남, 바닥면으로 할당한 뒤 입력되는 방향에 맞게 주사위 원소들을 이동하였다. 즉 주사위 면은 가만히 있고, 주사위에 적힌 숫자가 회전하는 개념으로 문제를 풀었다. 

정답 코드

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

구현 문제다. 문제에서 제시한 조건에 맞는 탐색을 통해 구현하면 된다.

풀이

입력이 주어지면 해당 학생의 번호와 좋아하는 사람의 번호들을 n*n개의 배열에 담아 저장한다. 마지막에 행복도 측정을 위해 한번 더 사용해야 하기 때문이다. 매번 정보가 입력될 때마다 교실을 행 - 열 순서로 탐색하면서 아직 배치가 되지 않은 자리에 대해서 인접한 좋아하는 사람의 개수와 인접한 빈 공간의 개수를 반환하는 cntLovers(x:Int, y:Int, lovers:[Int]) 함수를 통해 정보를 반환받은 후 문제에서 제시된 조건에 맞게 입력된 학생의 번호를 담아내야 할 좌표를 갱신한다. 이후 탐색이 끝나면 갱신된 좌표에 학생 번호를 입력한 후 다음 입력을 받는다.

마지막에 행복도 측정을 위해 한번 더 교실을 돌면서 해당 좌석의 번호에 해당하는 cntLovers(x:Int, y:Int, lovers:[Int]) 함수를 통해 행복도를 측정하면 된다.

정답 코드

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

구현 문제다. 톱니의 회전은 간단하게 구현이 가능하지만 문제는 회전하기 전 각 극성을 확인하여 주변 톱니바퀴를 회전해야 할지 회전하지 말아야 할지, 회전한다면 시계방향인지, 반시계 반향인지에 대해 오래 고민했던 문제다.

풀이

처음에는 재귀 호출 방식으로 구현하여 톱니가 회전하게 되면 양 측면의 톱니를 회전할지 말지를 확인 후 재귀 호출하는 방법으로 접근했었다. 하지만 그렇게 접근하게 되면 생각해야 할 조건이 너무 많아지게 된다. 따라서 톱니의 번호와 방향이 입력되면, 4개의 톱니의 회전 방향을 결정하고 난 후 한 번에 처리하는 방법으로 코드를 작성하였다.

톱니의 회전방향을 담아낼 progress: Array(repeating: 0 , count: 4) 배열을 생성한 후 해당 원소가 0이면 회전하지 않고, -1이면 반시계, 1이면 시계방향으로 회전하게 된다. 회전 방향과 톱니의 번호가 입력되면 다음과 같은 동작을 수행한다.

1. 입력된 번호에 해당하는 progress 배열 원소에 입력된 방향 담기
2. 입력된 번호부터 0까지 감소하면서 톱니의 맞닿은 부분의 조건 확인
3. 조건이 맞다면 기존 방향을 뒤집어가며 해당 인덱스의 progess 원소에 방향 담기
4. 입력된 톱니번호부터 마지막 톱니 번호까지 증가하면서 톱니의 맞닿은 부분의 조건 확인
5. 조건이 맞다면 기존방향을 뒤집어가며 해당 인덱스의 progess 원소에 방향 담기

중간에 조건이 맞지 않는다면 반복문은 바로 탈출한다. 이후 마지막에 일괄로 톱니의 회전을 처리하면 된다.

정답 코드

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

구현 문제다. 다리를 어떤 자료구조로 구현해낼지 고민해야 하는 문제다. cpp의 경우 큐 혹은 덱을 이용하여 풀면 되겠지만 스위프트의 경우에 큐나 덱이 없기에 배열을 사용해야 한다.

풀이

다리를 표현하는 bridge: Array(repeating:0, count:w) 배열을 생성하여 허용 중량까지만 담아내고 매 차례마다 원소들을 다음 인덱스로 밀어주는 함수 enter(truck:Int)를 구현하였다. 최대 중량과 현재 중량을 비교하는 부분에서 고민을 했던 문제다. 다리 끝자락에 위치한 트럭이 내리자마자 조건이 맞다면 바로 다음 트럭이 들어가야 하기 때문에 (현재 중량 - 마지막 트럭 무게 + 들어가야 할 트럭 무게) <= 최대 중량이라는 조건으로 매 차례 함수를 수행하였다. 트럭이 들어갈 수 없다면 0 무게를 bridge 배열에 추가하였다.

정답 코드

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

BFS 문제다. 산봉우리라고 판단하는 조건에 대해 고민해봐야 하는 문제다.

풀이

현재 좌표 기준 8방향 좌표의 높이를 탐색하고, 한 번이라도 보다 더 높은 좌표가 발견된다면 해당 탐색은 산봉우리가 아닌 것으로 처리한다. 만일 같은 높이의 좌표가 발견된다면 큐에 넣고 탐색을 이어간다. 탐색 큐를 모두 살펴본 뒤 마지막에 산봉우리인지 아닌지에 대한 flag를 확인하여 산봉우리의 개수를 추가해주면 된다. 당연하게도 무한루프에 빠질 수 있으니 방문 배열을 만들어 처리해야 한다.

정답 코드

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

문자열, 구현 문제이다. 딕셔너리 자료형을 사용했으나 시간 초과를 받았다. 아마도 알파벳순으로 정렬하는 과정에서 오래 걸린 듯싶다. 이후 크기 26인 배열을 생성하여 각 알파벳 순서대로 만들기 위한 개수와 사용 횟수를 담아 처리하였다.

풀이

퍼즐의 가운데 글자가 반드시 포함되어야 하는 것이 조건이다. 즉 해당 퍼즐을 통해 만들 수 있는 단어의 개수가 최저, 최고인 글자를 판별하는 문제다.

입력되는 단어들은 크기 26의 배열로 변환한다. 배열의 각 원소는 해당 알파벳의 개수를 담는 배열이다. 이후 해당 배열을 담는 2차원 배열 dictionary를 만든다.

퍼즐을 입력받을 때에는 마찬가지로 각 알파벳이 몇 개 있는지 나타내는 크기 26의 배열과 이후 dictionary를 탐색하면서 만들 수 있는 단어라 판단되면 해당 단어를 만들기 위해 사용된 알파벳의 횟수를 담는 배열 cnt: Array(repeating: -1, count:26)를 생성한다. 중요한 점은 해당 원소의 알파벳이 사용되었는지 사용되지 않았는지를 판별하기 위해 모든 크기 26짜리 배열은 -1로 초기화 한상태로 시작해야 한다. 코드로 보면 이해하기 쉬울 것이다.

마지막으로 cnt를 탐색하면서 최저 횟수와 최고 횟수를 찾아낸 뒤 해당 알파벳들을 출력해주면 된다.

정답 코드

 퍼즐의 입력 횟수가 문제에 적혀있지 않아, 처음 시간 초과를 받았을 때는 print() 호출 횟수가 많아져 스위프트의 느린 print() 속도를 대처하기 위해 Rhyno님이 작성한 FileIO 클래스를 사용했었다. 하지만 결론적으로는 해당 사항은 원인이 아니었고 아마도 딕셔너리 구조의 sort() 메서드의 속도가 느린 것이 더 큰 요인이지 않았나 싶다. 

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

완전 탐색 문제다. 두 배열 비교를 어떤 식으로 수행하는지 고민해야 하는 문제.

풀이

두 배열 중 짧은 배열을 덱을 사용하여 원소를 하나씩 담아낸 뒤 긴 배열과 비교, 짧은 배열의 원소를 모두 담아내었다면 긴 배열의 길이만큼 1을 추가하여 비교하였다. 값 갱신은 Bool 변수를 사용하여 두 원소가 모두 2일 경우에는 갱신을 하지 않는 방법으로 탐색하였다.

스위프트에는 기본적으로 제공되는 덱 구조가 없어서 배열을 사용하여 insert(_ newElement:Int , at:Int)를 사용했다. 시간 초과가 걱정되었지만 각 입력 배열의 길이가 최대 100으로 짧은 편에 속했고, 시간도 넉넉했기에 통과할 수 있었다. 이후 더 빠른 동작이 가능한지 궁금하여 배열을 합치는 방식으로 바꾸어 보았지만 큰 차이는 없었다.

정답 코드

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

dp문제다. 완전 탐색으로 시도했지만 역시나 시간 초과. 점화식을 생각해내는 데에 시간이 걸렸던 문제다.

풀이

최소한의 정사각형을 만들 수 있는 칸부터 시작해야 한다. 2차원 배열 map에 대해서 x와 y의 값이 모두 1 이상이고 map[x][y]의 값이 0보다 커야 한다. 해당 좌표의 상, 좌, 좌대각선 칸 중 최솟값 + 1로 갱신해나가면 된다.

map[x][y] = min(min(map[x-1][y], map[x][y-1]), map[x-1][y-1]) + 1

정답 코드