Array 문제 풀이 두 번째 시간!
1. Rotate Array
배열을 회전시킨다...? 무슨 뜻일까..
회전이라기 보다는 배열의 마지막 원소를 가장 맨 앞으로 옮기는 작업 요구하고 있다!
(k의 수 만큼 원소들을 이동해줘야 한다.)
// k = 3
[1,2,3,4,5,6,7,8]
// [6,7,8,1,2,3,4,5] 가 된다.
// [8,1,2,3,4,5,6,7]
// [7,8,1,2,3,4,5,6]
// [6,7,8,1,2,3,4,5]
// 위 프로세스로 수행이 되는 형태이다!하나씩 옮기면 될 것 같은 생각이 든다.
class Solution {
func rotate(_ nums: inout [Int], _ k: Int) {
// k가 0이면 움직일 필요 없음
if (k == 0) { return }
// k만큼 옮겨야하기에 k만큼 돌아준다.
for _ in 0..<k {
// 마지막 원소 추출하여 맨 앞에 위치하도록
nums.insert(nums[nums.count-1], at: 0)
// 앞으로 복사했던, 마지막 위치의 원소 삭제
nums.remove(at:nums.count-1)
}
}
}
[ 프로세스 ]
1. k가 0인 경우는 기존 배열 그대로 리턴
2. k만큼 돌면서!
3. 마지막 위치의 원소를 가장 앞에 추가하고
4. 마지막 위치의 원소를 삭제시킨다.
5. 반복이 종료되면 자동으로 배열 리턴 ( inout 파라미터 사용했기 때문에 기존 배열이 변경된다. )
(+)
처음에 이렇게 풀이를 했는데, 다른 풀이를 보고 아이디어가 아주 좋다고 생각했다..
원리는 다음과 같았다.
// k = 3
[1,2,3,4,5,6,7,8]
// 1. 배열을 먼저 뒤집는다.
[8,7,6,5,4,3,2,1]
// 2. 앞에서 부터 k만큼 다시 뒤집는다.
[6,7,8 | 5,4,3,2,1]
// 3. 나머지(배열 총 길이 - k) 수 만큼 다시 또 뒤집는다.
[6,7,8 | 1,2,3,4,5]
코드로 봐보자!
( + reverse라는 함수를 새로 정의해줬다. )
class Solution {
// 메인 풀이 함수
func rotate(_ nums: inout [Int], _ k: Int) {
// k의 크기가 배열의 수 보다 클 수 있어 range 조정하기 위함
var k = k % nums.count
// rotate할 기준 index 설정
var index = nums.count - k
// 배열이 [ 1,2,3,4 | 5,6,7 ] 일 때 (k=3)
// index 기준으로 앞에 까지 먼저 rotate 한다
reverse(&nums, 0, index - 1)
// [4,3,2,1 | 5,6,7]
// 뒷 부분 rotate
reverse(&nums, index, nums.count - 1)
// [4,3,2,1 | 7,6,5]
// 전체 rotate
reverse(&nums,0,nums.count-1)
// [5,6,7,1,2,3,4]
}
func reverse(_ array: inout [Int], _ low: Int, _ high: Int) {
// 값 수정 가능하도록 var로 정의
var low = low
var high = high
// 만날 때 까지
while low < high{
// temp에 최솟값 저장해두기
var temp = array[low]
// low에 최댓값 할당
array[low] = array[high]
// high에 최솟값 할당
array[high] = temp
// 다음 index로
low += 1
high -= 1
}
}
}
배열을 잘라서 일부 먼저 rotate하고 전체를 rotate한다는 것이 신선하게 다가왔다..!
이 방법이 메모리 사용량이나, 런타임에서 우월했다!
2. Contains Duplicate
배열 내 원소가 중복된 값을 가지고 있는지 파악해보는 것이 포인트인 문제.
중복된 값이 있을 때 true, 없을 때 false를 반환하면 된다.
// Case 1
[1,2,3,1] // true
// Case 2
[1,2,3,4] // false
그렇게 어렵지 않아보이기에 바로 코드를 봐보자!
class Solution {
func containsDuplicate(_ nums: [Int]) -> Bool {
// 중복값 제거 메서드 적용 후 개수에 변화가 있는지 확인
return nums.count != Set(nums).count
}
}코드는 간결하나, 테스트 케이스 마다 런타임이 조금 다르게 나오는 것 같다.
프로세스 쓰기에도 너무 간단해서 이건 패스!
3. Two Sum
배열 내 두 원소의 합의 결과가 타겟과 같게하는 원소들의 index 값들을 뽑아내는 문제이다.
말이 조금 헷갈리는 것 같은데 아래 예시를 봐보자
// Case 1, target = 6
[3,2,4]
// 2 + 4 = 6 , return [1,2]
// Case 2, target = 9
[7,2,11,15]
// 7 + 2 = 9, return [0,1]여기에 조건이 하나 더 붙는데, "답은 무조건 하나"라는 것이다.
즉 다른 숫자들을 더해서 target이 되는 경우는 없다는 것이다. 그렇기에 답이 되는 한 쌍만을 찾아 그 index를 반환하면 된다.
코드로 봐보자!
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
let cnt = nums.amount
// 경우의 수를 따지기 위해 for문을 돈다
for i in 0..<cnt {
for j in i+1..<cnt {
// 수를 하나씩 더해보며 target과 일치하는지 확인 후
if (nums[i] + nums[j] == target) {
// target과 같을 경우 인덱스를 반환한다.
return [i,j]
}
}
}
// 답이 없을 경우
return [0,0]
}
}
[ 프로세스 ]
1. 먼저 전체 길이를 구한다.
2. 길이 만큼 돌면서 경우의 수를 다 세본다.
3. 수들을 더해보며 target과 합이 같아지는 경우에 indices를 반환한다.
4. 답이 없을 경우는 [0,0] 반환!
4. Single Number
배열을 줬을 때, count가 1개인 원소를 구하는 문제이다. 배열 내의 원소는 2번 혹은 1번씩만 등장 가능하다!
아래의 케이스들을 봐보자.
class Solution {
func singleNumber(_ nums: [Int]) -> Int {
// 빈 딕셔너리를 만든다.
var dictNums: [Int:Int] = [:]
// count가 1개인 값을 찾기 위해 빈 값 생성
var res = 0
// nums의 갯수를 세기 위해 원소가 등장할 때 마다 dict에 값을 1씩 올려줌
for n in nums {
// nil일 경우 0으로
dictNums[n] = (dictNums[n] ?? 0 ) + 1
}
// key, value쌍에서 value가 1일 때 key값을 결과값으로 가져온다.
for (k,v) in dictNums {
if (v == 1) {
res = k
}
}
return res
}
}
[ 프로세스 ]
1. 빈 딕셔너리를 생성한다.
2. 결과값을 저장하기 위한 변수 생성
3. 빈 딕셔너리를 활용하여 key와 value(등장시 +1) 추가
4. 저장한 key,value쌍에서 value가 1일 때의 key를 선택
5. 결과값 반환
위 프로세스로 풀이했는데, 해당 방법이 아닌 기존 배열과 index를 활용한 방법으로 해봤는데, 더 효율적이진 않은 것 같다.
class Solution {
func singleNumber(_ nums: [Int]) -> Int {
// 먼저 배열을 정렬한다. (오름차순, 내림차순 상관X)
var nums = nums.sorted()
// index 설정
var index = 0
// 배열의 길이까지 돈다.
while index < nums.count {
// index가 마지막에 다다랐을때 혹은 현재 값과 이후 값이 다를 때
if (index == nums.count-1) || (nums[index] != nums[index+1]) {
// 그 때 값을 반환해준다.
return nums[index]
}
// 최대 등장 횟수가 2이기에, 아닌 경우에 index를 2만큼 증가시켜 다음 원소로 이동
index += 2
}
// 답이 없을 경우
return 0
}
}
[ 프로세스 ]
1. 배열을 정렬한다.
2. index값 설정
3. 배열의 끝까지 돌면서
4-1. index가 끝까지 갔거나, 혹은 현재 값과 그 다음값이 다를 때 해당 값을 리턴한다.
4-2. 그렇지 않을 경우 index += 2 (최대 등장 횟수가 2이기에 두 칸씩 뛰어넘어야 함!)
5. 답이 없을 경우 0 리턴