17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 배열에서 자기 자신보다 오른쪽에 있는 가장 가까운 큰 수를 찾는 문제이다. 처음 구현한 방법은 이중 for문을 활용하였으나, 배열의 크기가 클 땐 O(n^2) 의 시간복잡도를 감당할 수 없어 시간초과가 나왔다. 실패 코드 import Foundation let n = Int(readLine()!)! var numbers = readLine()!.split { $0 == " " }.map { Int(String($0))! } var result : [Int] = [] for ..

1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 긴 문자열 속에서 특정 문자열을 찾아내는 알고리즘이다. Knuth Morris Pratt의 앞글자를 따왔으며, 1번부터 특정 문자열의 길이만큼 접근하는 일반적인 탐색법은 시간 복잡도가 O((n-m)n)이지만, KMP 알고리즘을 활용하면 O(n + m)의 복잡도로 시간을 단축시킬 수 있다. 1. 파이 테이블 생성 사실 KMP 알고리즘은 특정 문자열에 한 번, 그리고 이를 통해 만들어진 파이 테이블을 바탕으로 전체 문자열에 한 번 적용하여 총 두 번 쓰인다. ..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 좀 더 클린한 코드로 리팩토링이 필요해보이나, List와 DFS 개념을 활용하여 해결하였다. 방문 배열을 만들어주고, 정상인의 경우와 적녹색약인 경우 각각의 함수를 정의하지 않고, 정상인일 경우를 해결한 후에 적색을 녹색으로 변경하여 다시 한번 깊이 우선 탐색을 돌려주었다. import sys sys.setrecursionlimit(10 ** 9) n = int(input()) arr = list() for _ in range(n): arr.append(l..

1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 추가하는 건 맨 뒤에서, 빼는 건 양쪽 방향에서 해줄 수 있는 큐가 필요하다. 덱(double ended queue)을 구현해주면 되는데, 해당 문제에서는 양방향으로 추가해줄 필요가 없어서 기존에 구현했던 큐를 일부 수정, 변형하였다. 회전하는 큐 구현 struct Queue { var left = [Int]() var right = [Int]() var count: Int { left.count + right.count } var isEmpty: Bool ..

Swift같은 개발 언어 중에는 힙, 큐, 덱같이 기본적으로 다른 언어에서 제공해주는 라이브러리가 따로 있지 않다. 따라서 직접 구현해줘야 한다. 알아야 될 것 1. 완전 이진트리로 부모 노드를 탐색하려면, 시작 인덱스를 1부터 시작해야 한다. 2. 힙은 우선순위 큐를 위한 자료형이다. 3. 우선순위 큐의 목적은 값을 추가할 때 부모 노드에 최댓값 or 최솟값을 넣기 위함이다. 4. 따라서 입, 출력을 할 때만 연산이 수행되고, 전체 힙의 값을 확인하면 오름차순이나 내림차순으로 정렬되지 않을 수 있다. struct Heap { var heap: Array = [] // 초기화 1. 아무 것도 넣지 않을 때 init() { } // 초기화 2. 시작부터 넣을 때 init(_ data: [Int]) { he..

1차원 리스트 정렬 arr = [5, 3, 7, 3, 6, 1, 2] arr.sort() # 오름차순 정렬 output: [1, 2, 3, 3, 5, 6, 7] arr.sort(reverse= True) # 내림차순 정렬 output: [7, 6, 5, 3, 3, 2, 1] 2차원 리스트 정렬 arr2 = [[1, 3], [2, 2], [5,3], [4, 2], [2, 2], [1, 5]] arr2.sort() # 오름차순 정렬. 부분 배열의 인덱스 별 우선 순위를 가지고 오름차순으로 정렬 # output: [[1, 3], [1, 4], [1, 5], [2, 2], [2, 2], [4, 2], [5, 3]] arr2.sort(reverse= True) # 내림차순 정렬. 부분 배열의 인덱스 별 우선 순위..

18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 1. 큐 구현 FIFO(First In First Out) 구조의 Queue는 Swift에서 기본적으로 제공되지 않기에 따로 구현을 해줘야한다. 추가) 왼쪽 배열에 추가 삭제) 오른쪽 배열에 값이 존재하면, 오른쪽의 마지막 값을 제거오른쪽 배열에 값이 없으면, 왼쪽 배열을 뒤집어(reversed) 오른쪽 배열에 할당 후 왼쪽 배열 삭제 struct Queue { var left = [Int]() var right = [Int]() // 큐..

1. 기본 PS를 할 때 기본적으로 사용되는 입출력이다. # 입력 # str, 문자열이 그대로 출력 a = input() # int, 문자열을 정수형으로 변경 a = int(input()) # list, 문자열을 문자(char) 리스트로 변경 a = list(input()) # list, 문자열을 공백으로 구분하여 문자열(str) 리스트로 변경 a = input().split() # list, 문자열을 공백을 구분하여 정수형 리스트로 변경 a = list(map(int, input().split)) # 복수 할당(공백을 구분하여 각각의 정수를 할당) a, b, c = map(int, input().split()) # 출력 # 기본 출력 print(a) # 배열을 "주어진 문자열"로 구분하여 합친 문자열로..