코딩하는 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) 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
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하도록 구현했다.

문제

카카오 문제들은 항상 프렌즈 캐릭터가 예시로 나온다.

프렌즈들은 넘나 귀엽지만.. 문제로 만나면 왠지 화가난다.. 귀여운척하지마 악랄한것아

그림에서 상하좌우가 같은 색으로 연결된 경우를 '한 영역'으로 친다.

위 그림의 경우는 총 12영역이다. (눈6, 입3, 볼2, 얼굴1)

영역의 개수와 가장 넓은 영역의 넓이를 return하는 문제이다.

풀이

#include <vector>
#include <deque>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector<int> answer(2);
    vector<vector<int>> v(m,vector<int>(n,0)); //visit
    deque<pair<int,int>> dq;
    int cnt=0, max_cnt=0, area_cnt=0;
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(v[i][j]==0 && picture[i][j]!=0){
                int val=picture[i][j];      //시작영역 값
                dq.push_back(make_pair(i,j)); //영역 시작 위치
                v[i][j]=1;                  //visit
                cnt=0;                      //영역 개수 초기화
                area_cnt++;                 //영역 추가
                while(!dq.empty()){
                    int cx=dq[0].first;
                    int cy=dq[0].second;
                    dq.pop_front();
                    cnt++;
                    
                    for(int k=0;k<4;k++){
                        int nx = cx+dx[k];
                        int ny = cy+dy[k];
                        if(nx>=0 && nx<m && ny>=0 && ny<n &&
                           v[nx][ny]==0 && picture[nx][ny]==val){
                            dq.push_back(make_pair(nx,ny));
                            v[nx][ny]=1; //visit
                        }
                    }
                }
                if(max_cnt<cnt)max_cnt=cnt;
            }
        }
    }
    
    // for(int i=0;i<v.size();i++){
    //     for(int j=0;j<v[i].size();j++){
    //         cout<<v[i][j]<<" ";    
    //     }
    //     cout<<endl;
    // }
    
    answer={area_cnt, max_cnt};
    return answer;
}

BFS로 풀었고 처음 picture 배열을 탐색하다 방문하지 않고 picture 값이 0이 아닌 경우

picture 값을 저장하고 해당 위치를 큐에 넣어 다음 위치값이 저장한 값과 같고 방문하지 않은 위치를 큐에 넣어 반복했다.

*2차원 벡터 사용법 참고 : vector<vector<int>> v(m,vector<int>(n,default_value))

문제

input : n (끝말잇기를 하는 사람 수), words (끝말잇기 단어 문자열배열)

output : [가장 먼저 탈락한 사람번호, 탈락한 게임 순서]

입출력 예

풀이

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

vector<int> solution(int n, vector<string> words) {
    vector<int> answer;
    map <string,int> m;
    int cnt=0;
    
    for(int i=0;i<words.size();i++){
        if(i%n==0)cnt++; //차례 count
        
        if(i>0){
            int prewordln = words[i-1].length()-1;
            if(words[i-1][prewordln]!=words[i][0]){ //끝말잇기를 틀렸을때
                answer.push_back((i+1)-n*(cnt-1));
                answer.push_back(cnt);            
                return answer;
            }
        }
        
        if(m.find(words[i])!=m.end()){ //이미 말했던 단어일때
            answer.push_back((i+1)-n*(cnt-1));
            answer.push_back(cnt);            
            return answer;
        }
        else m.insert({words[i],1}); //처음 나온 단어 딕셔너리 추가
    }
    if(answer.empty()) return {0,0}; //탈락자가 없을때
}

탈락 기준

1. 끝말잇기가 틀린 경우

2. 이미 말했던 단어인 경우

처음 등장하는 단어는 key:value 구조(딕셔너리)인 map에 저장했다.

탈락자가 발생하는 경우에 탈락한 사람의 번호와 탈락한 게임순서를 return 해야한다.

게임순서는 i%n==0 인 경우마다 count

사람번호는 게임순서와 문자열 순서와의 연관을 고려하여 (i+1)-n*(cnt-1) 로 계산하였다.

C++ map (key:value 딕셔너리 자료구조)

*map.find(key) = key 를 찾지 못하면 map.end()를 return 한다.

map에서 특정 키를 찾고 싶을때 if(map.find(key)!=map.end()) 사용

- map 사용법 참고