Part 01. 연습문제 풀이 2 [zerobase]

자료구조와 알고리듬 With Java/[zerobase] Algorithm

Part 01. 연습문제 풀이 2 [zerobase]

계란💕 2022. 5. 11. 19:21

1. 로마 숫자 표기를 정수로 바꾸기

- map을 이용해서 각각의 문자에 해당하는 값을 함께 넣어준다.

- s를 chararray로 바꿔서 작은 값을 가지는 키가 앞에 오면 그 값을 마이너스하도록 sum 식을 세운다.

- 가장 마지막 글자는 더한다.

<hide/>
import java.util.HashMap;
public class Practice1 {

    public static void solution(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int sum = 0;
        char[] arr = s.toCharArray();

        for(int i = 0; i < arr.length - 1; ++i){
            if(map.get(arr[i] ) < map.get(arr[i + 1])){ // 작은 기호가 앞에 오는 경우
                sum -= map.get(arr[i]);
            }else{
                sum += map.get(arr[i]);
            }
        }
        // 마지막 값은 바로 더해준다.
        sum += map.get(arr[arr.length - 1]);
        System.out.println(sum);
    }

    public static void main(String[] args) {
        // Test code
        solution("III");
        solution("IV");
        solution("VI");
        solution("XIII");
        solution("XXVI");
        solution("MCMXCIV");
    }
}

Note) 실행 결과

2. 정수를 로마숫자로 바꾸기

- String 배열과, int 배열을 만들어서 내림차순으로 각각 값을 넣어준다.

- 900, 400, 40, 4를 뜻하는 CM/ CD/ XL/ IV도 각각 배열에 넣는다.

- index를 뜻하는 i를 만들어서 num에서 values[i]를 하나씩 빼면서 그에 대응하는 로마숫자를 result에 하나씩 넣는다.

<hide/>
import java.util.HashMap;
public class Practice2 {
    public static String solution(int num){
        String result = "";
        String [] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        int [] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        int i = 0;
        while(num > 0){
            while(num >= values[i]){
                result += roman[i];
                num -= values[i];
            }
            ++i;
        }
        return result;
    }

    public static void main(String[] args) {
        // Test code
        System.out.println(solution(3));
        System.out.println(solution(4));
        System.out.println(solution(6));
        System.out.println(solution(13));
        System.out.println(solution(26));
        System.out.println(solution(1994));
    }
}

Note) 실행 결과

3. 커서 옮기기 (편집기 구현)

L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시)
D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시)
B : 커서 왼쪽에 있는 문자를 삭제 (커서가 문장의 맨 앞이면 무시)
P x : x라는 문자를 커서 왼쪽에 추가

- 커서는 문자열에서 편집이 시작되는 기준 위치로 문장의 맨 앞, 맨 뒤, 중간에 위치할 수 있다.

<hide/>
import java.util.ArrayList;
public class Practice3 {
    public static String solution(String input, String cmd) {

        StringBuffer sb = new StringBuffer(input);
        ArrayList<String> cmdArr = new ArrayList<>();

        for(String s : cmd.split(" ")){
            cmdArr.add(s);
        }

        int curSor = sb.length();
        int cmdIdx = 0;
        while(cmdIdx != cmdArr.size()){
            String cur = cmdArr.get(cmdIdx);
            if(cur.equals("L")){
                curSor = Math.max(0, curSor - 1);
                
            }else if(cur.equals("D")){
                curSor = Math.min(sb.length(), curSor + 1);

            }else if(cur.equals("B")){
                if(curSor == 0){    //지울게 없으니까
                    ++cmdIdx;
                    continue;
                }
                sb.delete(curSor - 1, curSor); // 좌측에 있는 하나를 지운다.
                curSor = Math.max(0, curSor - 1);

            }else if(cur.equals("P")){
                String s = cmdArr.get(++cmdIdx);    // 꺼낼 때마다 오른족으로 한 칸씩 이동
                sb.insert(curSor, s);
                curSor += 1;
            }
            ++cmdIdx;
        }
        return  sb.toString();
    }

    public static void main(String[] args) {
        // test code
        System.out.println(solution("aba", "L B"));
        System.out.println(solution("abcd", "P x L P y"));
        System.out.println(solution("abc", "L L L P x L B P y"));
        System.out.println(solution("a", "B B L L D D P a P b P c"));
    }
}

Note) 실행 결과

<hide/>
[입출력 예시]
초기문자열	명령어						 결과 출력
"aba"		"L B"						"aa"
"abcd"		"P x L P y"					"abcdyx"
"abc"		"L L L P x L B P y"			"yxabc"
"a"			"B B L L D D P a P b P c"	"abc"

4. 키로깅 프로그램

- 특수 작전을 위해 상대방의 PC에 키보드 입력 내용을 얻을 수 있는 키로깅 프로그램을 설치했다.

- 해당 키로깅 프로그램으로부터는 아래와 같이 특정 값으로 내용이 수신된다.

8 : Backspace
16 : Shift
20 : Caps Lock
32 : Space bar
37 : 키보드 왼쪽 화살표
39 : 키보드 오른쪽 화살표
155: Insert
127: Delete
97~122: 알파벳 소문자 (기본 입력은 소문자 기준, Shift 나 Caps Lock 에 의해 변경)
48~57: 숫자 0~9

- (이 외의 값은 들어오지 않는다고 가정)

- 키로깅 프로그램으로부터 수신된 데이터를 원래 내용으로 복구하는 프로그램을 작성하세요.

<hide/>
public class Practice4 {
    public static String solution(int[] keyLog) {
        final int BACK_SPACE = 8;
        final int SHIFT = 16;
        final int CAPS_LOCK = 20;
        final int SPACE_BAR = 32;
        final int KEY_LEFT = 37;
        final int KEY_RIGHT = 39;
        final int INSERT = 155;
        final int DELETE = 127;

        StringBuffer sb = new StringBuffer();
        int step = (int)'a' - (int)'A';
        int curSor = 0;
        int cmdIdx = 0;
        boolean isShift = false;    // 눌렸는지 안 눌렸는지
        boolean isCapsLock = false;
        boolean isInsert = false;
        while(cmdIdx != keyLog.length){
            int cur = keyLog[cmdIdx];
            if(cur == BACK_SPACE){
                if(curSor == 0){
                    ++cmdIdx;
                    continue;
                }
                sb.delete(curSor - 1, curSor);
                curSor = Math.max(0, curSor - 1);
            }else if(cur == SHIFT){
                isShift = true;
            }else if(cur == CAPS_LOCK){
                isCapsLock = !isCapsLock;   // 기존의 값을 반전시켜서 대입
            }else if(cur == SPACE_BAR){
                inputData(sb, ' ', curSor, isInsert);
                curSor += 1;

            }else if(cur == KEY_LEFT){
                curSor = Math.max(0, curSor - 1);

            } else if (cur == KEY_RIGHT) {
                curSor = Math.min(sb.length() , curSor + 1);

            }else if(cur == INSERT){
                isInsert = !isInsert;

            }else if(cur == DELETE){
                if(curSor == sb.length()){  // 가장 마지막에 있으면 지울게 없다.
                    ++cmdIdx;
                    continue;
                }
                sb.delete(curSor, curSor + 1);
                
            } else if (97 <= cur && cur <= 122 ) {      // 알파벳인 경우
                int data = cur;

                if(isCapsLock && isShift){
                    data = cur;// 아무것도 하지 않는다.

                } else if (isCapsLock || isShift) {
                    data -= step;   // 소문자로 바꿔준다.
                }
                inputData(sb, (char)data, curSor, isInsert );
                isShift = false;
                curSor += 1;

            }else if(48 <= cur && cur <= 57){

                if(isShift){
                    char[] specialKey = {')', '!', '@', '#', '$', '%', '^', '&' , '*', '(' };
                    inputData(sb, specialKey[cur - '0'],curSor, isInsert );
                }else{
                    inputData(sb, (char)cur, curSor, isInsert);
                }
                isShift = false;
                curSor += 1;
            }
            ++cmdIdx;
        }
        return sb.toString();
    }
    
    public static void inputData(StringBuffer sb, char data, int curSor, boolean isInsert){
        if(isInsert == false){
            sb.insert(curSor, data);
        }else{
            sb.setCharAt(curSor, data); //해당 위치를 데이터로 바꾼다.
        }
    }
    
    public static void main(String[] args) {
        // Test code
        int[] keyLog = {16, 106, 101, 108, 108, 111, 37, 37, 37, 37, 37, 155, 16, 104};
        System.out.println(solution(keyLog));

        keyLog = new int[]{20, 104, 16, 105, 32, 20, 16, 106, 97, 118, 97};
        System.out.println(solution(keyLog));

        keyLog = new int[]{49, 51, 8, 50, 51, 53, 55, 37, 37, 127, 127, 52, 53};
        System.out.println(solution(keyLog));

        keyLog = new int[]{20, 97, 98, 16, 99, 16, 100, 16, 49, 16, 50, 16, 51};
        System.out.println(solution(keyLog));
    }
}

Note) 입출력 예시

<hide/>
수신 내용														  결과
16, 106, 101, 108, 108, 111, 37, 37, 37, 37, 37, 155, 16, 104	"Hello"
20, 104, 16, 105, 32, 20, 16, 106, 97, 118, 97					"Hi Java"
49 51 8 50 51 53 55 37 37 127 127 52 53							"12345"
20 65 66 16 67 16 68 49 50 51									"ABcd!@#

5. 사탕 나눠주기

- N 명의 아이들이 한 줄로 서있다.
- 각각의 아이들은 점수 표를 가지고 있는데 점수 표에 따라 다음과 같은 규칙으로 사탕을 나누어 줘야 한다.

적어도 1개 이상의 사탕을 나누어줘야 한다.
점수가 높은 아이에게는 바로 옆의 아이 보다는 사탕을 많이 줘야 한다.

- N 명의 아이들에 대한 점수 표가 ratings 배열에 주어질 때, 나누어 줘야하는 최소한의 사탕 개수를 출력하세요.

<hide/>

public class Practice5 {
    public static int solution(int[] ratings) {
        if(ratings == null || ratings.length == 0){
            return 0;
        }
        int result = 1;
        int upCnt = 1;  // 커지는 방향으로 가는 변수
        int downCnt = 0; // 작아직는 방향으로 가는 변수
        int peak = 0;

        for(int i = 1; i < ratings.length;++i){
            if(ratings[i] > ratings[i -1]){     // 증가하는 경우
                ++upCnt;
                peak = upCnt;   //  peak를 갱신해준다.
                downCnt = 0;
                result += upCnt;

            }else if(ratings[i] == ratings[i - 1]){     // 같은 경우
                upCnt = 1;
                downCnt = 0;    // 방향 전환에 따른 초기화
                peak = 0;
                result += 1;

            }else{
                ++downCnt;
                upCnt = 1;
                result += downCnt;

                //peak가 0일 때 항상 실행된다.
                if(peak <= downCnt){    //연속적으로 증가하다가 peak를 넘어서면 result를 넘는 경우
                    result += 1;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // Test code
        int[] ratings = {1, 2, 3};
        System.out.println(solution(ratings));

        ratings = new int[]{3, 2, 1};
        System.out.println(solution(ratings));

        ratings = new int[]{1, 0, 2};
        System.out.println(solution(ratings));

        ratings = new int[]{1, 2, 2};
        System.out.println(solution(ratings));

        ratings = new int[]{1, 3, 5, 3, 1, 3, 5, 7, 5, 3, 1, 0};
        System.out.println(solution(ratings));
    }
}

Note) 입출력 예시

<hide/>
 입력									 출력
1 2 3									6
3 2 1									6
1 0 2									5
1 2 2									4
1, 3, 5, 3, 1, 3, 5, 7, 5, 3, 1, 0		29

출처: https://zero-base.co.kr/

저작자표시

'자료구조와 알고리듬 With Java > [zerobase] Algorithm' 카테고리의 다른 글

Chapter 02. 선형 자료구조 (0)	2022.05.30
Chapter 01. 기초 수학 [zerobase] (0)	2022.05.22
[Java 핵심 복습] (0)	2022.05.13
Part 01. 연습문제 풀이 3 [zerobase] (0)	2022.05.12
Part.01연습문제 풀이 [zerobase] (0)	2022.05.11

현재글Part 01. 연습문제 풀이 2 [zerobase]

Backend Developer lan4250@naver.com https://github.com/goraneee

백준, Stack, Java, BFS, dp, DB, mysql, SQL, 프로그래머스, GIT, 제로베이스 스쿨, 데이터베이스, 제로베이스 백엔드, 자바, 코드업, 알고리즘, Queue, JPA, dfs, 스프링,

Today :
Yesterday :

계란 블로그