Summary
- 실제 시간에 맞춰 푼 문제
[0] 성격 유형 검사하기 (100/100)[0] 두 큐 합 같게 만들기 (50.0/100) - 시간초과[0] 행렬과 연산 (100/100) (1/9) - 효율성 빵점
- 시간 제한 없이 풀어서 푼 문제
-
- 풀었든 못풀었든 해당 문제 어떻게 접근했는지
[X] 등산코스 정하기[O] 코딩 테스트 공부 (풀다 맘)
Lv1. 성격 유형 검사하기
문제) 2022 KAKAO TECH INTERNSHIP - 성격 유형 검사하기
접근방식
- 분석 노트 배열을 만든다.
/* | A3| A2| A1| A0| N1| N2| N3| | C3| C2| C1| C0| F1| F2| F3| | M3| M2| M1| M0| J1| J2| J3| | R3| R2| R1| R0| T1| T2| T3| | N3| N2| N1| N0| A1| A2| A3| */ for s in survey { // "AN" let type1 = String(s.prefix(1)) // "A" let type2 = String(s.suffix(1)) // "N" var note = "" for index in 1...7 { note += index < 5 ? type1 + "\(4 - index) " : type2 + "\(index - 4) " } analyzeNote.append(note) }
- 분석노트에서 choices 배열값을 매칭시킨 항목의 배열을 만든다.
[5, 3, 2, 7, 5] /* | A3| A2| A1| A0| "N1"| N2| N3| | C3| C2| "C1"| C0| F1| F2| F3| | M3| "M2"| M1| M0| J1| J2| J3| | R3| R2| R1| R0| T1| T2| "T3"| | N3| N2| N1| N0| "A1"| A2| A3| */ for (i, val) in analyzeNote.enumerated() { var note = val.components(separatedBy: " ") note.removeLast() essenceNote.append(note[choices[i] - 1]) } essenceNote = ["N1", "C1", "M2", "T3", "A1"]
- 답변값을 반영한 배열을 통해 dictionary를 만든다.
["N1", "C1", "M2", "T3", "A1"] // 딕셔너리 생성 for e in essenceNote { let type = String(e.prefix(1)) // N let score = String(e.suffix(1)) // 1 // if dict[type] != nil { dict[type]! += Int(score)! } else { dict[type] = Int(score) } } // 만들어진 dictionary ["N": 1, "C" : 1, "M" : 2, "T" : 3, "A" : 1, ]
- 성격유형을 지표 순서대로 만든 배열을 돌면서 결과배에 추가 -> 결과배열을 joined한 후 문자열을 return
let personalities = ["RT", "CF", "JM", "AN"] // 딕셔너리 생성 for p in personalities { let type1 = String(p.prefix(1)) // "A" let type2 = String(p.suffix(1)) // "N" // 앞 유형, 뒤 유형 빈도수 let type1Score = dict[type1] ?? 0 let type2Score = dict[type2] ?? 0 // 앞 유형의 빈도수가 더 높으면 앞 유형으로 판정 result.append(type1Score >= type2Score ? type1 : type2) } // 만들어진 결과 배열 result = ["T", "C", "M", "A" ] return result.joined() // "TCMA"
구현코드
import Foundation
//["AN", "CF", "MJ", "RT", "NA"] [5, 3, 2, 7, 5] "TCMA"
func solution(_ survey:[String], _ choices:[Int]) -> String {
let personalities = ["RT", "CF", "JM", "AN"]
var analyzeNote = [String]()
var essenceNote = [String]()
var result = [String]()
for s in survey { // "AN"
let type1 = String(s.prefix(1)) // "A"
let type2 = String(s.suffix(1)) // "N"
var note = ""
for index in 1...7 {
note += index < 5 ? type1 + "\(4 - index) " : type2 + "\(index - 4) "
}
analyzeNote.append(note)
}
for (i, val) in analyzeNote.enumerated() {
var note = val.components(separatedBy: " ")
note.removeLast()
essenceNote.append(note[choices[i] - 1])
}
var dict = [String: Int]()
for e in essenceNote {
let type = String(e.prefix(1))
let score = String(e.suffix(1))
if dict[type] != nil {
dict[type]! += Int(score)!
} else {
dict[type] = Int(score)
}
}
for p in personalities {
let type1 = String(p.prefix(1)) // "A"
let type2 = String(p.suffix(1)) // "N"
let type1Score = dict[type1] ?? 0
let type2Score = dict[type2] ?? 0
result.append(type1Score >= type2Score ? type1 : type2)
}
return result.joined()
}소요시간
45분 (문제 이해 - 10분, 접근 방식 - 5분, 구현 - 30분)
풀이결과
문제를 나누고 나눠서 생각해서 오래 걸렸다.
시간복잡도를 다시생각해봐야겠다.
하드코딩 할 수 있는 부분은 하드코딩을 사용하자.
초기화된 딕셔너리 활용을 했다면, 더 효율적인 코드가 되었을 것 같음.
Lv2. 두 큐 합 같게 만들기
문제) 2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기
접근방식
- queue1 요소들의 합과 queue2 요소들의 합을 구한다.
- 각각의 큐 요소들의 합을 구해서 홀수일 경우엔 바로 return -1
- 짝수인 경우에, 두 큐의 합이 다를 경우, 아래의 내용을 반복했다.
큐 요소들의 합이 큰 쪽의 항목을 제거하고, 작은쪽 큐에 해당 항목을 추가 시켜줬다.
- 반복 과정에서 큐의 요소이동이 몇번 일어났는지 세는 변수 count를 1씩 증가시켰다.
※ 반복하는 과정에서 count가 큐의 크기의 제곱 보다 커지면 return -1을 했다. (종료조건 추가)
구현코드
import Foundation
func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
var queue1Sum: CLong = queue1.reduce(0, +)
var queue2Sum: CLong = queue2.reduce(0, +)
var q1 = queue1
var q2 = queue2
var count = 0
// 두 배열의 총 합이 홀수일 경우, 반으로 쪼갤 수 없기 때문에 return -1
if (queue1Sum + queue2Sum) % 2 == 0 {
// 두 배열의 합이 다를 경우, 계속 반복
while queue1Sum != queue2Sum {
// 배열의 합 갱신
queue1Sum = q1.reduce(0, +)
queue2Sum = q2.reduce(0, +)
if queue1Sum > queue2Sum {
if let popElement = q1.first {
q1.removeFirst()
q2.append(popElement)
} else { return -1 }
} else {
if let popElement = q2.first {
q2.removeFirst()
q1.append(popElement)
} else { return -1 }
}
count += 1
if count >= (queue1.count * queue1.count) { return -1 }
}
return count - 1
} else { return -1 }
}풀이결과
45분 (문제 이해 - 5분, 접근 방식 - 10분, 구현 - 30분)
풀이결과
문제 이해와 구현은 쉬웠지만, 구현하는 과정에서 두 배열의 합이 다를때 계속 반복문을 돌리는 구조여서 탈출 조건을 설정하는 부분을 다시 고려해야 할것 같다. (시간초과가 반이었다.)
Lv3. 코딩 테스트 공부
문제) 2022 KAKAO TECH INTERNSHIP - 코딩 테스트 공부
복사한 코드
접근방식
- 문제의 알고력과 코딩력의 합을 오름차순으로 정렬
- 정렬된 문제 순서대로 배열을 돌리면서 (공부를 통해 능력을 얻는 시간, 문제를 풀어서 능력을 얻는 시간을 비교 한 후 시간을 갱신 하는 방향으로 가려 했으나... 풀면 풀수록 잘못된 것을 깨달음. (포기)
구현코드
import Foundation
func solution(_ alp:Int, _ cop:Int, _ problems:[[Int]]) -> Int {
let maxAlp = problems.map{$0[0]}.max()!
let maxCop = problems.map{$0[1]}.max()!
let alp = min(alp, maxAlp)
let cop = min(cop, maxCop)
let INF = 10000
var dp = Array(repeating: Array(repeating: INF, count: maxCop + 1), count: maxAlp + 1)
dp[alp][cop] = 0
for a in alp..<maxAlp+1 {
for c in cop..<maxCop+1 {
var flag = false
if a + 1 <= maxAlp {
dp[a+1][c] = min(dp[a+1][c], dp[a][c] + 1)
flag = true
}
if c + 1 <= maxCop {
dp[a][c+1] = min(dp[a][c+1], dp[a][c] + 1)
flag = true
}
if flag {
for problem in problems {
let (alp_req, cop_req, alp_rwd, cop_rwd, cost) = (problem[0], problem[1], problem[2], problem[3], problem[4])
if a >= alp_req && c >= cop_req {
let totalAlp = min(maxAlp, a + alp_rwd)
let totalCop = min(maxCop, c + cop_rwd)
dp[totalAlp][totalCop] = min(dp[totalAlp][totalCop], dp[a][c] + cost)
}
}
}
}
}
return dp[maxAlp][maxCop]
}소요시간
풀지 못함.
풀이결과
처음에는 반복문으로 될거라고 생각했지만, 오산이었다. (종료조건이 애매했음)
BFS인것 같긴 했으나, 구현하기는 어려웠다.
다른 알고리즘 같기도 했으나 역시 DP를 활용한 풀이가 많았다.
DP 점화식 세우는 공부를 해야겠다.
Lv3. 등산코스 정하기
문제) 2022 KAKAO TECH INTERNSHIP - 등산코스 정하기
이해 참고링크
접근방식
구현코드
// 업슴.
소요시간
풀지 못함.
풀이결과
문제에 그래프만 나오면 풀기 싫어진다.
그래프 문제를 쉬운거라도 차근차근 풀여봐야 할것 같다.
최대값을 찾는 거기에 dfs를 사용하나 했다. bfs를 사용한 풀이도 있었지만, swift풀이는 거의 힙을 썼다.
힙 공부를 해야겠다.
Lv4. 행렬과 연산
문제) 2022 KAKAO TECH INTERNSHIP - 행렬과 연산
이해참고링크
이해참고영상
접근방식
- ShiftRow는 rc에서 마지막 항목을 제거후, 맨 위에 올려주는 방식을 생각했다. -> 함수로 구현
- Rotate는 첫번째줄일경우, 마지막줄일 경우, 그 외 경우로 나눠서 배열을 재조정해야 겠다고 생각했다 -> 함수로 구현
- operations를 반복문을 돌리며,
"ShiftRow"일때는 -> shiftRow(_ rc:[[Int]]) 함수를 실행 "Rotate"일때는 -> rotate(_ rc:[[Int]]) 함수를 실행위 로직을 반복해 행렬을 갱신 시킨다.
구현코드
import Foundation
func solution(_ rc:[[Int]], _ operations:[String]) -> [[Int]] {
var result = rc
for op in operations {
if op == "ShiftRow" {
result = shiftRow(result)
} else {
result = rotate(result)
}
}
return result
}
// ShiftRow 함수
func shiftRow(_ rc:[[Int]]) -> [[Int]] {
var result = [[Int]]()
var temp = rc
if rc.count == 1 { return rc }
else {
let lastRow = temp[rc.count - 1]
temp.removeLast()
result += temp
result.insert(lastRow, at: 0)
}
return result
}
func rotate(_ rc:[[Int]]) -> [[Int]] {
var result = [[Int]]()
var temp = rc
for index in 0..<temp.count {
if index == 0 {
temp[0].removeLast()
// temp의 첫번째에 다음 줄의 첫번째 항목 넣기
temp[0].insert(rc[1][0], at:0)
} else if index == temp.count - 1 {
temp[temp.count - 1].removeFirst()
temp[temp.count - 1].append(rc[index - 1][rc[0].count - 1])
} else {
temp[index].removeLast()
temp[index].removeFirst()
temp[index].insert(rc[index + 1][0], at:0)
temp[index].append(rc[index - 1][rc[0].count - 1])
}
}
return temp
}소요시간
45분 (문제 이해 - 5분, 접근 방식 - 5분, 구현 - 35분)
풀이결과
정확성은 100점이 나왔으나, 효율성은 하나만 통과하고 끝.
효율성이 떨어질거라고 생각했으나, 역시였다.
dequqe와 로직이 필요했던 것 같다.
shiftRow는 카카오해설과 로직이 동일하게 구현했다. (이것때문에 효율성 하나 통과된것 같기도..)
Just Do It