[ 코드트리 조별과제 ] 프로그래밍 연습 - Chapter4. 시뮬레이션(1)

 1. 날짜와 시간 계산 

 

[ 개념문제 ]

2011년 11월 11일 a시 b분에서 시작하여 2011년 11월 11일 c시 d분까지 몇 분이 걸리는지를 계산하는 프로그램을 작성해보세요.

 

풀이1 : a시 b분에서 시작하여 1분 단위로 시뮬레이션을 하며, 60분이 되면 시간을 늘리고 분을 다시 0으로 맞추는 식으로 진행한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt(); //hour
        int b = sc.nextInt(); //min
        int c = sc.nextInt();
        int d = sc.nextInt();

        int elapsedTime = 0;

        while(true){
            if(a==c && b==d) break;
            elapsedTime++;
            
            b++;
            if(b==60){
                a++;
                b=0;
            }
        }

        System.out.println(elapsedTime);
    }
}

 

 

풀이2 : 0시 0분에서 시작하여 각 시간까지 걸리는 분을 계산하여 그 차이를 계산하는 식으로 진행, 시뮬레이션을 하지 않아도 답을 구할 수 있다.

 

ex) 2시 5분에서 4시 1분이 되기 위한 시간 계산

0시 0분부터 4시 1분까지 소요되는 241분 - 0시 0분부터 2시 5분까지 소요되는 125분 = 126분 소요

 

 

[ 개념문제 ]

import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt(); 
        int d = sc.nextInt();

        System.out.println((c * 60 + d) - (a * 60 + b));
    }
}

 

 

 

 2. Notation 

2진수로 변환하기

: 일반적인 10진수 -> 2진수 변환방법을 코드로 표현해보기, 2로 나눈 나머지를 거꾸로 순서대로 나열한다.

 

 

public class Main {
    public static void main(String[] args) {
        int n = 29;
        int[] digits = new int[20];
        int cnt = 0;

        while (true) {
            if(n < 2) {
                digits[cnt++] = n;
                break;
            }
        
            digits[cnt++] = n % 2;
            n /= 2;
        }
        
        // print binary number : 거꾸로 출력
        for(int i = cnt - 1; i >= 0; i--)
            System.out.print(digits[i]);
    }
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

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

        ArrayList<Integer> arr = new ArrayList<>();
        
        while(true){
            if(n<2){
                arr.add(n);
                break;
            }
            arr.add(n % 2); 
            n /= 2;
        }

        Collections.reverse(arr);
        for(int i=0; i<arr.size(); i++) System.out.print(arr.get(i));
    }
}

 

10진수로 변환하기

: 일반적인 2진수->10진수 변환방법을 코드로 표현해보기

0부터 시작하여 binary[i]의 가중치를 더하여 2배해주는 작업을 n번 반복한다( = 2의 n승 + binary[i] )

num = num * 2 + binary[i] 로 반복갱신하기

 

public class Main {
    public static void main(String[] args) {
        int[] binary = new int[]{1, 1, 1, 0, 1};
        int num = 0;

        for(int i = 0; i < 5; i++)
            num = num * 2 + binary[i];
        
        System.out.print(num);
    }
}

import java.util.Scanner;

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

        // 변수 선언 및 입력
        String binary = sc.next();

        // 십진수로 변환합니다.
        int num = 0;
        for(int i = 0; i < binary.length(); i++)
            num = num * 2 + (binary.charAt(i) - '0');
        
        // 출력
        System.out.print(num);
    }
}

 

 

N진수로 변환하기

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

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

        int num = sc.nextInt(); //변환대상숫자
        int n = sc.nextInt();   //n진수로 변환

        ArrayList<Integer> arr = new ArrayList<>();
        while(true){
            if(num<n) {
                arr.add(num);
                break;
            }
            arr.add(num%n);
            num /= n;
        }
        Collections.reverse(arr);
        
        for(int i=0; i<arr.size(); i++) System.out.print(arr.get(i));
    }
}

 

 

[ 개념문제 ]

정수 a와 b가 주어지고, a진수로 표현된 어떤 수 n이 주어지면, n을 b진수로 변환하여 출력하는 프로그램을 작성해보세요.

 

a진수 -> 10진수 -> b진수

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt(); //주어지는 진수
        int b = sc.nextInt(); //변환하는 진수
        String n = sc.next();
		
        // a진수 -> 10진수 변환
        int num = 0;
        for(int i=0; i<n.length(); i++){
            num = a*num + ( n.charAt(i) - '0' );
        }
        
        // 10진수 -> b진수 변환
        ArrayList<Integer> arr = new ArrayList<>();
        while(true){
            if(num<b){
                arr.add(num);
                break;
            }

            arr.add(num%b);
            num /= b;
        }
        Collections.reverse(arr);

        for(int i=0; i<arr.size(); i++) System.out.print(arr.get(i));
    }
}

 

 

 3. 구간 칠하기 

겹치는 지점 : 위치를 숫자배열로 만들어서 숫자값으로 식별한다.

 

 

 

겹치는 구간 : 각 구간의 시작 지점을 배열로 만들어서 숫자값으로 식별한다.

 

 

이때 음수값이 주어진다면? 자바의 배열에서는 음수값을 표현할 수 없으므로 특정 OFFSET을 더해 모든 좌표를 양수로 만들어 진행한다.

ex)  문제에서 주어지는 좌표의 범위가 -100에서 100 사이라면, OFFSET을 최소 +100으로 잡아 진행한다.

 

 

[ 어려웠던 문제 ]

위치 0에서 시작하여 n번의 명령에 걸쳐 움직인 뒤, 2번 이상 지나간 영역의 크기를 출력하는 프로그램을 작성해보세요. 단 명령은 “x L“, “x R” 형태로만 주어집니다. "x L" 의 경우 왼쪽으로 x만큼 이동해야 함을, "x R"의 경우 오른쪽으로 x만큼 이동해야 함을 뜻합니다. ( 1 ≤ n ≤ 100, 1 ≤ x ≤ 10 )

 

좌표의 범위는 -10n ~ 10n 이므로 0 ~ 20n으로 양수화시키고 시작지점을 0이 아닌 10n으로 둔다.

구간의 시작지점에만 숫자를 올려줘야하므로 L로 이동시에는 인덱스(start)를 감소시킨뒤에 숫자를 올려준다.

import java.util.Scanner;

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

        int[] arr = new int[20*n];
        for(int i=0; i<arr.length; i++) arr[i] = 0;

        int[] size = new int[n];
        char[] dir = new char[n];
        for(int i=0; i<n; i++){
            size[i] = sc.nextInt();
            dir[i] = sc.next().charAt(0);
        }
        
		// 시작지점
        int start = 10*n;
        for(int i=0; i<n; i++){
            if(dir[i]=='R'){
                for(int j=0; j<size[i]; j++){
                    arr[start]++;
                    start++;
                }
            } else {
                for(int j=0; j<size[i]; j++){
                    start--;
                    arr[start]++;
                }
            }
        }

        int cnt = 0;
        for(int i=0; i<arr.length; i++){
            if(arr[i]>=2) cnt++;
        }

        System.out.println(cnt);
    }
}

 

 

[ 어려웠던 문제 ]

일직선으로 무한히 나열된 타일이 있습니다. 아무 타일에서 시작하여 n번의 명령에 걸쳐 움직입니다. 명령은 "x L", "x R" 형태로만 주어지며, "x L"의 경우 왼쪽으로 이동하면서 현재 위치 타일포함 총 x칸의 타일을 흰색으로 연속하게 칠하고, "x R"의 경우 오른쪽으로 이동하면서 현재 위치 타일포함 총 x칸의 타일을 검은색으로 연속하게 칠함을 뜻합니다. 각 명령 이후에는 마지막으로 칠한 타일 위치에 서있는다고 가정합니다. 타일의 색은 덧칠해지면 마지막으로 칠해진 색으로 바뀌는데, 만약 타일 하나가 순서 상관없이 흰색과 검은색으로 각각 두 번 이상 칠해지면 회색으로 바뀌고 더 이상 바뀌지 않습니다. 모든 명령을 실행한 뒤의 흰색, 검은색, 회색의 타일 수를 각각 출력하는 프로그램을 작성해보세요.
1 ≤ n ≤ 1000 , 1 ≤ x ≤ 100

 

 

 

좌표의 범위는 -100n ~ 100n 이므로 0 ~ 200n으로 양수화시키고 시작지점을 0이 아닌 100n으로 둔다.

 

구간이 검정색으로 칠해진 횟수를 나타내는 int배열 black, 구간이 흰색으로 칠해진 횟수를 나타내는 int배열 white, 최종적으로 구간의 색을 저장하는 char배열 color(b,w,g의 값중 하나)를 선언했다.

명령의 크기를 나타내는 int배열 size, 명령의 방향을 나타내는 char배열 dir(L, R 값 중 하나)을 선언했다.

 

동작방식은 현재영역(index)에 명령의 크기만큼, 명령의 색으로 칠하는 것이다. 명령의 방향으로 움직이기 위해 R은 인덱스를 증가시키고 L은 인덱스를 감소시키는 방향으로 진행한다. 동작시마다 해당구간의 color값을 변경하고 black, white횟수값을 증가시킨다. black, white의 횟수값이 순서관계없이 각각 2이상으로 증가한다면 gray의 색으로 변경하고 더이상 이 구간에서는 명령이 동작하지 않도록 제어한다.( 동작처리가 끝난후 인덱스 조정이 일어나기 전에 그 상태를 체크한다 )

 

import java.util.Scanner;

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

        int n = sc.nextInt();
        int[] black = new int[200*n];
        int[] white = new int[200*n];
        char[] color = new char[200*n];

        //명령
        int[] size = new int[n];
        char[] dir = new char[n];
        for(int i=0; i<n; i++){
            size[i] = sc.nextInt();
            dir[i] = sc.next().charAt(0);
        }

        int index = 100*n;
        for(int i=0; i<n; i++){
            if(dir[i]=='R'){
                for(int j=0; j<size[i]; j++){
                    if(color[index] !='g') {
                        color[index] = 'b';
                        black[index]++;
                    }
                    if(black[index]>=2 && white[index]>=2) color[index]='g';
                    index++; //인덱스 조정
                }
                index--; //마지막 위치조정
            } else {
                for(int j=0; j<size[i]; j++){
                    if(color[index]!='g'){
                        color[index] = 'w';
                        white[index]++;
                    }
                    if(black[index]>=2 && white[index]>=2) color[index]='g';
                    index--;
                }
                index++;
            }
            
        }

        int whiteCnt = 0;
        int blackCnt = 0;
        int grayCnt = 0;
        for(int i=0; i<color.length; i++){
            if(color[i]=='w'){
                whiteCnt++;
            } else if(color[i]=='b'){
                blackCnt++;
            } else if(color[i]=='g'){
                grayCnt++;
            }
        }

        System.out.println(whiteCnt+" "+blackCnt+" "+grayCnt);

        
    }
}

 

어려웠던 점1 - 마지막 인덱스 조정

: 반복동작은 현재 위치(index)에서부터 적용되고 마친뒤에 위치를 이동시킨다. (증가 혹은 감소)

이전반복동작이 적용된 마지막 위치에서 다음반복동작이 시작되어야한다. 마지막 반복이후에 인덱스가 하나더 증가되거나 감소되는 것을 보정해줄 필요가 있다. for문동작이 종료된 후에 마지막 위치를 조정해주어야했다.

 

실제로 조정하지 않고 출력해보았을때 각 배열은 다음과 같이 위치가 어긋나서 오답이 발생하였다.

System.out.print(black[i]); //12222110 <-> 정답 : 1222211
System.out.print(white[i]); //01112211 <-> 정답 : 1112211
System.out.print(color[i]); //bbbbgwww <-> 정답 : bbbggww

 

어려웠던 점2 - gray색상변경조건

단순 예제만보고 gray색상 변경조건을 index위치의 black값이 2와 일치하면서 index위치의 white값이 2와 일치하는 경우로 생각하였다. 그러나 큰 이동이 발생하는 테스트케이스( 855, 80 R, 73 R, 65 L, 31 R, ... ) 오류를 통해 변경조건이 일치조건()이 아닌 이상조건(>=)으로 변경되어야함을 알게 되었다.

 

 

 4. 사각형 칠하기 

양쪽 모서리 좌표를 통한 직사각형 넓이 구하기

: 좌표를 2차원배열로 표현하여 직사각형이 존재하는 위치만큼 1로 값을 넣어 모두 합해준다.

 

 

(x, y) 위치를 2차원 배열에서의 (x 행, y 열)로 옮기게 되면 시계방향으로 90' 회전이 일어난다.

기존 좌표계에서 (x1, y1), (x2, y2)로 이루어진 직사각형은 2차원 격자 상에서는 (x1 행, y1 열) 부터 (x2 - 1 행, y2 - 1 열) 까지로 이루어지게 된다.

좌표상에서는 음수의 표현이 일어날 수 있기에 이때에도 적절한 OFFSET을 모두 더해주어 해결한다.

 

2차원 배열 : 각 행(1차원 배열)을 원소로가지는 배열

선언 : int[행 크기][열 크기]
이용 : arr2d[i][j] =  i+1행, j+1열

1 2 3 4
7 8 9 10
11 12 13 14
15 16 17 18

{{1, 2, 3, 4}, {7, 8, 9, 10}, {11, 12, 13, 14}, {15, 16, 17, 18}}

 

 

[ 개념문제 ]

2차 평면 위에 N개의 직사각형이 주어집니다. 이 직사각형들이 만들어내는 총 넓이를 구하는 프로그램을 작성해보세요.
첫 번째 줄에 N이 주어집니다.
두 번째 줄부터는 N개의 줄에 걸쳐 각 줄마다 x1, y1, x2, y2 값이 공백을 사이에 두고 주어집니다. 이는 (x1, y1), (x2, y2)를 양 끝으로 직사각형임을 의미합니다.
1 ≤ N ≤ 10, -100 ≤ x1 < x2 ≤ 100, -100 ≤ y1 < y2 ≤ 100

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[][] cord = new int[200][200];

        for(int i=0; i<n; i++){
            int x1 = sc.nextInt() + 100;
            int y1 = sc.nextInt() + 100;
            int x2 = sc.nextInt() + 100;
            int y2 = sc.nextInt() + 100;
            for(int k=x1; k<x2; k++){
                for(int j=y1; j<y2; j++){
                    cord[k][j] = 1;
                }
            }
        }

        int sum = 0;
        for(int i=0; i<200; i++){
            for(int j=0; j<200; j++){
                if( cord[i][j]==1) sum++;  
            }
        }
        System.out.println(sum);
    }
}

 

좌표를 2차원배열로 작성하여 영역이 있는 공간에 표기하는 것으로 이러한 방법을 통해서 겹치는 부분없이 총 넓이를 구할 수 있다.

 

+) 잔해물을 덮기위한 최소 사각형 넓