코딩하는 eroke

문제

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

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

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

위 그림의 경우는 총 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 사용법 참고

문제

피보나치 수 F(n) = F(n-1) + F(n-2)

input: 2<=n<=100,000 

return : n번째 피보나치 수 % 1234567

그냥 재귀함수로만 구현하면 틀리는 문제로 메모이제이션이 중요한 문제이다.

(실패이유 : 재귀함수 호출 수 초과)

메모이제이션 (memoization) :

한 번 계산한 결과는 저장, 이후 저장한 값으로 호출하여 재귀가 계속해서 호출되는 것을 방지

풀이

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

int d[100001]; //전역=0초기화
int fibo(int n){
    if(n<=2) return 1;
    
    if(d[n]!=0) return d[n]%1234567; //메모이제이션
    else{
        d[n]=fibo(n-1)+fibo(n-2);
        return d[n]%1234567;
    }    
}

int solution(int n) {
    return fibo(n);
}

문제

input :

0과 1로 이루어진 어떤 문자열 x

1. x의 모든 0을 제거
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 변환

return :
x가 "1"이 될 때까지 계속해서 x에 변환을 가했을 때의

[이진 변환의 횟수, 변환 과정에서 제거된 모든 0의 개수]

   ex)

x = "0111010"이라면,

x = "0111010" -> 0제거 -> "1111" -> 4("1111"의 길이) 이진변환 -> "100" 

[3,5] return

풀이

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

vector<int> solution(string s) {
    vector<int> answer={0,0};
    int zero=0,ztotal=0,cnt=0,len=0;
    string cp=s;
    
    if(cp=="1") return answer;
    
    while(cp!="1"){
        cnt++; //이진변환 횟수
        zero=0;
        for(int i=0;i<cp.length();i++){
            if(cp[i]=='0')zero++;
        }
        ztotal+=zero; //제거한 0개수
        len = cp.length()-zero;

        string bin="";
        while(len){
            bin+=to_string(len%2);
            len/=2;
        }
        reverse(bin.begin(),bin.end());
        cp=bin;
    }
    answer[0]=cnt;
    answer[1]=ztotal;
    return answer;
}

요새 파이썬으로만 문제를 풀다가 오랜만에 C++ 로 문제를 풀려고하니 문법을 죄다 까먹었다;;

특히 STL, 문자열........... 당분간 C++ 문법 복기용 문제들을 풀어볼 예정이다..

문제

위의 입출력 예시 그대로인 간단한 문제이다. 뒤의 숫자 네개를 제외하고 마스킹(*)하면 된다.

(phone_number는 길이 4 이상, 20이하인 문자열)

풀이

#include <string>
#include <iostream>

using namespace std;

string solution(string phone_number) {
    string star = "****************";
    
    string subs = phone_number.substr(phone_number.size()-4, phone_number.size());
    int ln = phone_number.size()-4;
    string answer = star.substr(0,ln);
    answer+=subs;
    
    return answer;
}

전화번호의 뒤 숫자 4개를 substr로 끊고

4개를 제외한 길이만큼 * 문자열을 만들어 둘을 합쳐서 return 했다.

문제

FOOD_ORDER 테이블에서 5월 1일을 기준으로 주문 ID, 제품 ID, 출고일자, 출고여부를 조회하는 SQL작성

5월 1일까지 출고완료, 이 후 날짜는 출고 대기, 미정이면 출고미정

결과는 주문 ID를 기준으로 오름차순 정렬해주세요.

출력예시 (출처 : 프로그래머스)

위의 예시만 보고 OUT_DATE 포맷도 'YYYY/MM/DD' 로 맞췄더니 틀렸다고나왔다;

OUT_DATE는 그냥 출력하면된다. 출고여부는 CASE문으로 작성했다.

풀이

SELECT ORDER_ID
     , PRODUCT_ID
     , OUT_DATE
     , CASE WHEN TO_CHAR(OUT_DATE,'YYYYMMDD') <= '20220501' THEN '출고완료'
            WHEN TO_CHAR(OUT_DATE,'YYYYMMDD') > '20220501' THEN '출고대기'
            ELSE '출고미정' END AS 출고여부
FROM FOOD_ORDER 
ORDER BY ORDER_ID

문제

M,N,K (행, 열, 직사각형 개수)를 입력받고

K개의 직사각형 왼쪽 아래 좌표와 오른쪽 위 좌표를 입력받아 색칠한다.

<그림1> 같이 색칠이 끝나면 <그림2>처럼 직사각형 외부에 분리된 영역들이 생기는데

이 영역들의 넓이를 각각 구하고 영역의 개수를 첫째 줄에 출력,

영역의 넓이를 오름차순으로 각각 출력해주면 되는 문제이다.

풀이 (python, BFS)

from collections import deque

dx=[1,-1,0,0]
dy=[0,0,1,-1]

m,n,k = map(int,input().split())
sq=[[0]*(n) for _ in range(m)] #n*m 맵

#직사각형 좌표 입력 및 색칠
for tc in range(k):
    a,b,c,d = map(int,input().split()) #0 2 4 4
    for x in range(b,d): #2~4
        for y in range(a,c): #0~4
            sq[x][y]=1

#BFS
dq=deque()
answer=[]
for i in range(m):
    for j in range(n):
        if sq[i][j]==0:
            dq.append((i,j))
            cnt=0
            while dq:
                cx,cy=dq.popleft()
                for i in range(4):
                    nx=cx+dx[i]
                    ny=cy+dy[i]
                    if 0<=nx<m and 0<=ny<n and sq[nx][ny]==0:
                        cnt+=1
                        sq[nx][ny]=2 #visit
                        dq.append((nx,ny))
            if cnt==0: answer.append(1)
            else: answer.append(cnt)

answer.sort()
print(len(answer))
for a in answer:
    print(a,end=' ')

좌표를 입력받고 색칠한 뒤 (1로 표기)

맵에서 0인 영역이 존재하면 해당위치를 큐에 넣고 BFS를 돌려서 풀었다.

백준의 단지번호 붙이기와 매우 유사한 문제였다.

사실 오늘 냅색 알고리즘을 복습했는데 머리 빠개지는줄 알았다..

흑흑스 갈길이 넘멀다

파이팅..

문제

그림과 같이 N*M 맵에서좌측 맨 상단에서 우측 맨 하단까지 갈 수 있는 최단거리를 출력하는 문제이다.

맵에서 0인 구간은 못가고 1인 구간만 갈 수 있으며 목적지까지 도달할 수 없으면 -1을 출력한다.

주의할 점은 N,M은 같을 수도 다를 수도 있다.

큐를 사용해 BFS로 풀었고 이동한 거리는 현재 지점+1로 계산했다.

BFS 개념 복습하기 좋은 문제인 것 같다.

입출력 예

풀이

from collections import deque

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def solution(maps):

    n = len(maps)
    m = len(maps[0])
    
    dq=deque()
    dq.append((0,0))
    
    while dq:
        cx, cy = dq.popleft()
        
        if cx==n-1 and cy==m-1: 
            #for m in maps: print(m)
            return maps[cx][cy]
        
        for i in range(4):
            nx = cx+dx[i]
            ny = cy+dy[i]
            if 0<=nx<n and 0<=ny<m and maps[nx][ny]==1:
                dq.append((nx,ny))
                maps[nx][ny] = maps[cx][cy]+1

    return -1

문제

문제 설명

제한 조건

• s는 길이 1 이상 200 이하인 문자열입니다.
• s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
  • 숫자는 단어의 첫 문자로만 나옵니다.
  • 숫자로만 이루어진 단어는 없습니다.
  • 공백문자가 연속해서 나올 수 있습니다.

입출력 예

유의해야 할 점은 공백문자가 여러 개일 수 있어 단순 split()을 하면 안된다.

풀이 (python)

def solution(s):
    answer = ''
    lspace = list()
    is_space = False
    
    space = ''
    for x in s:
        if x==' ':
            is_space = True
            space+=' '
        elif x!=' ' and is_space==True:
            is_space = False
            lspace.append(space)
            space=''
    if space!='': lspace.append(space)
            
    sp = 0            
    tmp = s.split()
    for t in tmp:
        y = t.lower().capitalize() #문자열 전체 소문자 치환 후 첫글자만 대문자화
        answer+=y
        if sp<len(lspace):
            answer+=lspace[sp]
        sp+=1
        
    return answer

첫번째 반복문에서 공백이 등장할때마다 공백 문자열을 리스트에 추가 했다.

두번째 반복문에서 공백이 아닌 문자열들을 소문자화, 첫 문자만 대문자화한 뒤 

결과 문자열에 재처리한 문자열들과 공백 문자열들을 더해 리턴해주었다.

공백 문자열이 마지막까지 있는 경우도 고려해주어야 모든 케이스가 통과된다.

문제

1칸, 2칸을 갈 수 있을때 n칸 까지 도달하기 위한 경우의 수를 리턴하는 문제이다.

 n=1일때, (1칸) = return 1

n=2일때, (1칸, 1칸), (2칸) = return 2

n=3, n=4 는 그림을참고하면 된다.

결국 피보나치 문제였다.

주의할 점은 n이 1 또는 2일때 어떠한 메모리 할당도 하지 않고 바로 리턴해야 테스트1번이 통과된다.

풀이

def solution(n):
    if n<3: return n
    
    dp=[0]*(n+1)
    dp[1]=1
    dp[2]=2
    
    for i in range(3,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    
    return dp[n]%1234567