1. 폰켓몬 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/1845

# 이해
# N마리 중에서 N/2마리를 선택.
# 이때 가장 많은 종류를 선택하고, 그때의 가짓수를 return
# nums의 길이는 10,000이므로 O(n^2)까지는 괜찮겠다. 프로그래머스는 10억에서 시간 초과가 발생하므로.

# 풀이
# nums+1(0부터 200,000) 크기의 visited 배열을 만든다.
# nums를 탐색하며, 방문하지 않은 포켓몬일 경우 result, cnt에 += 1 하고, 방문 처리한다.
# 매 탐색마다 cnt가 len(nums) // 2 이하인지 확인한다. 초과하면 result를 return 한다.

def solution(nums):
    return min(len(nums) // 2, len(set(nums)))

최초에는 방문 처리를 통해 최소 횟수로 최대 개수를 확보하려고 했다.

그러나 모든 포켓몬이 다른 종류인 경우 최대 방문 가능 횟수(`len(nums) // 2`) == 정답이다.

포켓몬의 종류가 `len(nums) // 2`보다 작은 경우 그것이 정답이다.

2. 완주하지 못한 선수 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/42576

최초 풀이 (정렬)

# 이해
# completion에 있지만, participant에 없는 사람 return
# 동명이인이 있을 수 있다.

# 풀이
# 정렬한다.
# 순서대로 나오지 않으면 즉시 return 한다.

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

더 나은 풀이 (hash 함수)

def solution(participant, completion):
    
    dic = {}
    tmp = 0
    
    for part in participant:
        dic[hash(part)] = part
        tmp += hash(part)
    
    for comp in completion:
        tmp -= hash(comp)
        
    return dic[tmp]

hash 함수의 성질을 이용한 풀이이다.

배열의 각 원소를 탐색하며, hash()로 생성된 고유 숫자를 더하고 빼면, 하나의 고유 숫자만이 남는다는 것을 응용했다.

3. 전화번호 목록 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42577

# 이해
# 어떤 번호가 다른 번호의 접두어인 경우 false
# 아니라면 true
# str.startswith() / str.endswith() -> Bool

# 풀이
# phone_book을 탐색하며, 딕셔너리에서 현재 단어가 없다면,
# 현재 단어를 1글자씩 tmp에 더해가며 딕셔너리가 True가 반환되는 것이 있는지 확인.
# 있으면 return 없으면 완성된 단어를 True로 갱신


def solution(phone_book):
    dic = {}
    
    for pb in phone_book:
        dic[pb] = 1
    
    for pb in phone_book:
        tmp = ""
        for pb_chr in pb:
            tmp += pb_chr
            if tmp in dic and tmp != pb:  # 여기서도 동일하게 'if' 사용
                return False
    
    return True

단어 배열을 탐색하며, 완성된 단어는 모두 방문 처리한다.

단어 배열을 다시 탐색하며, 각 단어를 이중 탐색한다.

한 글자씩 더해가며 딕셔너리에 있는 단어인지 판단한다.

이때, 한 글자씩 더해가다가 단어가 완성된 경우는 제외한다. 문제의 조건에 중복된 단어는 없기 때문이다

4. 의상 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42578

# 이해
# 패션 조합의 가짓수
# 하루에 최소 한 개의 의상
# 한 종류에서는 하나의 옷만 선택
# 모든 종류를 선택할 수도, 하나의 종류만 선택할 수도, 복수의 종류만 선택할 수도 있다.

# 풀이
# from itertools import combinations
# type별로 카운트 횟수를 딕셔너리에 기록함
# type에 대한 조합을 구함.
# 모든 조합에 대하여, type에 대응하는 카운트 횟수를 곱해 answer에 더함.
# answer 반환.

def solution(clothes):
    answer = 1  # 곱셈을 위해 1부터 시작
    dic = {}
    
    # 각 옷의 종류별로 개수를 계산
    for _, type in clothes:
        dic[type] = dic.get(type, 0) + 1
    
    # 각 종류별로 옷을 선택하는 경우의 수 계산 (해당 종류의 옷을 안 입는 경우 포함)
    for count in dic.values():
        answer *= (count + 1)  # 해당 종류의 옷을 선택하지 않는 경우도 포함하여 +1
    
    return answer - 1  # 아무것도 입지 않는 경우의 수 1을 뺌

최초에는 combinations를 사용하여 복잡하게 풀이했다.

더 나은 풀이를 참고하니 깨달음을 얻었다.

선택하지 않는 것을 포함한 모든 조합의 수를 구하는 것 == 케이스마다 선택 가능한 `경우의 수 + 1` 모두 곱하기

5. 베스트앨범 (Lv. 3)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

# 이해
# 1. 해당 장르의 재생 수
# 2. 동일 장르 내 곡의 재생수
# 3. 고유번호가 낮은 것

# 풀이
# genre_count = { 장르: 총 재생 횟수 }
# genre_dic = { 장르: [고유번호, 재생 횟수] }
# genre_count -> 재생 횟수 -> 고유 번호 순서대로 정렬
# 각 장르마다 2개씩 끊어서 고유 번호 저장

def solution(genres, plays):
    answer = []
    
    genre_count = {}
    genre_dic = {}
    
    for i in range(len(genres)):
        if genres[i] in genre_count:
            genre_count[genres[i]] += plays[i]
        else:
            genre_count[genres[i]] = plays[i]
        
        genre_dic.setdefault(genres[i], []).append([i, plays[i]])
    
    # genre_count의 values의 내림차순으로 정렬
    genre_count_sorted = sorted(genre_count.items(), key=lambda x: x[1], reverse=True)
    
    for genre, _ in genre_count_sorted:
        sorted_songs = sorted(genre_dic[genre], key=lambda x: (-x[1], x[0]))
        answer.extend([song[0] for song in sorted_songs[:2]])
    
    
    return answer

최초에는 정말 복잡하게 풀었다.

`dictionary.setdefault(val, default_val)` 함수를 기억하자.

lambda로 정렬 함수를 작성할 때 `-, +` 부호를 활용하여 `내림차순, 오름차순`을 쉽게 표현할 수 있다는 것을 기억하자.

구현 문제가 아닌 이상 코딩테스트의 코드는 과도하게 복잡해지지 않는다는 것을 기억하자.

실전에서는 어찌 됐든 풀이하는 게 맞다. 그러나 코드의 엔트로피가 올라가고 있다면 뭔가 잘못 됐다는 것을 의식하자.

8. Leader lesson - Learn to Code - Codility

문제 분석

 배열을 쪼개, 두 배열 모두 같은 leader를 갖게 하는 index를 모두 return

의사 코드

 leftCount = 0, rightCount = 배열의 길이, leftLeaderCount = 0, rightLeaderCount = 0
 1 .leader 구함
 2. 배열 탐색하면 leader를 만나면
     leftLeaderCount += 1
     rightLeaderCount -= 1
leftSize += 1
rightSize -= 1
leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2일 때, answer += 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    // leader 구한다.
    let sortedA = A.sorted()
    let candidate = sortedA[A.count / 2]
    var cnt = 0
    for elem in A {
        if candidate == elem {
            cnt += 1
        }
    }
    let leader = cnt > A.count / 2 ? candidate : -1 

    var leftSize = 0
    var leftLeaderCount = 0
    var rightSize = A.count
    var rightLeaderCount = cnt
    var answer = 0

    for elem in A {
        if elem == leader {
            leftLeaderCount += 1
            rightLeaderCount -= 1
        }

        leftSize += 1
        rightSize -= 1

        if leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2 {
            answer += 1
        }
    }

    return answer
}

Dominator coding task - Learn to Code - Codility

의사 코드

 1. leader 후보 찾기
     배열을 탐색하며, size == 0이라며면,
         해당 값을 value에 할당한다. size += 1
     size == 0이 아니라면,
         새로운 값이라면, size -= 1
         새로운 값이 아니라면, size += 1
    
     2. 후보 개수 세기
     candidate = -1
     if size > 0이라면,
         candidate = value
     배열에서 candidate와 같은 값의 index를 저장한다.
     return candidate의 개수 > 배열의 크기 / 2 이면 ? index 배열 : - 1

풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var size = 0
    var value = 0

    for elem in A {
        if size == 0 {
            value = elem
            size += 1
        } else {
            if value != elem {
                size -= 1
            } else {
                size += 1
            }
        }
    }

    var candidate = -1
    var count = 0
    var idxArray = -1
    if size > 0 {
        candidate = value
    }

    for i in 0..<A.count {
        if A[i] == candidate {
            count += 1
            idxArray = i
        }
    }

    return count > (A.count / 2) ? idxArray : -1
}

StoneWall coding task - Learn to Code - Codility

문제 분석 (틀림)

문제 분석
막대 그래프를, 직사각형으로만 구성하기 위해 필요한 최소 개수는?
막대의 높이가 최대 10억이므로, 일반적인 탐색 문제는 아닌 듯하다.
왼쪽부터 현재 원소의 값(높이)를 기준으로, 연속으로 확장 가능한 너비를 측정한다.
현재 값보다 작은 값을 만나면 멈춘다. 직사각형을 1개를 구성한다.
    구성이 완료된 부분은, 각 원소에서 현재 값만큼 빼준다.
    직사각형 개수를 += 1
그런데 이렇게 하면, O(N^2)으로 시간 초과가 난다..

문제 분석 (구글링)

 스택에 저장된 높이와 현재 높이를 비교하면서 다음을 실행한다.
     1. 저장된 높이가 더 높은 경우: 현재 더 낮은 높이 블럭이 생길 것이므로, 이어지던 직사각형 생성 과정이 종료되었다. 이후 판단 과정에서 저장된 높이들이 필요 없어졌다. 현재보다 더 높은 블럭을 모두 스택에서 제거한다.
     2. 같은 경우: 아무 것도 하지 않는다. 블럭을 아끼는 것이다.
     3. 저장된 높이가 더 낮은 경우: 더 높은 새로운 블럭이 필요하다. 개수를 세고, 스택에 추가한다.

풀이 (구글링)

import Foundation
import Glibc

public func solution(_ H : inout [Int]) -> Int {
    var stack: [Int] = []
    var count = 0

    for element in H {
        while !stack.isEmpty && stack.last! > element {
            stack.removeLast()
        }

        if stack.isEmpty || stack.last! < element {
            count += 1
            stack.append(element)
        }
    }

    return count
}

회고

분명 Easy인데, 꽤나 어려운 문제였다.

인간의 직관과는 다른 컴퓨팅 사고가 필요한 문제에 여전히 고전한다.

이 문제는 3가지 케이스를 생각해내는 것이 핵심이다.

stack.top과 탐색 중인 element을 비교한다. 비교값은 3가지 케이스를 갖는다.

1. 같은 경우:
   1. 패스한다.
2. element가 더 작은 경우:
   1. stack의 더 높은 막대들은, element를 만들 수 없다.
   2. 동시에 1.의 케이스로 이어지던 직사각형의 생성 과정이 종료된다.
   3. 생성이 종료된 높은 막대들은 이후 판단 과정에 필요 없다. 모두 제거한다.
3. element가 더 큰 경우:
   1. 새로운 높은 막대가 필요하다.
   2. count를 증가시키고, stack에 element를 추가한다.

참고

https://rkdvnfma90.tistory.com/261

Nesting coding task - Learn to Code - Codility

의사 코드

 입력값이 "("인 경우:
     스택이 비어있으면 추가한다
     스택이 비어있지 않으면
         top이 ")"이면 return 0
         아니라면 추가한다.

 입력값이 ")"인 경우:
     스택이 비어있으면 return 0
     스택이 비어있지 않으면
         top이 "("이면 popLast()
         아니라면 return 0

 stack의 길이가 0이라면 return 1, 아니라면 return 0

풀이

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    var stack: [String] = []
    
    for currentB in S {
        if currentB == "(" {
            if stack.isEmpty {
                stack.append(String(currentB))
            } else {
                if stack.last! == ")" { return 0 }
                else { stack.append(String(currentB)) }
            }
        } else { // ")"
            if stack.isEmpty { 
                return 0
            } else {
                if stack.last! == "(" { _ = stack.popLast() }
                else { return 0 }
            }
        }
    }

    return stack.count == 0 ? 1 : 0
}

https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

문제 분석

 인접한 원소가 다른 방향을 갖고 있다면, 싸움이 붙는다.
 싸움: 큰 물고기가 작은 물고기를 먹어버린다.
 물고기는 한 방향으로 계속 이동한다.

의사 코드

 순방향으로 탐색
 while stack이 비어있지 않고, 현재 원소가 올라가고, stack에 있는 원소가 내려가고 있을 때 판단
     if stack.last!.0 < currentElement.0
         stack.popLast()
     else 
				 flag = true // 현재 원소가 잡아먹힘 -> 더 할 게 없음.
		     break
if flag == false // 현재 원소 잡아먹히지 않음 -> stack에 추가
	append

나의 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int {
    var survivedStack: [(Int, Int)] = []

    for i in 0..<A.count {
        let currentElement = (A[i], B[i])
        var isEaten = false

        while !survivedStack.isEmpty && survivedStack.last!.1 == 1 && currentElement.1 == 0 {
            if survivedStack.last!.0 < currentElement.0 {
                _ = survivedStack.popLast()
            } else {
                isEaten = true
                break
            }
        }

        if !isEaten {
            survivedStack.append(currentElement)
        }
    }

    return survivedStack.count
}

Brackets coding task - Learn to Code - Codility

문제 분석 (오답)

문자열 S가 'properly nested' 문자열인지 판단하는 문제
 'properly nested'이란?
     1. "": 빈 문자열
     2. "(X)", "[X]", "{X}": 괄호로 둘러싸인 배열
     3. "XX": nested strings이 나열된 배열
 문자열 S는 (, ), [, ], {, } 으로만 구성된다.

 Stack으로 푸는 문제
 Stack을 구현하지 않아도 된다.

의사 코드 (오답)

3가지의 괄호를 담당하는 변수를 하나씩 선언한다.
 문자열을 탐색한다.
     열린 괄호를 만나면, 해당하는 변수에 += 1
     닫힌 괄호를 만다면, 해당하는 변수에 -= 1
     변수가 0 보다 작아지면, 즉시 return 0
 탐색이 종료되고, 3개의 변수가 모두 0이면 return 1 아니면 return 0

나의 풀이 (오답)

import Foundation
 import Glibc

 public func solution(_ S : inout String) -> Int {
     let size = S.count
     if size == 0 { return 1 }
     if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

     var bracket = 0
     var squareBracket = 0
     var curlyBracket = 0

     for i in 0..<size {
         let idx = S.index(S.startIndex, offsetBy: i)
         let currentBracket = S[idx]

         switch currentBracket {
             case "(":
                 bracket += 1
             case ")":
                 bracket -= 1
                 if bracket < 0 { return 0 }
             case "[":
                 squareBracket += 1
             case "]":
                 squareBracket -= 1
                 if squareBracket < 0 { return 0 }
             case "{":
                 curlyBracket += 1
             default: // "}"
                 curlyBracket -= 1
                 if curlyBracket < 0 { return 0 }
         }
     }

     return bracket == 0 && squareBracket == 0 && curlyBracket == 0 ? 1 : 0
 }

문제 분석 2 (오답)

Stack으로 구현해야 한다 ..
카운트만 해서는 다음과 같은 테스트 케이스를 통과할 수 없다. "([)()]"

의사 코드 2 (오답)

문자열을 담을 스택을 선언한다. var bracketStack = [String]()
 열린 괄호가 들어오면, 스택에 push() 한다.
 닫힌 괄호가 들어오면, 스택에서 pop() 한 값과 짝을 이루는지 검증한다.
     짝이 아니면 즉시 return 0
     짝이 맞으면 그대로 pop()
 탐색이 끝났을 때, 배열이 비어있으면 1 아니면 0

나의 풀이 2 (오답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

    var bracketStack = [String]()

    for i in 0..<size {
        let idx = S.index(S.startIndex, offsetBy: i) // 여기가 문제
        let currentBracket = String(S[idx])

        switch currentBracket {
            case ")":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "(" { return 0 }
            case "]":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "[" { return 0 }
            case "}":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "{" { return 0 }
            default:
                bracketStack.append(currentBracket)
        }
    }

    return bracketStack.count == 0 ? 1 : 0
}

// 시간 복잡도가 무려 O(3 ** N)...
// String의 subscript는 O(N)이다. RandomAccessCollection이 아니므로.
// 그렇다 하더라도 O(N ** 2) 아닌가? 찾아봤지만 답을 얻기 어렵다.

수정된 풀이 (정답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 } // 문자열이 홀수 길이면 properly nested 조건X

    var bracketStack = [String]()

    for currentBracket in S {
				let currentBracket = String(currentBracket) // 이 부분 개선

        switch currentBracket {
            case ")":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "(" { return 0 }
            case "]":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "[" { return 0 }
            case "}":
                guard let popped = bracketStack.popLast() else { return 0 }
                if popped != "{" { return 0 }
            default:
                bracketStack.append(currentBracket)
        }
    }

    return bracketStack.count == 0 ? 1 : 0
}

// O(N)
// removerLast() -> Element
// popLast() -> Element?

더 나은 풀이 (정답)

import Foundation
import Glibc

public func solution(_ S : inout String) -> Int {
    let size = S.count
    if size == 0 { return 1 }
    if size % 2 == 1 { return 0 }

    let bracketMap = [")": "(", "]" : "[", "}" : "{"]
    var bracketStack = [String]()

    for bracket in S {
        if let matchingBracket = bracketMap[String(bracket)] {
            if bracketStack.isEmpty || matchingBracket != bracketStack.last {
                return 0
            }
            bracketStack.removeLast()
        } else {
            bracketStack.append(String(bracket))
        }
    }

    return bracketStack.isEmpty ? 1 : 0
}

// 딕셔너리와 함께 하면 쉽다.
// switch를 활용하지 않아도 된다.

회고

가장 기본적인 문제인데 꽤 고생했다.

Swift의 문자열 인덱싱은 쉬이 익숙해지지 않는다.

Swift에서 subscript(_ :)는 기본적으로 O(1)을 보장하지만, String은 다르다.

String은 Character의 Collection이다.

C++, Java의 char는 고정된 크기를 갖지만, Swift의 Character는 1개 이상의 Unicode Scalar로 이루어져 있다. 크기가 가변적이다.

따라서 String은 RandomAccessCollection 프로토콜을 따르지 않는다. (BidirectionalCollection 채택)

따라서 순차 접근해야 한다.

그렇기에, index(_ : offsetBy:)로 접근해야 하고, O(N)의 시간복잡도를 갖는다.

길이를 구하는 .count 연산도 String은 O(N). RandomAccessCollection은 O(1).

String의 원소에 대한 임의 접근이 반드시 필요하다면?

String을 Character의 Array로 바꾸고 작업을 한 뒤, 마지막에 String으로 바꾸는 것이 좋다.

String.index를 순회하는 것보다, Character의 Array가 훨씬 효율적이다.

let str = "Hello, World!"
let arr = Array(str)

print(arr) 
// ["H", "e", "l", "l", "o", ",", " ", "W", "o", "r", "l", "d", "!"]

참고

https://jcsoohwancho.github.io/2019-11-19-Swift-String-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9C%BC%EB%A1%9C-%EC%93%B0%EA%B8%B0/

https://stackoverflow.com/questions/38800662/big-o-of-accessing-a-string-with-an-index-in-swift-3-0

NumberOfDiscIntersections coding task - Learn to Code - Codility

문제 분석

겹치는 원의 개수를 구한다
 겹치기만 하면 되니까, x축만 고려하자
 겹친다의 정의: i번째 원의 max 값 >= i+1번째 원의 min 값
 O(N^2)하면 쉽게 풀리지만, N = 100,000이므로 불가능

구글링

 시작점과 끝점의 배열을 각각 구한다
 각각 오름차순으로 정렬한다
 시작점 배열을 기준으로 탐색하며, 활성화된 원의 개수를 하나씩 추가한다
     다음 순서 원을 탐색할 때,
     현재 원의 시작점 < 이전까지 가장 큰 원의 끝점인지 확인한다.
         아니라면 조건을 성립할 때까지 탐색하며 활성화된 원을 제거한다.
     기존 활성화된 원의 개수를 정답에 더한다.
     정답이 조건을 넘어서면 -1을 반환한다.

참고한 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    var starts = [Int]()
    var ends = [Int]()

    for i in 0..<size {
        starts.append(i - A[i])
        ends.append(i + A[i])
    }

    starts.sort()
    ends.sort()

    var intersections = 0
    var activeDiscs = 0
    var endIdx = 0

    for start in starts {
        while endIdx < size && ends[endIdx] < start { // 겹치지 않는 상황
            activeDiscs -= 1
            endIdx += 1
        }
        intersections += activeDiscs // 지금까지 활성화된 디스크 수를 더하고
        activeDiscs += 1 // 디스크 수 + 1

        if intersections > 10_000_000 {
            return -1
        }
    }

    return intersections
}

회고

꽤 어려웠다. 코딜리티 문제는 난도가 들쭉날쭉하다.

시작점과 끝점 만을 고려한다는 것에는 접근을 했다.

그러나 정렬을 해도 된다는 생각을 하지 못 했다.

순서쌍을 구하는 것이 아니라, 카운트만 하면 되니까 정렬을 해서 따져도 문제가 없다.

점화식 만드는 훈련을 지속하자.

참고

https://study-ihl.tistory.com/175