코딩하는 eroke

문제

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고,

우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

풀이

from collections import deque
def solution(priorities, location):
    answer = 0
    dq=deque()
    #0
    for i,v in enumerate(priorities):
        dq.append((i,v))
    
    priorities.sort(reverse=True)
    while True:
    	#1
        if dq[0][0]==location and dq[0][1]==priorities[0]: 
            return answer+1
        
        #2
        elif dq[0][1]!=priorities[0]: 
            top=dq.popleft()
            dq.append(top)
        
        #3
        else:  
            a=dq.popleft()
            del priorities[0]
            answer+=1

    return answer

0. 우선순위 배열을 (인덱스, 값) 형식의 deque로 생성 (이후 우선순위 배열은 내림차순 정렬)

1. 대기 큐 첫 원소가 찾으려는 location이면서 max 우선순위이면 출력차례를 return

2. max 우선순위가 아닌 원소는 다시 대기큐 맨 뒤로 이동

3. max 우선순위이지만 찾는 location 원소가 아닌경우 pop, 우선순위 배열에서도 max 우선순위 삭제, 출력순+1

문제

1. USED_GOODS_BOARD와 USED_GOODS_FILE 테이블에서 조회수가 가장 높은 중고거래 게시물에 대한 첨부파일 경로를 조회하는 SQL문을 작성해주세요. 

2. 첨부파일 경로는 FILE ID를 기준으로 내림차순 정렬해주세요. 

3. 기본적인 파일경로는 /home/grep/src/ 이며, 게시글 ID를 기준으로 디렉토리가 구분되고, 파일이름은 파일 ID, 파일 이름, 파일 확장자로 구성되도록 출력해주세요. 

4. 조회수가 가장 높은 게시물은 하나만 존재합니다.

풀이

WITH A AS(
 SELECT * FROM (
      SELECT UGB.BOARD_ID
        FROM USED_GOODS_BOARD UGB
        ORDER BY UGB.VIEWS DESC
    )
    WHERE ROWNUM=1
)

SELECT '/home/grep/src/'||UGF.BOARD_ID||'/'||FILE_ID||FILE_NAME||FILE_EXT AS FILE_PATH
FROM A, USED_GOODS_FILE UGF
WHERE UGF.BOARD_ID=A.BOARD_ID
ORDER BY FILE_ID DESC

보드게시판에서 조회수가 최대인 데이터를 임시테이블로 추출한 뒤 파일테이블과 조인해서 풀었다.

세부조건 잘 확인하기!

1. 중복순열

1~n의 숫자 중 m개를 중복순열로 선택하기

n개의 노드를 가진 트리를 m레벨 만큼 내려가며 1에서 n사이의 숫자를 중복하여 선택한다

import sys
input=sys.stdin.readline #input 속도 개선/ 문자열 읽을 시 input().rstrip()으로 개행문자 제거필수
#중복순열
def dfs(lev): 
    global cnt
    if lev==m:
        print(res)
        cnt+=1

    else:
        for i in range(1,n+1): #1~n까지 m번 돌면서 하나씩 선택
            res[lev]=i
            dfs(lev+1)


if __name__=="__main__":
    n,m = map(int,input().split()) #n개 중 m개 중복순열 > n개의 노드 트리 m개 레벨 생성
    res=[0]*m
    cnt=0
    dfs(0)
    print(cnt) #중복순열의 개수

2. 순열

순열은 중복순열과 로직이 거의 똑같다.

단, dfs를 태울때 중복으로 선택하지 않도록 체크해주면 된다.

import sys
input=sys.stdin.readline #input 속도 개선/ 문자열 읽을 시 input().rstrip()으로 개행문자 제거필수
#순열
def dfs(lev):
    global cnt
    if lev==m:
        print(res)
        cnt+=1

    else:
        for i in range(1,n+1): #1~n까지 m번 돌면서 하나씩 선택
            if(ch[i]==0):   #선택하지 않은것만
                res[lev]=i  #선택
                ch[i]=1     #체크
                dfs(lev+1)
                ch[i]=0


if __name__=="__main__":
    n,m = map(int,input().split()) #n개의 노드 트리 m개 레벨 생성
    res=[0]*m
    ch=[0]*(n+1) #중복 제외처리 체크배열
    cnt=0
    dfs(0)
    print(cnt) #순열의 개수

3. 조합

조합은 1~n의 숫자들 중 m개를 선택한 부분집합끼리도 중복이 없어야 한다. [2,4]=[4,2]

n개의 숫자중 하나씩 택할때마다 다음 노드는 무조건 앞에서 선택한 것보다 큰 수를 선택하도록 한다. (중복방지)

import sys
input=sys.stdin.readline #input 속도 개선/ 문자열 읽을 시 input().rstrip()으로 개행문자 제거필수
#조합
def dfs(lev,node):
    global cnt
    if lev==m:
        print(res)
        cnt+=1

    else:
        for i in range(node,n+1): #node~n까지 m번 돌면서 하나씩 선택
            res[lev]=i
            dfs(lev+1, i+1) #트리 가지에 +1 (중요)

if __name__=="__main__":
    n,m = map(int,input().split()) #n개의 노드 트리 m개 레벨 생성
    res=[0]*m
    cnt=0
    dfs(0,1)
    print(cnt) #조합의 개수

참고

1. 부분집합

1부터 N까지의 부분집합을 구할때 DFS로 부분집합을 구현할 수 있다.

집합 원소는 포함할 수, 포함하지 않을 수로 체크하는 배열을 두어서 구현한다.

DFS가 N+1까지 도달하면 포함하기로 한 수를 차례로 출력한다.

#부분집합
def dfs(v):
    if v==n+1: #도착점
        for i in range(1,n+1):
            if ch[i]==1: print(i, end=' ')
        print()

    else:
        ch[v]=1 #사용하겠다
        dfs(v+1)
        ch[v]=0 #사용안함
        dfs(v+1)


if __name__=="__main__":
    n=int(input())
    ch=[0]*(n+1)
    dfs(1)

2. 합이 같은 부분집합 (응용)

입력받은 배열의 합과 부분집합의 합의 차이를 이용한다. (total-sum)

사용할 원소는 해당 원소를 더해준다.

사용하지 않을 원소는 기존 sum 값을 유지하고 트리 레벨만 증가시킨다.

import sys

def dfs(lev,sum): #tree level
    if sum>total//2: return #cut off (합이 같은 부분집합이므로 절반 이상 합산은 제거)

    if lev==n: #dfs탈출
        if sum==(total-sum):
            print("합이같은 부분집합 존재 : ",sum)
            sys.exit(0)

    else:
        dfs(lev+1, sum+arr[lev]) #사용
        dfs(lev+1, sum)          #사용x (기존 sum 그대로)

if __name__=="__main__":
    n=int(input())
    arr=list(map(int,input().split()))
    total=sum(arr)
    dfs(0,0)

    print("합이 같은 부분집합 없음") #dfs 함수에서 종료처리 안됐을 시

[1,3,5,7] [6,10] 16으로 합이 같은 부분집합이 존재한다.

참고

문제

 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 

노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1) 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2) 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3) 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 

베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 

(출처 : 프로그래머스)

입출력 예

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.
고유 번호 3: 800회 재생
고유 번호 0: 500회 재생
고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.
고유 번호 4: 2,500회 재생
고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를, classic 장르의 [3, 0]번 노래를 차례대로 return 합니다.

풀이

from collections import defaultdict as dd

def solution(genres, plays):
    answer = []
    gcac=dd(int) #calc
    gd=dd(list) #dict
    
    for i,v in enumerate(genres):
        gcac[v]+=plays[i]
        gd[v].append((i,plays[i]))
        
    gcac=sorted(gcac.items(),key=lambda x:x[1], reverse=True) #장르:플레이수합 
    #print('gcac: ',gcac)
    
    for name,total in gcac:
        gd[name]=sorted(gd[name],key=lambda x:x[1],reverse=True)
        #print('gd[',name,']',gd[name]) #[(4, 2500), (1, 600)]
        
        for idx in range(2):
            if idx==len(gd[name]): break
            answer.append(gd[name][idx][0])
    
    return answer

int형 defaultdict를 선언해 장르별 플레이 횟수를 집계했고 (gcac)

list형 defaultdict에 plays 배열의 장르별 플레이 횟수와 인덱스를 넣어주었다. (gd)

gcac을 플레이 횟수가 많은 순으로 정렬한 뒤 

gd에 플레이를 많이한 장르부터 접근해 리스트를 플레이 수 역순으로 정렬했다.

리스트 정렬 후 최대 2개까지 정렬된 리스트에서 인덱스를 answer에 추가해주었다.

문제

한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한이 있는 구명보트가 있다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 무게 제한이 100kg이라면 

2번째 사람과 4번째 사람은 같이 탈 수 있지만 

1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 무게 제한을 초과해 같이 탈 수 없다.

input : 사람들의 몸무게를 담은 배열 people, 구명보트의 무게 제한 limit

output : 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값

풀이

people 배열을 오름차순 정렬 후 첫 번째와 마지막 무게의 합이 제한보다 적거나 같으면 둘다 pop

아니면 마지막 무게를 pop하는 방식으로 구현했다.

파이썬으로는 deque를 활용했고 (pop, pop_left)

C++은 vector가 입력자료형이어서 첫 번째 원소를 pop할때 erase(v.begin(), v.begin()+1) 를 썼더니

매번 벡터의 인덱스를 호출해서인지 효율성 두개가 틀리게 제출돼서

인덱스를 증가시켜 첫 번째 원소를 pop 하듯이 구현했다.

1. Python

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort() #오름차순 
    people=deque(people) #deque로 형변환
    while people:
        if len(people)>1 and people[0]+people[-1]<=limit:
            answer+=1
            people.pop()
            people.popleft()
        
        else:
            people.pop()
            answer+=1

    return answer

2. C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end());
    
    // 정확성 100%, 효율성 2/5개 time out
    // while(!people.empty()){
    //     int s=people.size();
    //     if(people.size()>1&&people[0]+people.back()<=limit){
    //         answer+=1;
    //         people.pop_back();
    //         people.erase(people.begin(),people.begin()+1);
    //     }
    //     else{
    //         answer+=1;
    //         people.pop_back();
    //     }
    // }
    
    int idx=0;
    while(idx<people.size()){
        if(people.size()>1&&people[idx]+people.back()<=limit){
            answer+=1;
            people.pop_back();
            idx+=1;
        }
        else{
            answer+=1;
            people.pop_back();
        }
    }
    return answer;
}

문제

위와 같은 삼각형의 꼭대기에서 바닥까지 아래 칸으로 이동할 때 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능

(예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능)

삼각형의 정보가 담긴 배열 triangle이 주어질 때, 거쳐간 숫자의 최댓값을 return

풀이

노드 높이가 1일 때부터 부모노드 중 가능한 값을 더하며 그 중 최대값을 저장하도록 구현했다.

위의 그림처러 세 가지 경우로 나누어 계산했다.

인덱스가 (x,y)라고 했을 때,

1)  y=0 인경우 > 접근 가능한 부모1  (x-1,0)

2) y=해당 배열의 최대 인덱스인 경우 > 접근 가능한 부모1 (x-1, size)

3) 그 외 > 접근 가능한 부모2 (x-1, y-1), (x-1,y)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    vector<vector<int>> ct=triangle;
    
    for(int i=1;i<ct.size();i++){
        for(int j=0;j<ct[i].size();j++){
            if(j==0)ct[i][j]+=ct[i-1][0];
            
            else if(j==ct[i].size()-1)ct[i][j]+=ct[i-1][ct[i].size()-2];
            
            else ct[i][j]+=(max(ct[i-1][j-1],ct[i-1][j]));
        }
    }
    //greater<>() 내림차순, *max_element = algorithm include
    sort(ct[ct.size()-1].begin(),ct[ct.size()-1].end(), greater<>()); 
    answer = ct[ct.size()-1][0];
    //answer = *max_element(ct[ct.size()-1].begin(), ct[ct.size()-1].end());
    return answer;
}

완탐으로 누적합들을 계산한 뒤 

마지막 배열에서의 최대값을 구해 return 했다.

*최대값 구하는 방식*

algorithm 헤더 필요!

1) 내림차 순 정렬 후 마지막 배열의 0번째 값 return : greater<>()

2) *max_element(v.begin(), v.end())

오후내내 SQL을 오라클로 풀고 있었는데 실행결과는 잘 나오는데

틀렸다고 나와서 구글링도 해보고 시간을 꽤나... 썼는데

똑같은 SQL을 오라클로 제출할땐 실패였는데 MySQL에선 정답으로 떠서 어이가 없던 문제.....!!!!!!!!!

열받아서 서론을 길게 적었다.

문제

리뷰를 가장 많이 작성한 회원의 <회원 이름, 리뷰 텍스트, 리뷰 작성일>을 조회하는 SQL을 작성한다.

결과는 리뷰 작성일을 기준으로 오름차순 정렬해서 출력한다.

풀이 (MySQL, Oracle)

SELECT IMEMBER.MEMBER_NAME
     , MEM_RR.REVIEW_TEXT
     , MEM_RR.REVIEW_DATE
FROM  (SELECT MEM_MP.MEMBER_ID, MEM_MP.MEMBER_NAME
        FROM (SELECT MEMBER_ID
              , RANK() OVER (ORDER BY COUNT(MEMBER_ID) DESC) AS RNK
                FROM REST_REVIEW
                GROUP BY MEMBER_ID
             ) MEM_RNK
            , MEMBER_PROFILE MEM_MP
        WHERE MEM_RNK.RNK=1
          AND MEM_RNK.MEMBER_ID = MEM_MP.MEMBER_ID
      ) IMEMBER
      , REST_REVIEW MEM_RR
WHERE MEM_RR.MEMBER_ID = IMEMBER.MEMBER_ID
ORDER BY MEM_RR.REVIEW_DATE
;

리뷰 테이블에서 리뷰를 작성한 회원의 ID를 집계한 뒤 많은 순으로 랭킹을 부여했다.

MySQL 제출은 맞고 오라클은 틀리게 제출되는 이유.. 아시는 분은 댓글 부탁드립니다!!!

문제

테이블에서 생산일자가 2022년 5월인 식품들의 식품 ID, 식품 이름, 총매출을 조회하는 SQL을 작성한다.

최종 결과는 총매출을 기준으로 내림차순 정렬해서 출력한다.

ORDER 테이블에서 주문량(amount)을 집계한 뒤

PRODUCT 테이블의 생산일자가 2022년 05월인 제품의 금액을 곱해서 매출을 출력했다.

풀이 1 (MySQL)

SELECT FINFO.PRODUCT_ID
     , FINFO.PRODUCT_NAME
     , PTOTAL.AMOUNT*FINFO.PRICE AS TOTAL_SALES
FROM
    (SELECT PRODUCT_ID
         , SUM(AMOUNT) AS AMOUNT
    FROM FOOD_ORDER 
    WHERE DATE_FORMAT(PRODUCE_DATE,'%Y%m')='202205'
    GROUP BY PRODUCT_ID) PTOTAL, FOOD_PRODUCT FINFO
WHERE PTOTAL.PRODUCT_ID = FINFO.PRODUCT_ID
ORDER BY TOTAL_SALES DESC
;

풀이 2 (Oracle)

SELECT FINFO.PRODUCT_ID
     , FINFO.PRODUCT_NAME
     , PTOTAL.AMOUNT*FINFO.PRICE AS TOTAL_SALES
FROM
    (SELECT PRODUCT_ID
         , SUM(AMOUNT) AS AMOUNT
    FROM FOOD_ORDER 
    WHERE TO_CHAR(PRODUCT_DATE,'YYYYMM')='202205'
    GROUP BY PRODUCT_ID) PTOTAL
    , FOOD_PRODUCT FINFO
WHERE PTOTAL.PRODUCT_ID = FINFO.PRODUCT_ID
ORDER BY TOTAL_SALES DESC
;

이상한 점은 오라클에선 PRODUCE_DATE 필드를 못 읽었다..

PRODUCT_DATE 로 실행하면 결과는 MySQL과 동일하게 나오고 채점할땐 틀렸다 나왔다..;;

아마도 프로그래머스의 오류인 듯.. 싶다.

(링크)그룹별 조건에 맞는 식당 목록 출력하기 문제도

 MySQL, Oracle 같은 로직으로 풀었는데 MySQL은 정답, Oracle은 틀림으로 제출됐다....

첨엔 오라클로 풀었는데 날린 시간 생각하니 열받는다 ㅂㄷㅂㄷ

혹시나 제 sql이 문제라면 댓글 부탁드립니다..

문제

입출력 예제

입출력 예 설명

phone_book의 누군가의 번호가 누군가의 번호의 시작번호일때 false return

풀이

#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=1;i<phone_book.size();i++){
        if(phone_book[i].find(phone_book[i-1])==0)
            return false;
    }    
    return true;
}

정렬 후 문자열에서 이전 문자열 발견 인덱스가 0인 경우 false를 return하도록 구현했다.