Array 파트 마지막 풀이!
------------------
1. Best Time to Buy and Sell Stock II
주식을 사고 파는데 있어 저점에 사서 고점에 팔아 최대 이익을 남기기 위한 문제!
다음 원소의 가격보다 싸면 사서 팔아주면 된다!
바로 코드로 봐보자.
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
// 결과값 저장을 위한 변수 생성
var total = 0
var cnt = prices.count
// 배열을 돌면서 저점 매수 고점 매도 진행
for i in 1..<cnt {
if prices[i-1] < prices[i] {
total += prices[i] - prices[i-1]
}
}
return total
}
}
[ 프로세스 ]
1. 결과값 저장을 위한 Int 객체, 배열의 길이 객체를 생성
2. 배열을 돈다
2-1. 이전 원소가 그 다음 원소보다 작을 때
2-2. (i원소값 - (i-1)원소값) 이익을 결과값에 추가
2. Intersection of Two Arrays II
두 배열의 교집합을 구하는 문제!
주의해야할 부분은 중복된 원소들도 잘 골라내야한다는 점.
그렇기에 딕셔너리의 Key와 Value로 접근하였다.
코드로 봐보자.
class Solution {
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
// nums1을 기준으로 Key와 Value 세팅
var standNums = Dictionary(nums1.map {($0, 1)}, uniquingKeysWith: +)
// 결과값 저장을 위한 빈 배열
var res: [Int] = []
// nums2를 돌면서
for n in nums2 {
// standNums[n]은 optional이기 때문에 value를 미리 unwrapping 해둔다.
if let num = standNums[n], num > 0 {
// num이 존재하고 0이상일 경우, 결과값에 추가
res.append(n)
// 결과에 추가하였으니 기존 배열에서 frequency를 1 감소 시키기
standNums[n] = num - 1
}
}
return res
}
}
[ 프로세스 ]
1. nums1을 기준으로 Dictionary인 StandNums를 생성한다.
2. 결과값 저장을 위한 res 배열을 생성
3. nums2의 원소를 돌면서
3-1. standNums에 n이 존재하고, 값이 1 이상일 때
3-1-1. 결과값에 n을 추가하고
3-1-2. 중복된 값을 뽑지 않도록 standNums[n]의 값을 1 내려준다.
4. res 리턴
3. Valid Sudoku
주어진 스도쿠가 풀 수 있는 것인지 확인하는 문제이다.
같은 줄(행,열)에 중복되는 숫자가 없는지, 박스안에 같은 수가 없는지 확인하는 것이다.
스도쿠의 룰은 알 것 이라고 생각하고 아래의 코드를 봐보자.
엄청 복잡하고, 좋아보이지 않는 코드로 짰지만... 개선한 버전도 이후에 봐보자.
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
return rowCheck(board) && colCheck(board) && matCheck(board)
}
// 행 체크
func rowCheck(_ board: [[Character]]) -> Bool {
var row = true
for i in 0..<9 {
// "."인 것은 필터링
var rowCheck = board[i].filter {$0 != "."}
// 중복값 제외시 수가 다를 경우 false
if rowCheck.count != Set(rowCheck).count {
row = false
// 미리 탈출!
return row
}
}
return row
}
// 열 체크
func colCheck(_ board: [[Character]]) -> Bool {
var col = true
// 열 체크를 위해 for문 두 번 돌기
for i in 0..<9 {
// 각 열 마다 배열 초기화
var newCol = [Character]()
for j in 0..<9 {
// "."이 아닌 것 배열에 추가
if board[j][i] != "." {
newCol.append(board[j][i])
}
}
// 행과 똑같이 길이로 비교
if newCol.count != Set(newCol).count {
col = false
// 미리 탈출!
return col
}
}
return col
}
// 박스 내 숫자 비교
func matCheck(_ board: [[Character]]) -> Bool {
var mat = true
// 3칸씩 이동
for i in stride(from:0, to: 9, by: 3 ) {
for j in stride(from:0, to:9, by: 3) {
var matCheck = [Character]()
for m in i..<i+3 {
for n in j..<j+3 {
if board[m][n] != "." {
matCheck.append(board[m][n])
}
}
}
if matCheck.count != Set(matCheck).count {
mat = false
// 미리 탈출!
return mat
}
}
}
return mat
}
}
조금 주먹구구식으로 풀이한 것 같긴하나..! 봐보자.
프로세스를 보기 이전에, 행/열/박스 내 중복값을 체크하는 방식은 동일하다는 점 참고!
[프로세스]
1. isValidSudoku는 각 3개의 함수들의 반환값들의 && 연산 결과를 반환한다.
(즉 하나라도 false일 경우 false)
2. rowCheck는 board의 행들을 체크한다.
2-1. filter를 통해 "."를 제외하고 모든 숫자들을 배열에 담는다.
2-2. 기존 배열과 중복값을 제외한 배열의 길이가 다르면 false 처리
3. colCheck는 board의 열들을 체크한다.
3-1. if문을 통해 "."를 제외하고 모든 숫자들을 배열에 담는다.
3-2. 기존 배열과 중복값을 제외한 배열의 길이가 다르면 false 처리
4. matCheck는 board의 박스들을 체크한다.
4-1. 3칸씩 이동해야 하기 때문에 stride를 사용하여 3씩 이동한다.
4-2. if문을 통해 "."를 제외하고 모든 숫자들을 배열에 담는다.
4-3. 기존 배열과 중복값을 제외한 배열의 길이가 다르면 false 처리
해당 값이 어느 박스에 해당하는지를 알아냄으로써 조금 더 개선할 수 있는 것 같다.
for i in 0..<9 {
for j in 0..<9 {
var boxNum = (i / 3) * 3 + j / 3
// 0,0일 때는 0번째 박스
// 2,5일 때는 1번째 박스
// 7,8일 때는 8번째 박스!
}
}
이후에 조금 더 알아보자.
-----------------------
이렇게 Array를 모두 풀이했다. 이제 String으로 넘어가보자!