코딩 테스트
[Swift] - 프로그래머스 짝지어 제거하기
출처: 프로그래머스 [짝지어 제거하기] https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는..
행렬의 곱셉 구하기 문제 - swift
arr1 1 4 3 2 4 1 arr2 3 3 3 3 일때 행렬을 곱셈하여 [[15,15],[15,15],[15,15]]을 출력하는 함수를 작성하기 이번 문제는 행렬 A와 행렬 B가 주어졌을 때 그 곱을 구하는 문제이다. 삼중 반복문을 써야되는 점에서 시간복잡도가 크지 않을까라는 걱정을 했는데 다른 분들도 이 방법을 많이 사용하신 것 같았다. 인덱스가 세개가 되니 어떤 인덱스를 이용해서 행렬을 완성시켜야하는지 굉장히 머리가 아팠었다.. 이 문제를 해결하기 위해서 우선 행렬들을 하나하나 직접 인덱스를 적었다. 가령 답이 2*2 행렬이라면 00 01 10 11 -> 이런 형태의 행렬이 될텐데, 2*2와 2*2의 행렬을 곱할때는 00 01 00 01 10 11 10 11 00 = 00*00 + 01*10 01..
코딩 테스트 - [백준 1931] 회의실 배정(탐욕 알고리즘)
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 예제 입력 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 예제 출력 4 문제 해결 과정 이 문제는 회의가 끝나는 시간을 기준으로 배열을 정렬한다. 만약 끝나는 시간이 같은 것이 있다면 시작 시간이..
코딩 테스트 - [백준 11047: 동전] (탐욕 알고리즘)
문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 6 나의 답안: var coinArr = [Int]() v..
코딩테스트 - Swift Array, Set, Dictionary 관련 함수 시간 복잡도
Array append(_ newElement: Element) 평균 시간 복잡도는 O(1)입니다. 최악의 시간복잡도 O(N)입니다. 최악의 상황은 메모리를 재할당 해야 할 때입니다.(C++ Vector와 유사, exponential로 크기가 증가합니다.) append(contentsOf:) 평균 시간 복잡도는 O(M)입니다.M은 새로운 Elements의 개수입니다. insert(_ newElement: Element, at i: Int) O(N)입니다. i가 마지막 index일 경우, append와 시간 복잡도가 같습니다. count O(1)입니다. subscript(_:) read는 항상 O(1), write는 일반적으로 O(1)입니다. NSArrary와 brideged 됐을 경우나 다른 arrary..
코딩테스트 - [백준: 10815] 숫자 카드(이진 탐색)
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다 출력 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해..
