초니로그

문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/42885

문제 설명

사람들의 무게를 담은 배열과 구명보트 1개가 최대로 담을 수 있는 무게의 한계값(limit)이 주어짐

이를 토대로 필요한 구명보트 수의 최솟값을 구해야 함

단, 구명보트에는 최대 2명만이 탑승할 수 있음

풀이법 구상

무게 배열을 정렬하고, 가장 큰 값과 작은 값을 더해서 limit을 넘는지 안 넘는지를 토대로 개수를 구함

[큰 값과 작은 값을 더했을 때 limit 이하인 경우]

-> 두 사람(큰 값, 작은 값)이 보트 하나에 탔다고 치고, 큰/작은 값에 해당하는 인덱스를 한 칸씩 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

[큰 값과 작은 값을 더했을 때 limit 초과인 경우]

-> 한 사람(큰 값)만 보트에 태우고, 큰 값에 해당하는 인덱스를 한 칸 이동 + 새로운 구명보트 꺼냄(카운트 1 증가)

코드 구현 (Java)

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int idx = 0;
        for (int i=people.length-1; i>=idx; i--) {
            if (people[i]+people[idx] <= limit) idx++;
            answer++;
        }
        return answer;
    }
}

문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제 설명

귤 크기를 의미하는 정수 배열이 주어짐

이 중 k개의 귤을 뽑아야 할 때, 크기의 종류 최솟값을 구해야 함

풀이법 구상

<틀린 풀이>

DFS를 활용하여 귤 크기 배열 내 부분 집합을 구하여 최솟값 갱신

-> n은 최대 100,000인데, dfs가 끝날 때마다 ch 배열을 전부 확인하게 되며 O(N^2)의 시간 복잡도를 가지게 됨

import Foundation

var answer = 100000
var ch:[Bool] = []

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    ch = Array(repeating: false, count: tangerine.count)
    dfs(0, tangerine, k)
    return answer
}

func dfs(_ v: Int, _ t:[Int], _ k: Int) {
    if(v == t.count) {
        var sizes = Set<Int>()
        var contain_cnt = 0
        for i in 0..<t.count {
            if(ch[i]) {
                contain_cnt += 1
                sizes.insert(t[i])
            }
        }
        if(!sizes.isEmpty && contain_cnt == k && answer > sizes.count) { 
            answer = sizes.count
        }
        
    } else {
        ch[v] = true
        dfs(v+1, t, k)
        ch[v] = false
        dfs(v+1, t, k)
    }
}

<정답 풀이>

딕셔너리를 통해 귤의 크기 별 개수를 정의

크기 별 개수를 기준으로 딕셔너리를 내림차순 정렬

딕셔너리를 돌며 개수와 종류 수를 누적합하며, 그 값이 k 이상이 될 경우 누적된 종류 수를 반환

(개수가 많은 것부터 탐색하므로 누적된 종류 수는 최소일 수밖에 없음)

코드 구현 (Swift)

import Foundation

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    var dict:[Int:Int] = [:]
    for t in tangerine {
        if(dict[t] == nil) { dict[t] = 1 }
        else { dict[t]! += 1 }
    }
    let s_dict = dict.sorted { $0.value > $1.value }
    
    var sum = 0
    var answer = 0
    for d in s_dict {
        sum += d.value
        answer += 1
        if(sum >= k) { return answer }
    }
    return answer
}

문제 링크 - 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/15008/lessons/121683?language=python3

문제 설명

알파벳 소문자로만 이루어진 문자열이 주어짐

해당 문자열 중 같지만 바로 옆에 붙어있지 않은 알파벳이 존재하는 경우 '외톨이 알파벳'으로 간주

외톨이 알파벳으로 이루어지고 알파벳 순으로 정렬된 새로운 문자열을 출력

풀이법 구상

반복문으로 각 자리의 글자를 대상으로 다른 똑같은 글자가 존재하는지 확인

단, 기준 글자의 바로 옆에 똑같은 다른 글자가 존재하는 경우 기준 인덱스 += 1 -> 그냥 바로 다음 글자로 넘어간다는 의미

기준 인덱스로부터 2자리 이상 떨어진 경우 외톨이 알파벳으로 간주

코드 구현 (파이썬 사용)

def solution(input_string):
    answer = ''

    for p in range(0,len(input_string)):
        if input_string[p] in answer: continue
        for q in range(p+1,len(input_string)):
            if input_string[p] == input_string[q]:
                if ((q-p) == 1): break
                elif ((q-p) > 1):
                    answer += input_string[p]
                    break
                
    if len(answer) == 0 : return 'N'
    else: return ''.join(sorted(answer))

문제 링크 - 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://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 사용