초니로그

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

주어진 정수 배열을 적절히 더하거나 뺀 값이 주어진 타겟 넘버와 같은 경우의 수를 출력

풀이법 구상

처음에는 이중 반복문을 돌면서 각 숫자를 음수로 바꾼 후의 총 합이 타겟과 같은지 판별하는 로직으로 구현했다가 실패

-> +4-1+2-1 과 같이 음수 사이에 양수가 존재하는 경우는 고려할 수 없음

각 숫자가 양수이거나 음수인 경우만 고려하면 되고 그러면 2^N의 시간 복잡도가 발생하는데, N의 최대값은 20으로 약 1,050,000이 됨

각 숫자가 양수이거나 음수가 되는 경우를 모두 고려하려면 각 숫자에 +,-를 붙인 노드로 이루어진 트리로 시각화할 수 있음

각 노드를 탐색하며 더한 합계값을 타겟 넘버와 비교하면 결과값 도출 가능

탐색에는 BFS/DFS를 모두 사용할 수 있으나 제출 코드는 BFS사용

코드 구현 (스위프트 사용)

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var result = 0
    var sum_arr = [0]   // 반복문 시작을 위해 0 하나 추가
    
    for n in numbers {
        var temp: [Int] = []
        for s in sum_arr {
            temp.append(s+n)
            temp.append(s-n)
        }
        sum_arr = temp
    }
    
    for s in sum_arr { result += (s == target) ? 1 : 0 }
    
    return result
}

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/120875

문제 설명

x,y 좌표값으로 구성된 점 4개의 정보가 2차원 정수형 배열로 주어짐

4개의 점들이 조합되어 만들 수 있는 직선 중 서로가 평행한 경우가 있다면 결과값으로 1을, 아니라면 0을 반환해야함

풀이법 구상

점의 정보는 4개로 고정된 만큼만 주어짐

직선의 x,y 좌표간 차이값의 절대값이 같으면 평행한 것으로 간주하고 풀었다가 틀림 -> 방향 고려 안됨

방향을 포함하는 기울기값(y차이 / x차이)이 같으면 평행

주어진 점 4개로 서로 다른 직선을 구성할 수 있는 경우의 수를 아래와 같음

(0번째 점, 1번째 점)

(0번째 점, 2번째 점)

(0번째 점, 3번째 점)

(1번째 점, 2번째 점)

(1번째 점, 3번째 점)

(2번째 점, 3번째 점)

서로 다른 직선 6가지 경우의 각 기울기 값을 구하여 반복문을 돌며 같은 값이 존재하는지 판단 -> 틀림(12번 케이스부터 실패)

위와 같은 로직으로 기울기들을 판별할 경우 불가능한 경우까지 비교하게됨

ex. (0번째 점, 1번째 점)으로 이루어진 직선과 (0번째 점, 2번째 점)으로 이루어진 직선 간의 기울기를 비교

즉 주어진 점 4개로 '서로 다른 2개의 직선'을 구성하여 비교하기 위한 경우는 아래와 같음

(0번째 점, 1번째 점) VS (2번째 점, 3번째 점)

(0번째 점, 2번째 점) VS (1번째 점, 3번째 점)

(0번째 점, 3번째 점) VS (1번째 점, 2번째 점)

코드 구현 (스위프트 사용)

func solution(_ dots:[[Int]]) -> Int {
    if (getInc(dots[0], dots[1]) == getInc(dots[2], dots[3])) {
        return 1
    } else if  (getInc(dots[0], dots[2]) == getInc(dots[1], dots[3])) {
        return 1
    } else if  (getInc(dots[0], dots[3]) == getInc(dots[1], dots[2])) {
        return 1
    } else {
        return 0
    }
}

func getInc(_ m:[Int], _ n: [Int]) -> Double {
    let diffX = max(m[0], n[0]) - min(m[0], n[0])
    let diffY = max(m[1], n[1]) - min(m[1], n[1])
    let inc = ((n[0]-m[0])*(n[1]-m[1]) < 0) ? -1.0 : 1.0
    return inc*(Double(diffY)/Double(diffX))
}

문제 링크 - https://www.acmicpc.net/problem/2012

문제 설명

n명에게 각각 예상 등수값을 입력받고, 그 값들을 토대로 불만족 지수가 최소로 나오도록 구성하여 불만족 지수의 최소값을 출력

불만족 지수란 예상 등수가 1등이고, 실제 순위 구성 후 등수가 3등인 경우 (|1-3|)으로 2의 값이 됨

(n의 범위는 1이상 500,000이하)

풀이법 구상

예상 순위보다 실제 순위가 높든 낮든 무관하게 그 차이값만큼이 불만족 수치가 됨

최대한 예상 순위가 실제 순위가 되도록 해야하므로 정렬 후 각 예상 순위값을 돌며 실제 순위와의 차이값을 구해야함

정렬 + 반복문이 필요함

-> 스위프트 기본 정렬 메소드의 시간복잡도 - O(n log n)

-> 반복문 시간 복잡도 - O(N)

-> 동시에 일어나지 않고 정렬 후 반복문 돌게됨

코드 구현 (스위프트 사용)

import Foundation

func solution(_ arr: [Int]) -> Void {
    var sum = 0
    let temp = arr.sorted()
    for i in 1...arr.count { sum += abs(i - temp[i-1]) }
    print(sum)
}

var arr: [Int] = []
let cnt = Int(readLine()!)!
for _ in 0..<cnt { arr.append(Int(readLine()!)!) }

solution(arr)

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/131533

문제 설명

판매중인 상품 정보(ID, 상품코드, 가격)를 담은 PRODUCT 테이블과 오프라인 판매 정보를 담은 OFFLINE_SALE 테이블이 주어짐

그 중 상품 코드 당 총 판매금액 (판매한 개수*판매액)을 출력 

(총 판매금액을 기준으로 내림차순 정렬, 같다면 상품코드를 기준으로 오름차순 정렬)

풀이법 구상

ID값을 기준으로 Join을 이용하여 PRODUCT 테이블 내 가격정보와 OFFLINE_SALE 테이블 내 판매량 정보를 곱한 SALES 열 생성

코드 구현 (MySQL 사용)

SELECT PRODUCT_CODE, SUM(PRICE*SALES_AMOUNT) AS SALES
    FROM PRODUCT JOIN OFFLINE_SALE
    ON PRODUCT.PRODUCT_ID = OFFLINE_SALE.PRODUCT_ID
    GROUP BY PRODUCT_CODE
    ORDER BY SALES DESC, PRODUCT_CODE ASC

+) 삽질

처음에 이렇게 작성했다가 중복 행이 있는 줄 알고 DISTINCT 썼는데 틀렸음

혹시나하고 OFFLINE_SALE_ID 같이 출력해봤더니 중복행이 아니었음

-> 각각 다른 판매건수이므로 상품코드별로 다 합쳐야 총 판매금액을 구할 수 있어서 GROUP BY 사용

문제 링크 - https://www.acmicpc.net/problem/2751

문제 설명

랜덤한 숫자 n개가 입력되면 해당 숫자들을 오름차순으로 정렬하여 한 줄에 하나씩 출력

- 입력되는 숫자의 개수는 1개 이상 1,000,000개 이하

- 들어오는 숫자는 절대값이 1,000,000이하인 정수

풀이법 구상

스위프트에 있는 sort 메소드 사용하기

-> 기본 정렬 메소드의 시간 복잡도는 O(n log n) 이므로 시간 제한에 문제되지않음

코드 구현 (스위프트 사용)

import Foundation

func solution(_ arr: [Int]) -> Void {
    let result = arr.sorted()
    for n in result { print(n) }
}

var arr: [Int] = []
let cnt = Int(readLine()!)!
for _ in 0..<cnt { arr.append(Int(readLine()!)!) }

solution(arr)

문제 링크 - https://www.acmicpc.net/problem/2581

문제 설명

주어진 두 수 m, n을 포함하여 그 사이에 존재하는 소수의 합계값과 그 소수들 중 최소값을 출력 (소수가 없는 경우 -1 출력)

풀이법 구상

m이상 n이하를 범위로 하는 반복문을 돌면서 각 수가 소수인지 판별

코드 구현 (스위프트 사용)

import Foundation

func solution(_ m:Int, _ n:Int) -> Void {
    var sum = 0
    var min = -1

    for p in m...n {
        if isDecimal(p) {
            sum += p
            if (min == -1 || min > p) { min = p }
        }
    }
    if (sum == 0) { print(-1) }
    else {
        print(sum)
        print(min)
    }

}

func isDecimal(_ n:Int) -> Bool {
    if (n == 1) { return false }
    for i in 2..<n { if (n%i == 0) { return false } }
    return true
}

let m = Int(readLine()!)!  
let n = Int(readLine()!)!  

solution(m,n)