Hyun's_Devlog

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

정답 코드

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

구현 문제에 해당한다. 홍준이의 이동방향을 어떻게 구현할지 고민했던 문제다.

풀이

시작지점이 지도의 어느 부분인지 알 수 없다. 따라서 시작 지점에서 최대 이동 범위인 50칸을 상하좌우로 확장한 상태에서 시작하여 지도를 그려낸 뒤 방문했던 x, y값의 최대, 최소 좌표 영역을 출력했다. 

미로 탐색 부분의 구현은 BFS를 사용할 때 자주 사용하던 dx, dy배열을 사용하여 "L"이나 "R"이 입력되면 배열의 인덱스를 변경하는 방법으로 구현했다.

정답 코드

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

그래프 탐색문색 문제로 BFS, DFS를 사용해서 풀어도 되지만 입력되는 바닥의 크기가 작고, 시간제한이 여유로운 편이어서 그래프를 x축 탐색, y축으로 탐색하여 개수를 세도 정답을 받을 수 있다.

풀이

Bool 타입의 flag변수를 사용하여 처음 마주하는 장식의 갯수를 세면 된다. 가로축 탐색은 처음 장식을 입력받을 때 수행하고, 이후 세로축으로 한번 더 탐색을 수행하면 된다.

정답 코드

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

1달 전에 오답인 상태로 방치했다가 다시 풀어본 문제다. 문제에 제시된 조건대로 구현만 하면 풀리는 문제다. 근데 집중해서 보지 않았는지 실수를 여러 번 남발해서 여러 번 시도했던 문제다. 처음엔 8가지 경우의 입력에 대해 switch 문으로 풀려했으나 코드가 너무 길어지기도 하고 코드가 길어지니 실수한 부분을 바로 찾기가 힘들었다. 설명문이 문제 자체를 이해하는 데에 실수를 유발하기 쉬운 문맥이기도 했다. 처음엔 돌과 킹이 동시에 움직이는 문제인 줄 알고 풀었고, 처음엔 둘 중 하나라도 움직일 수 없는 경우라면 둘 다 움직이지 않는 것으로 이해했었다. 결국 집중력이 부족해서 시간이 오래 걸렸던 문제다.

풀이

우선 해당 문제는 킹이 움직이는 문제다. 단, 킹이 돌이 있는 좌표로 움직이게 될 경우 돌은 킹이 움직이는 방향으로 똑같이 움직여야 한다. 추가적으로 돌이 만약 범위 밖의 좌표로 움직여야 한다면 해당 움직임은 취소. 당연히 킹도 제자리로 돌아가 다음 입력을 받아야 한다. 킹 혼자서 움직이는 경우 마찬가지로 범위 밖의 좌표로 이동해야 한다면 해당 이동은 취소다. 이번엔 문제에 대해 제대로 이해하고 각 움직임을 배열로 담아서 처리하였다. 

아스키코드로 세로좌표를 표현했다. 여기서 실수했던 점은 좌표에 대한 조건을 작성하는데 65(A)부터 72(H)까지 범위를 잡아야 했지만, 아무 생각 없이 65(A)부터 90(Z)까지 범위로 잡는 실수를 했다. 

정답 코드

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

탐색 종료 조건 부분에서 고생했던 문제였다. 처음에는 지도를 입력받을 때 빈칸의 개수를 세어놓고 빈칸이 0이 될 때까지 플레이어 순서대로 경로탐색을 수행하는 방법으로 시도했으나, 벽으로 둘러싸인 빈 공간의 가능성을 뒤늦게 깨달았다. 

풀이

각 플레이어에게 해당하는 경로탐색용 큐 Array(repeating: [[Int]](), count: p+1)를 생성하여 앞으로 방문해야할 공간의 좌표를 담아둔다. 이후 모든 플레이어의 큐가 비어있는 상태가 될 때까지 각 플레이어 턴마다 Si번 경로탐색을 수행하면 된다. 큐의 첫 수행 좌표는 지도를 입력받을 때 큐에 담아두면 된다. 

정답 코드

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

오답 판정으로 고생했던 문제. 다른 분의 풀이를 보니 접근 불가능한 문을 마주했을 때와 이후 열쇠를 얻어 방문할 수 있게 되는 부분에서의 처리방법이 달랐다. 

풀이

bfs를 수행할 때 크게 4가지 조건을 확인하면서 경로를 탐색해야 한다.

• 빈 공간을 마주한 경우
• 문서를 마주한 경우
• 문을 마주한 경우
• 열쇠를 마주한 경우

문서와 빈 공간의 경우 알맞게 처리하고 경로탐색을 수행하면 된다.

헤맸던 부분은 열쇠를 마주했던 부분이다. 문과 열쇠 각각 두 가지 경우로 다시 나뉜다.

• 열 수 있는 문을 마주한 경우 -> 그대로 경로 탐색 수행
• 열 수 없는 문을 마주한 경우 -> 해당 좌표를 담아두고 다음 경로 탐색
• 이미 얻었던 열쇠를 마주한 경우 -> 그대로 경로 탐색 수행
• 기존에 없던 열쇠를 마주한 경우 -> 기존에 마주했던 열 수 없었던 문들 중 해당 열쇠로 열 수 있는 문 좌표에 대해 경로 탐색 수행

기존의 코드는 맵을 입력받을 때 모든 문의 좌표를 담아두고 경로탐색 시 새로운 열쇠를 얻을 때마다 좌표를 담아두었던 배열을 돌며 탐색을 수행했었다. 문제는 그렇게 되면 벽으로 둘러싸여 도달할 수 없는 문의 경우를 매번 마주해야 하고, 이러한 예외처리를 해주어야 하는데, 거기서 부터 해결을 못해 오답 판정을 받았다.

그리고 또 한번 곤욕을 겪은 부분이 경로 탐색 시작 지점에 대한 부분이다. 처음엔 문제에서 주어진 대로 맵의 테두리만 돌면서 탐색 가능한 지점을 직접 찾는 코드를 적었다. 여기서부터 시작 가능한 지점에 대해서 다시 한번 위의 4가지 경우에 맞게 예외처리를 해주어야 했고 이렇게 되면서 코드 양도 많아지고 오답 판정을 받았을 때 찾아봐야 할 지점이 너무 많아서 해결을 못했다.

다른 분의 풀이에서 이 부분도 잘 해결한 모습을 찾을 수 있다. 입력받은 맵 주변에 빈 공간으로 한번 둘러주어 map[0][0]에서 경로를 탐색하게 되면 자연스럽게 4가지 조건에 대한 처리가 이루어지게 된다.

//입력된 지도				
*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*
.	.	.	.	.	.	.	.	.	.	.	.	.	*	*	$	*
*	B	*	A	*	P	*	C	*	*	X	*	Y	*	.	X	.
*	y	*	x	*	a	*	p	*	*	$	*	$	*	*	$	* 
*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*
						
//테두리 추가
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	*	*	$	*	.
.	*	B	*	A	*	P	*	C	*	*	X	*	Y	*	.	X	.	.
.	*	y	*	x	*	a	*	p	*	*	$	*	$	*	*	$	*	.
.	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.

정답 코드