키패드 누르기

제출일 : 2020-07-27

문제 풀이 시간 : 30M

---

:link: 문제 link

문제 설명

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• numbers 배열의 크기는 1 이상 1,000 이하입니다.

• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.

• hand는

  "left"

또는

  "right"

입니다.

• "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.

• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

순서대로 눌러야 할 번호가 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5]이고, 오른손잡이입니다.

따라서 "LRLLLRLLRRL"를 return 합니다.

입출력 예 #2

왼손잡이가 [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2]를 순서대로 누르면 사용한 손은 "LRLLRRLLLRR"이 됩니다.

입출력 예 #3

오른손잡이가 [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]를 순서대로 누르면 사용한 손은 "LLRLLRLLRL"이 됩니다.

문제 풀이 접근

배열을 정렬하는 방법을 재정의 하여 문제를 해결하였다.

만약 3과 30이란 값이 들어오게 된다면

3+30과 30+3을 비교하여 정렬하게 되는데 이때는 330이 303보다 크기 때문에 3은 30 보다 큰 수가 되는 것이다. 값을 내름차순으로 정렬하여 앞에서 부터 문자열을 이어 붙여주면 정답이 된다.

문제 풀이 접근

문제에서 주어진 조건을 읽고 로직을 구현하는 문제로 처음 왼쪽과 오른쪽 손의 위치가 주어지고 위치에서

1. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
2. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
3. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

좌표의 위치를 Point배열을 이용하여 저장하고 가운데 2,5,8,0의 숫자를 입력할때 Math.abs(R.x - nums[num].x) + Math.abs(R.y - nums[num].y); 와 같이 거리를 구하고 가까운쪽의 손가락으로 누르게 된다. 만약 갚이 같다면 주어진hand의 손으로 누르게 되며

이를 StringBuilder에 추가해 결과를 출력하였습니다.

코드

언어 : JAVA

package Programmers;

import java.awt.Point;

public class Kakao2020_키패드누르기 {
    public static void main(String[] args) {
        System.out.println(solution(new int[] { 1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5 }, "right"));
        System.out.println(solution(new int[] { 7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2 }, "left"));
        System.out.println(solution(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }, "right"));
    }

    private static String solution(int[] numbers, String hand) {
        Point[] nums = new Point[10];
        nums[0] = new Point(3, 1);
        nums[1] = new Point(0, 0);
        nums[2] = new Point(0, 1);
        nums[3] = new Point(0, 2);
        nums[4] = new Point(1, 0);
        nums[5] = new Point(1, 1);
        nums[6] = new Point(1, 2);
        nums[7] = new Point(2, 0);
        nums[8] = new Point(2, 1);
        nums[9] = new Point(2, 2);
        Point L = new Point(3, 0);
        Point R = new Point(3, 2);

        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            if (num == 1 || num == 4 || num == 7) {
                L.x = nums[num].x;
                L.y = nums[num].y;
                sb.append("L");
            } else if (num == 3 || num == 6 || num == 9) {
                R.x = nums[num].x;
                R.y = nums[num].y;
                sb.append("R");
            } else {
                int disL = Math.abs(L.x - nums[num].x) + Math.abs(L.y - nums[num].y);
                int disR = Math.abs(R.x - nums[num].x) + Math.abs(R.y - nums[num].y);
                if (disL == disR) {
                    if (hand.equals("right")) {
                        R.x = nums[num].x;
                        R.y = nums[num].y;
                        sb.append("R");
                    } else {
                        L.x = nums[num].x;
                        L.y = nums[num].y;
                        sb.append("L");
                    }
                } else {
                    System.out.println(disL + " " + disR);
                    if (disR < disL) {
                        R.x = nums[num].x;
                        R.y = nums[num].y;
                        sb.append("R");
                    } else {
                        L.x = nums[num].x;
                        L.y = nums[num].y;
                        sb.append("L");
                    }
                }
            }
        }
        return sb.toString();
    }
}

1406. 에디터

제출일 : 2020-06-28

문제 풀이 시간 : 1H

난이도 : Silver III

---

:link: 문제 link

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제

입력

abcd
3
P x
L
P y

출력

abcdyx

문제 풀이 접근

문제를 처음 풀때 LinkedList를 이용하여 문제를 풀었다. 코드 1을 작성했고 그 결과 시간초과가 발생하였다.

코드 1

언어 : JAVA

결과 : 시간초과

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.next();
        LinkedList<Character> list = new LinkedList<>();

        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        int cursor = str.length();
        int M = sc.nextInt(); // 명령어의 개수

        for (int k = 0; k < M; k++) {
            char cmd = sc.next().charAt(0);
            switch (cmd) {
                case 'L':
                    if (cursor != 0)
                        cursor--;
                    break;
                case 'D':
                    if (cursor != list.size())
                        cursor++;
                    break;
                case 'B':
                    if (cursor != 0)
                        list.remove(--cursor);
                    break;
                case 'P':
                    char c = sc.next().charAt(0);
                    list.add(cursor++, c);
                    break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (Character c : list) {
            sb.append(c);
        }
        System.out.println(sb);
    }
}

처음 Scanner로 입력을 받고 System.out.println()으로 출력을 했다. 시간초과가 발생해 빠른 BufferedReader과 BufferedWriter로 입출력 방식을 변경했지만 결과는 시간초과가 발생했다.

코드 2

언어 : JAVA

결과 : 시간초과

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();

        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        int cursor = str.length();
        int M = Integer.parseInt(br.readLine()); // 명령어의 개수

        for (int k = 0; k < M; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            char cmd = st.nextToken().charAt(0);
            switch (cmd) {
                case 'L':
                    if (cursor != 0)
                        cursor--;
                    break;
                case 'D':
                    if (cursor != list.size())
                        cursor++;
                    break;
                case 'B':
                    if (cursor != 0)
                        list.remove(--cursor);
                    break;
                case 'P':
                    char c = st.nextToken().charAt(0);
                    list.add(cursor++, c);
                    break;
            }
        }

        for (Character c : list) {
            bw.write(c);
        }
        bw.flush();
    }
}

LinkedList는 ArrayList에 비해 임시 배열을 생성하지 않아 삽입/삭제가 더 유리한 장점을 가지고 있다.

하지만 N번째에 값을 삽입하거나 삭제하려면 인덱스를 통한 접근을 할 수 없기에 N번의 탐색과정이 필요하다.

이 시간을 줄여야 했기에 Iterator를 사용하여 문제를 해결했다.

ListIterator는 Iterator를 상속한 인터페이스다.

Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.

코드 3

언어 : JAVA

메모리 : 115812 kb

실행 시간 : 668 ms

결과 : 맞았습니다!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.StringTokenizer;

public class Silver3_1406_에디터 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();

        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        ListIterator<Character> iter = list.listIterator(list.size());
        int M = Integer.parseInt(br.readLine());

        for (int k = 0; k < M; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            switch (st.nextToken()) {
                case "L":
                    if (iter.hasPrevious())
                        iter.previous();
                    break;
                case "D":
                    if (iter.hasNext())
                        iter.next();
                    break;
                case "B":
                    if (iter.hasPrevious()) {
                        iter.previous();
                        iter.remove();
                    }
                    break;
                case "P":
                    iter.add(st.nextToken().charAt(0));
                    break;
            }
        }

        for (Character c : list) {
            bw.write(c);
        }
        bw.flush();
    }
}

문제 해결을 위해 블로그의 글들을 보니 대부분 2개의 스택을 이용하여 구현하여 문제를 해결했다. 스텍을 활용한 문제풀이의 핵심 아이디어는 왼쪽과 오른쪽 스택을 구분지어 커서의 위치를 항상 왼쪽 Top에 위치하여 문제를 푸는 것이다.

코드 4

언어 : JAVA

메모리 : 119188 kb

실행 시간 : 804 ms

결과 : 맞았습니다!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Silver3_1406_에디터_ver2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str = br.readLine();

        Stack<Character> left = new Stack<>();
        Stack<Character> right = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            left.add(str.charAt(i));
        }

        int M = Integer.parseInt(br.readLine());

        for (int k = 0; k < M; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            switch (st.nextToken()) {
                case "L":
                    if (!left.isEmpty())
                        right.push(left.pop());
                    break;
                case "D":
                    if (!right.isEmpty())
                        left.push(right.pop());
                    break;
                case "B":
                    if (!left.isEmpty())
                        left.pop();
                    break;
                case "P":
                    left.push(st.nextToken().charAt(0));
                    break;
            }
        }

        while (!left.isEmpty()) {
            right.push(left.pop());
        }
        while (!right.isEmpty()) {
            bw.write(right.pop());
        }

        bw.flush();
    }
}

📚 Reference :books:

https://minhamina.tistory.com/17

[SWEA] 1208. [S/W 문제해결 기본] 1일차 - Flatten - (Java)

제출일 : 2020-06-19

문제 풀이 시간 : 30M

난이도 : ★★★

---

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh

문제

한 쪽 벽면에 다음과 같이 노란색 상자들이 쌓여 있다.

높은 곳의 상자를 낮은 곳에 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 평탄화라고 한다.

평탄화를 모두 수행하고 나면, 가장 높은 곳과 가장 낮은 곳의 차이가 최대 1 이내가 된다.

평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려있을 때, 제한된 횟수만큼 옮기는 작업을 한 후 최고점과 최저점의 차이를 반환하는 프로그램을 작성하시오.

가장 높은 곳에 있는 상자를 가장 낮은 곳으로 옮기는 작업을 덤프라고 정의한다.

위의 예시에서 제1회 덤프를 수행한 이후 화면은 다음과 같다.

A부분의 상자를 가장 낮은 B부분에 덤프하였으며, A대신 A’부분의 상자를 사용해도 무방하다.

다음은 제2회 덤프를 수행한 이후의 화면이다.

A’부분의 상자를 옮겨서, C부분에 덤프하였다. 이때 C 대신 C’부분에 덤프해도 무방하다.

2회의 덤프 후, 최고점과 최저점의 차이는 8 – 2 = 6 이 되었다 (최초덤프 이전에는 9 – 1 = 8 이었다).

덤프 횟수가 2회로 제한된다면, 이 예시 문제의 정답은 6이 된다.

제약 사항

가로 길이는 항상 100으로 주어진다.

모든 위치에서 상자의 높이는 1이상 100이하로 주어진다.

덤프 횟수는 1이상 1000이하로 주어진다.

주어진 덤프 횟수 이내에 평탄화가 완료되면 더 이상 덤프를 수행할 수 없으므로 그 때의 최고점과 최저점의 높이 차를 반환한다 (주어진 data에 따라 0 또는 1이 된다).

입력

총 10개의 테스트 케이스가 주어지며, 각 테스트 케이스의 첫 번째 줄에는 덤프 횟수가 주어진다. 그리고 다음 줄에 각 상자의 높이값이 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 최고점과 최저점의 높이 차를 출력한다.

예제

입력

834
42 68 35 1 70 25 79 59 63 65 6 46 82 28 62 92 96 43 28 37 92 5 3 54 93 83 22 17 19 96 ...
617
16 40 59 5 31 78 7 74 87 22 46 25 73 71 30 78 74 98 13 87 91 62 37 56 68 56 75 32 53 ...
...

출력

#1 13
#2 32
...

문제 풀이 접근

문제를 2가지 방법으로 풀어보았다.

첫번째 방법은 주어진 입력을 그대로 map의 배열에 담은 뒤

1. 정렬을 수행한다
2. 맨앞의 값(map[0])은 +1, 맨 뒤의 값(map[99])은 +1의 연산을 수행한다.

위 과정을 dump 수 만큼 반복한 뒤 결과를 출력(map[99]-map[0])하였고

두번째 풀이는 입력을 받을 때 상자의 개수를 카운트 하는 형식으로 값을 담았고 입력을 받을때 min값과 max값을 구하였다.

1. min개의 개수를 가진 상자를 -1 하고 min+1개의 개수를 가진 상자를 +1
2. max개의 개수를 가진 상자를 -1 하고 max-1개의 개수를 가진 상자를 +1
3. map[min], map[max]값이 0이라면 min, max를 조정한다.

위 과정을 dump수만큼 반복한 뒤 결과를 출력(max-min)하였다.

처음 문제에서는 dump 수 만큼 정렬을 진행하기 때문에 속도가 느릴 것 같아 두번째 풀이로 문제를 한번 더 풀어보았다. 생각보다 속도측 면에서 많은 차이가 나지 않은 것이 조금 놀랐다.

코드 1

언어 : JAVA

메모리 : 24,804 kb

실행 시간 : 179 ms

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = 10;
        int N = 100;
        for (int tc = 1; tc <= T; tc++) {
            int dump = sc.nextInt();
            int[] map = new int[N];
            for (int i = 0; i < N; i++) {
                map[i] = sc.nextInt();
            }
            for (int i = 0; i < dump; i++) {
                Arrays.sort(map);
                map[0]++;
                map[99]--;
            }
            Arrays.sort(map);
            System.out.println("#" + tc + " " + (map[99] - map[0]));
        } // end of TC
    }// end of Main
}

코드 2

언어 : JAVA

메모리 : 24,444 kb

실행 시간 : 160 ms

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);
        int T = 10;
        for (int tc = 1; tc <= T; tc++) {
            int dump = sc.nextInt();
            int[] map = new int[101];
            int max = 1;
            int min = 100;
            for (int i = 0; i < 100; i++) {
                int tmp = sc.nextInt();
                map[tmp]++;
                max = Math.max(max, tmp);
                min = Math.min(min, tmp);
            }
            for (int i = 0; i < dump; i++) {
                map[min]--;
                map[min + 1]++;

                map[max]--;
                map[max - 1]++;

                while (map[min] == 0) {
                    min++;
                }

                while (map[max] == 0) {
                    max--;
                }
            }

            System.out.println("#" + tc + " " + (max - min));
        } // end of TC
    }// end of Main
}

[SWEA] 1206. [S/W 문제해결 기본] 1일차 - View - (Java)

제출일 : 2020-06-17

문제 풀이 시간 : 30M

난이도 : ★★★

---

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh

문제

강변에 빌딩들이 옆으로 빽빽하게 밀집한 지역이 있다.

이곳에서는 빌딩들이 너무 좌우로 밀집하여, 강에 대한 조망은 모든 세대에서 좋지만 왼쪽 또는 오른쪽 창문을 열었을 때 바로 앞에 옆 건물이 보이는 경우가 허다하였다.

그래서 이 지역에서는 왼쪽과 오른쪽으로 창문을 열었을 때, 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다고 말한다.

빌딩들에 대한 정보가 주어질 때, 조망권이 확보된 세대의 수를 반환하는 프로그램을 작성하시오.

아래와 같이 강변에 8채의 빌딩이 있을 때, 연두색으로 색칠된 여섯 세대에서는 좌우로 2칸 이상의 공백이 존재하므로 조망권이 확보된다. 따라서 답은 6이 된다.

A와 B로 표시된 세대의 경우는 왼쪽 조망은 2칸 이상 확보가 되었지만 오른쪽 조망은 한 칸 밖에 확보가 되지 않으므로 조망권을 확보하지 못하였다.

C의 경우는 반대로 오른쪽 조망은 2칸이 확보가 되었지만 왼쪽 조망이 한 칸 밖에 확보되지 않았다.

제약 사항

가로 길이는 항상 1000이하로 주어진다.

맨 왼쪽 두 칸과 맨 오른쪽 두 칸에는 건물이 지어지지 않는다. (예시에서 빨간색 땅 부분)

각 빌딩의 높이는 최대 255이다.

입력

입력 파일의 첫 번째 줄에는 테스트케이스의 길이가 주어진다. 그 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 조망권이 확보된 세대의 수를 출력한다.

예제

입력

100
0 0 225 214 82 73 241 233 179 219 135 62 36 13 6 71 179 77 67 139 31 90 9 37 ...
1000
0 0 225 214 82 73 241 233 179 219 135 62 36 13 6 71 179 77 67 139 31 90 9 37 ...
...

출력

#1 691
#2 9092
...

문제 풀이 접근

현재 위치를 기준으로 좌우 2칸의 빌딩의 높이와 비교하여 문제를 해결하면 된다.

문제 풀이는 좌우 2개의 빌딩의 최대 높이를 구하고 현재 빌딩보다 낮다면 얼마나 낮은지를 카운트 하여 문제를 해결하였습니다.

코드

언어 : JAVA

메모리 : 37,200 kb

실행 시간 : 182 ms

package SWEA.문제해결_기본;

import java.io.FileInputStream;
import java.util.Scanner;

public class Day01_View {
    static int N;
    static int[] building;

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("res/input.txt"));
        Scanner sc = new Scanner(System.in);

        int T = 10;
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt(); // 가로 길이
            building = new int[N];
            for (int i = 0; i < N; i++) {
                building[i] = sc.nextInt();
            }

            int cnt = 0;
            for (int i = 2; i < N - 2; i++) {
                int max = Math.max(building[i - 2], Math.max(building[i - 1], Math.max(building[i + 1], building[i + 2])));
                if (building[i] - max > 0)
                    cnt += building[i] - max;
            }

            System.out.println("#" + tc + " " + cnt);
        } // end of TC
    } // end of Main
}

[BOJ] 17822. 원판 돌리기 - (Java)

제출일 : 2020-06-01

문제 풀이 시간 : 1H30M

난이도 : ★★★★

---

link : https://www.acmicpc.net/problem/17822

문제

• 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

  • (i, 1)은 (i, 2), (i, M)과 인접하다.
  • (i, M)은 (i, M-1), (i, 1)과 인접하다.
  • (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
  • (1, j)는 (2, j)와 인접하다.
  • (N, j)는 (N-1, j)와 인접하다.
  • (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

  아래 그림은 N = 3, M = 4인 경우이다.

  

  원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

  다음 그림은 원판을 회전시킨 예시이다.

  1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

  원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

  1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
  2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
     1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
     2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

  원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

예제

입력

4 4 3
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2

출력

22

문제 풀이 접근

시뮬레이션 문제

주어진 조건을 천천히 읽고 놓치는 부분 없이 코딩하면 되는 문제

놓치기 쉬운 부분은

1. 원판의 수를 지울 때, 원판에 인접한 수가 없는 경우 평균을 구하고 평균보다 큰 수는 1을 빼고 평균보다 작은 수는 1을 더한다.
   • 평균 값을 INT형으로 구하게 된다면 문제의 정답을 구할 수 없다.
2. 배열을 이용하여 문제를 해결했다. 배열의 0번째 인덱스 값과 M-1번째 인덱스 값은 서로 인접함을 주의 해야 한다.

코드

언어 : JAVA

메모리 : 31940 kb

실행 시간 : 328 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, T;
    static int[][] map;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        T = sc.nextInt();

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        for (int t = 0; t < T; t++) {
            int x = sc.nextInt();
            int d = sc.nextInt();
            int k = sc.nextInt();
            rotate(x, d, k);
            if (!remove())
                replace();
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1)
                    ans += map[i][j];
            }
        }
        System.out.println(ans);
    }

    private static void replace() {
        int sum = 0, cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1) {
                    sum += map[i][j];
                    cnt++;
                }
            }
        }
        double avg = sum / (double) cnt;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != -1) {
                    if ((double) map[i][j] > avg)
                        map[i][j]--;
                    else if ((double) map[i][j] < avg)
                        map[i][j]++;
                }
            }
        }
    }

    private static boolean remove() {
        boolean flag = false;
        boolean[][] visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1 || visit[i][j])
                    continue;
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[] { i, j, map[i][j] });
                visit[i][j] = true;
                while (!q.isEmpty()) {
                    int[] now = q.poll();
                    for (int k = 0; k < dr.length; k++) {
                        int nr = now[0] + dr[k];
                        int nc = now[1] + dc[k];

                        if (nr < 0 || nr >= N)
                            continue;

                        if (nc == -1)
                            nc = M - 1;
                        else if (nc == M)
                            nc = 0;
                        if (visit[nr][nc])
                            continue;
                        if (map[nr][nc] == now[2]) {
                            visit[nr][nc] = true;
                            q.add(new int[] { nr, nc, now[2] });
                            map[now[0]][now[1]] = -1;
                            map[nr][nc] = -1;
                            flag = true;
                        }
                    }
                }
            }
        }
        return flag;
    }

    private static void rotate(int x, int d, int k) {
        for (int r = 0; r < N; r++) {
            if ((r + 1) % x != 0)
                continue;
            if (d == 0) {
                // 시계방향 회전
                for (int times = 0; times < k; times++) {
                    // k 칸 이동
                    int[] tmp = map[r].clone();
                    map[r][0] = tmp[M - 1];
                    for (int i = 1; i < M; i++) {
                        map[r][i] = tmp[i - 1];
                    }
                }
            } else {
                // 반시계 방향 회전
                for (int times = 0; times < k; times++) {
                    // k 칸 이동
                    int[] tmp = map[r].clone();
                    map[r][M - 1] = tmp[0];
                    for (int i = 0; i < M - 1; i++) {
                        map[r][i] = tmp[i + 1];
                    }
                }
            }
        }
    }

}

[BOJ] 17780. 새로운 게임 - (Java)

제출일 : 2020-05-18

문제 풀이 시간 : 4H

난이도 : ★★★★

---

link : https://www.acmicpc.net/problem/17780

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

제한

• 4 ≤ N ≤ 12
• 4 ≤ K ≤ 10

예제

입력

4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2

출력

-1

문제 풀이 접근

시뮬레이션 문제

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다.

말을 옮길 때 현재 움직이려는 말이 가장 밑에 있는 말인지 확인하는 과정을 거쳐야 한다. -> state[][]을 사용!

코드

언어 : JAVA

메모리 : 14840 kb

실행 시간 : 136 ms

package BOJ.Simulation;

import java.util.LinkedList;
import java.util.Scanner;

public class Gold2_17780_새로운게임 {
    static final int WHITE = 0, RED = 1, BLUE = 2;
    static final int[] change = { 1, 0, 3, 2 };
    // →, ←, ↑, ↓
    static final int[] dr = { 0, 0, -1, 1 };
    static final int[] dc = { 1, -1, 0, 0 };

    static int N, K;
    static int[][] map;
    static LinkedList<Integer>[][] state;
    static Horse[] horses;

    static class Horse {
        int r, c, dir;

        Horse(int r, int c, int dir) {
            this.r = r;
            this.c = c;
            this.dir = dir;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 체스판의 크기 N
        K = sc.nextInt(); // 말의 개수 K

        map = new int[N][N]; // 체스판 색상 정보
        state = new LinkedList[N][N]; // 체스판에 쌓인 말의 순서

        // 체스판의 정보
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                state[i][j] = new LinkedList<>();
            }
        }

        // 말의 정보
        horses = new Horse[K + 1]; // 1 ~ K번 말
        for (int i = 1; i <= K; i++) {
            int r = sc.nextInt() - 1;
            int c = sc.nextInt() - 1;
            int dir = sc.nextInt() - 1;
            horses[i] = new Horse(r, c, dir);
            state[r][c].add(i);
        }

        System.out.println(start());

    }

    private static int start() {
        boolean flag = true;
        int times = 0;
        while (flag) {
            times++;
            if (times > 1000)
                break;

            for (int i = 1; i <= K; i++) {
                Horse h = horses[i];
                int r = h.r;
                int c = h.c;

                // 가장 아래쪽 말이 아니라면 PASS
                if (state[r][c].get(0) != i)
                    continue;

                int nr = r + dr[h.dir];
                int nc = c + dc[h.dir];

                // 말이 이동하려는 칸이 파란색인 경우 + 체스판을 벗어나는 경우
                if (!isRange(nr, nc) || map[nr][nc] == BLUE) {
                    // 방향 반대로
                    h.dir = change[h.dir];
                    nr = r + dr[h.dir];
                    nc = c + dc[h.dir];
                }

                // 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우
                if (!isRange(nr, nc) || map[nr][nc] == BLUE) {
                    continue;
                }
                // 말이 이동하려는 칸이 빨간색인 경우
                else if (map[nr][nc] == RED) {
                    // 순서를 반대로 모든 말이 이동
                    for (int j = state[r][c].size() - 1; j >= 0; j--) {
                        int tmp = state[r][c].get(j);
                        state[nr][nc].add(tmp);
                        horses[tmp].r = nr;
                        horses[tmp].c = nc;
                    }
                    state[r][c].clear();
                }
                // 말이 이동하려는 칸이 흰색인 경우
                else {
                    // 모든 말이 이동
                    for (int j = 0; j < state[r][c].size(); j++) {
                        int tmp = state[r][c].get(j);
                        state[nr][nc].add(tmp);
                        horses[tmp].r = nr;
                        horses[tmp].c = nc;
                    }
                    state[r][c].clear();
                }

                // 이동한 곳에 말이 4개 이상 있는가?
                if (state[nr][nc].size() >= 4) {
                    flag = false;
                    break;
                }
            }
        }
        return flag ? -1 : times;
    }

    static boolean isRange(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }
}

[Programmers] K번째수 - (Java)

Problem

제출일 : 2020-05-15

문제 풀이 시간 : 5M

난이도 : ★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42748

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

Solution & Inpression

정렬 문제

Arrays.copyOfRange(original, from, to) 사용하여 문제를 풀어도 되지만 리스트를 사용하여 문제를 해결하였습니다.

Code

언어 : JAVA

package Programmers;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

public class Level1_K번째수 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(solution(new int[] { 1, 5, 2, 6, 3, 7, 4 },
                new int[][] { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 }, }))); // [5,6,3]
    }

    public static int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for (int i = 0; i < commands.length; i++) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int j = commands[i][0] - 1; j < commands[i][1]; j++) {
                list.add(array[j]);
            }
            Collections.sort(list);
            answer[i] = list.get(commands[i][2] - 1);
        }

        return answer;
    }
}

[Programmers] 체육복 - (Java)

Problem

제출일 : 2020-05-15

문제 풀이 시간 : 10M

난이도 : ★

---

link : https://programmers.co.kr/learn/courses/30/lessons/42862

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

Solution & Inpression

그리디 문제!!

• 잃어버린 사람이 앞사람에게 먼저 물어보고 없으면 뒷사람.

문제 의 조건 중 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 에 유의 하여 문제를 풀면 된다.

Code

언어 : JAVA

package Programmers;

public class Level1_체육복 {
    public static void main(String[] args) {
        System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 1, 3, 5 })); // 5
        System.out.println(solution(5, new int[] { 2, 4 }, new int[] { 3 })); // 4
        System.out.println(solution(3, new int[] { 3 }, new int[] { 1 })); // 2
    }

    public static int solution(int n, int[] lost, int[] reserve) {
        int[] student = new int[n];
        for (int i = 0; i < lost.length; i++) {
            student[lost[i] - 1]--;
        }
        for (int i = 0; i < reserve.length; i++) {
            student[reserve[i] - 1]++;
        }

        int answer = n;
        for (int i = 0; i < student.length; i++) {
            if (student[i] == -1) {
                if (i - 1 >= 0 && student[i - 1] == 1) {
                    student[i]++;
                    student[i - 1]--;
                } else if (i + 1 < student.length && student[i + 1] == 1) {
                    student[i]++;
                    student[i + 1]--;
                } else
                    answer--;
            }
        }
        return answer;
    }
}