C++ Level1 - 나머지 문제들(?)1

#작성양식

1. 필요 가정 도출, 내가 생각한 알고리즘 서술

2. 시간/공간복잡도 계산

3. 개선점 찾기

 

앞으로 1,3번은 필수로 작성하기!

 

---

1. 폰켓몬(찾아라 프로그래밍 마에스터)

 

• 알고리즘 서술

1. 중복제거

2. 배열에 추가(같으면 pass, 다르면 배열에 추가)

3. n/2개 check

#include <vector>
#include <algorithm>

using namespace std;
vector<int>cnt;
int solution(vector<int> nums)
{
    
    int answer = 0;
    sort(nums.begin(),nums.end());
    for(int i=0;i<nums.size();i++){
        if(nums[i]!=nums[i+1]){
            cnt.push_back(nums[i]);
        }
    }
    if(cnt.size()<=nums.size()/2){
        answer=cnt.size();
    }else{
        answer=nums.size()/2;
    }
    return answer;
    
}

 

 

---

2. 예산(Summer/Winter Coding(~2018)

• 알고리즘 서식

1. 정렬

2. 순서대로 sum 구하기

3. if 예산보다 같거나 작으면 ncnt++, 크면 break

 

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int solution(vector<int> d, int budget) {
    int answer = 0, ncnt=0,sum=0;
    
    sort(d.begin(),d.end());
    for(int i=0;i<d.size();i++){
        sum+=d[i];
        if(sum<=budget){
            ncnt++;
        }else{
            break;
        }
    }
    answer=ncnt;
    
    return answer;
}

 

---

 

 

3. 키패드 누르기(2020년 카카오 인턴쉽)

• 알고리즘 서식

1. 키패드 생성, 시작 위치 초기화

2. 숫자 선택시 손가락 위치 찾기 -> fingpoint()

3. 1,4,7-> left       3,6,9 ->right        2,5,8,0 -> hand, fingpoint 확인

3.1) 현재 fingpoint와 입력할 숫자 사이 거리 구하기

3.2) 거리 비교하여 L/R 입력

4. 전체 값 출력

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
// 시작 손가락 위치 초기화
int ln=10;//* 
int rn=12;//#
int ln_x,ln_y,rn_x,rn_y;
vector<vector<int>> keypad={{1,2,3},{4,5,6},{7,8,9},{10,0,12}};// 키패드
void fingpoint() {
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 3; y++) {
            if (keypad[x][y] == ln) {
                ln_x = x;
                ln_y = y;
            }
            if (keypad[x][y] == rn) {
                rn_x = x;
                rn_y = y;
            }
        }
    }
}


string solution(vector<int> num, string hand) {
    string answer = "";
  
    for(int i=0;i<num.size();i++){
        fingpoint();
        if(num[i]==1||num[i]==4||num[i]==7){
            ln=num[i];
            answer.push_back('L');
        }else if(num[i]==3||num[i]==6||num[i]==9){
            rn=num[i];
            answer.push_back('R');
        }else{ // hand, 거리 check
            for(int x=0;x<4;x++){
                for(int y=0;y<3;y++){
                    if(num[i]==keypad[x][y]){ // 1. 좌표 거리 구함
                        int ldis=abs(x-ln_x)+abs(y-ln_y);
                        int rdis=abs(x-rn_x)+abs(y-rn_y);
                        
                        // 2. hand 비교(거리가 같은 경우)
                        if(ldis==rdis){
                            if(hand=="left"){
                                ln=num[i];
                                answer.push_back('L');
                            }else if(hand=="right"){
                                rn=num[i];
                                answer.push_back('R');
                            }
                        }else if(ldis>rdis){
                            rn=num[i];
                            answer.push_back('R');
                        }else if(ldis<rdis){
                            ln=num[i];
                            answer.push_back('L');
                        }
                    }
                }
            }
        }
    }    
    return answer;
}

 

 

• 개선점

키패드 초기화 할때 0을 11로 초기화 해서 시간이 좀 걸렸다. 요구사항 제대로 확인하기