신발끈 공식을 이용하여 풀었다. 다각형을 이루는 모든 꼭지점의 좌표를 알면 좌표를 이용해 다각형을 여러 개의 삼각형으로 쪼개 넓이를 구하는 공식이다.
다각형의 넓이 = ABS(sum1 - sum2) / 2
꼭지점이 시계방향 혹은 반시계 반향으로 순차적으로 주어지게 될 경우, 다음과 같이 순환하는 형태로 줄지어 격자 형태로 곱해서 나온 누적합 sum1, sum2의 차를 2로 나누면 다각형의 넓이를 구할 수 있다. 다행히도 문제에 다각형을 이루는 꼭짓점의 순서대로 입력이 되기에 입력되는 순서 그대로 배열에 담아내면 손쉽게 답을 구할 수 있다.
swift에서는 자릿수 반올림 함수가 제공되지 않으므로 원하는 자릿수에서 반올림 하기위해 직전 자릿수까지 10을 곱해준 뒤 반올림 함수 round()를 이용하였고 다시 자릿수만큼 나누어 주었다.
해당 질문은 첫 iOS 개발 면접에서 마주했던 질문이라 기억에 강하게 남아있는 질문이다. 우선 swift 레퍼런스 문서를 보면 다음과 같이 정의를 찾을 수 있다.
Frame
The frame rectangle, which describes the view’s location and size in its superview’s coordinate system.
Bounds
The bounds rectangle, which describes the view’s location and size in its own coordinate system.
Declaration
var bounds: CGRect { get set }
두 개념 모두 뷰의 위치와 사이즈를 반환하는 CGRect 타입 변수이다.
하지만 frame은 해당 뷰가 속해있는 상위 뷰의 좌표계를 기준으로 정해진 크기와 좌표이고, bounds의 경우는 자기 자신의 좌표계를 기점으로 정해진 크기와 좌표이다.
What is View?
UIView
An object that manages the content for a rectangular area on the screen.
뷰가 무엇인지부터 설명하자면 사용자의 앱 위에 그려지게 되는 Label, Switch, Button들과 같은 요소들을 모두 view라고 정의한다. SwiftUI 혹은 UIKit을 통해서 생성할 수 있으며, 이러한 뷰들은 UIView라는 클래스로 생성된 객체들이다. 해당 객체들을 통해 유저와의 상호작용이 가능하다.
Create a View
let rect = CGRect(x: 10, y: 10, width: 100, height: 100) let myView = UIView(frame: rect)
뷰를 생성하기 위해선 크기와 좌표가 필요하며 이러한 좌표와 크기는 CGRect라는 형태로 표현된다. 크기와 좌표가 주어지면 해당 조건에 맞게 화면 위에 그려지게 되는 것이다.
CGRect
A structure that contains the location and dimensions of a rectangle.
Creating Rectangle Values
init(origin: CGPoint,size: CGSize)
Creates a rectangle with the specified origin and size.
Creates a rectangle with coordinates and dimensions specified as floating-point values.
init(x: Int, y: Int, width: Int, height: Int) Creates a rectangle with coordinates and dimensions specified as integer values.
init(x: CGFloat, y: CGFloat, width: CGFloat, height: CGFloat) Creates a rectangle with coordinates and dimensions specified as CGFloat values.
그렇다면 CGRect는 무엇일까? 위에서 얘기했듯이 뷰의 크기와 좌표계를 담는 구조체이며, 초기화하는 방법에는 여러 가지 방법이 있지만 기본적으로 CGFloat이라는 실수 형태의 자료형을 통해 크기와 좌표를 표현한다.
여기서 CG는 CoreGraphics의 약자로 그래픽 관련 즉 화면 표현에 대한 자료들은 모두 CG로 시작하는 자료형을 사용하니 알아두면 처음 보는 자료형에 대해서도 어떠한 용도로 쓰이는지 유추할 수 있다.
iOS의 좌표계 시스템은 뷰의 좌측 상단이 원점(0,0)이며, 화면의 수직면이 y 축이며 수평면이 x 축이다. 즉 y값이 증가하게 되면 아래로 이동하고 x값이 증가하게 되면 우측으로 이동하게 된다. 뷰에 관한 자세한 설명은 해당 글에 따로 정리해두었다.
frame과 bounds의 사이즈는 항상 똑같은가?
직관적으로 둘의 차이점에 대해 알 수 있는 예시이다. B가 기울어진 상태에서 frame의 경우, 상위 뷰 A의 좌표계에서 차지하는 크기는 좌표를 기준으로 사각형을 그려 표현하게 때문에 B의 frame은 Point(140, 65), Size(320, 320)이 반환되며 bounds의 경우 Point(0,0), Size(200,250)이 반환된다.
결론
frame : 상위 뷰의 좌표계 기준으로 좌표 원점과 크기를 반환 bounds : 자기 자신의 좌표계 기준으로 좌표 원점과 크기를 반환
그래프 탐색 문제다. 너비 우선 탐색으로 풀었다. 상어의 움직임에 대해 오래 고민했던 문제다.
풀이
상, 좌, 우, 하 순서로 너비 우선 탐색을 수행한다. 빈 곳이거나 같은 사이즈의 물고기를 만난다면 큐에 담아 이동을 수행, 자신보다 작은 사이즈의 물고기를 만나면 해당 좌표를 다른 배열에 저장하였다.
탐색이 끝난 뒤 문제의 조건에 맞게 먹을 수 있는 물고기가 담긴 배열을 시간, x좌표, y좌표 순으로 정렬한 뒤 가장 가까운 좌표로 이동하여 해당 물고기를 먹으면 된다. 처음에는 이러한 정렬 없이 먹을 수 있는 물고기를 만나면 바로 먹어버리고 탐색을 종료했는데, 같은 거리에 있는 먹을 수 있는 물고기에 대한 조건이 안 맞아 오답이 나왔다.
탐색 함수는 상어가 이동한 좌표와 걸린 시간을 반환하게 하였다. 상어의 좌표에 이동이 없는 경우 먹을 수 있는 물고기가 없는 것으로 판단하여 반목문을 빠져나오는 것으로 코드를 작성했다.
0부터 9999에 해당하는 움직임을 담는 문자열 배열을 생성한 뒤, 입력되는 A부터 시작하여 너비 우선 탐색을 수행한다. D, S, L, R 연산에 해당하는 숫자를 만들고 해당 인덱스의 배열에 현재까지의 움직임에 해당 움직임 문자열을 더하여 탐색을 수행한 뒤 탐색이 끝나면 B인덱스의 배열 값을 출력하면 된다.
정답 코드
시간초과를 마주하여 조금 더 동작을 빠르게 해결하기 위해 27번 라인에 B번째 배열의 값이 갱신되면 탐색을 곧바로 종료하는 조건을 추가하였다.
백트래킹 대표 유형 문제다. 예전에 시도했던 문제지만 시간제한에 걸려 풀지 못했던 문제다. 결국 다른 분의 풀이를 확인하고 풀 수 있었다.
풀이
해당 문제는 같은 행과 열, 그리고 우측에서 좌측으로 내려오는 대각선과 좌측에서 우측으로 내려오는 대각선이 겹치는지 확인하여 N번의 조건을 백트래킹을 통해 풀어야 한다. 단순하게 매 횟수마다 2차원 배열의 true false를 통해 조건을 탐색하게 된다면 시간 초과가 일어나게 된다.
이번 풀이는 열, 좌측 하행 대각선, 우측 하행 대각선을 담당하는 Bool 타입 1차원 배열을 각각 따로 생성하여 조건을 확인하는 방법이다. 행에 대한 배열이 없는 이유는 한 행에 하나의 퀸만 놓을 수 있기에 따로 퀸을 놓게 되면 바로 다음 행으로 넘어가기 때문이다.
N = 4일 경우의 각 배열의 양상이다. 2차원 보드판 위치의 기준으로 각 배열에 확인해야 하는 인덱스를 넣어 놓았다. 3가지 배열 모두 해당 인덱스에 퀸이 없을 경우에만 퀸을 배치하고 다음 열로 넘어가게 된다.
지도를 탐색하면서 인접 배열과의 인구수를 비교, 조건에 맞다면 큐에 담아낸 뒤 마지막에 큐에 담겨있는 좌표를 확인하면서 값을 갱신한다. 문제에서는 몇 차례의 변동이 일어났는지 횟수를 요구하기 때문에 반복문으로 수행한 뒤 Bool 타입의 flag 변수를 사용하여 종료 여부를 확인하였다.
