04 1회차 모의 코딩테스트 해설
2번 문제 해설과 답안
* 이 문제의 해설을 보기 전에 색종이 문제를 먼저 공부하고 오시면 좋습니다! 비슷하지만 서로 풀이가 다를 수 밖에 없는 두 문제의 차이에 초점을 맞추고 공부하면 좋습니다.
중요 포인트
문제를 읽고 솔루션을 설계하기 전에는 아래의 두 가지를 꼭 점검해야 합니다.
- 문제에서 직/간접적으로 주어진 모든 정보를 정확히 이해하고 받아들였는지 확인했는가?
- 나 스스로 문제에서 언급되지 않은 내용을 마음대로 추측/가정하고 있지는 않은지 확인했는가?
그리고 솔루션을 실제로 구현하고 적용하기 전에 아래의 세 가지를 고려해야 합니다.
- 내가 설계한 솔루션이 예제 데이터뿐만 아니라 항상 정답을 구해낼 수 있는 일반적인 방법인가?
- 내가 설계한 알고리즘이 요구하는 시간 복잡도와 공간 복잡도가 문제의 시간/메모리 제한을 지킬 수 있는가?
- 문제에서 주어진 제한 사항을 활용하고 불필요한 정보 획득을 버려가며 조금 더 경량화된 알고리즘을 설계할 수 있는가?
물론 이런 과정은 이렇게 말로 설명한다고해서 바로 실전에 적용할 수 있는 것은 아닙니다. 수 많은 문제들을 풀어보며 쌓인 경험을 바탕으로 감각적으로 하게 되는 경우가 많습니다. 하지만 문제의 풀이를 고민하고 다른 사람의 해설을 볼 때에 위의 내용들에 초점을 맞추고 공부해보세요.
더 공부할 things
이 문제처럼 계산 과정에서 제곱이나 곱하기가 들어가는 경우 항상 데이터의 범위를 확인합니다. 계산 과정에서 범위 초과가 날 수 있기 때문입니다. 각 변수들의 표현 범위를 대략적으로라도 알고 있는 것이 좋습니다.
답안 코드
아래에 세 언어로 각기 다른 방법을 이용해 작성한 코드를 첨부합니다. 세 가지 언어와 방법을 보고 공부해보세요.
C++ 답안 코드
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <algorithm>
using namespace std;
/**
@description
하나의 점(좌표)를 나타내는 구조체
**/
struct point_t{
int x;
int y;
point_t(int x = 0, int y = 0)
:x(x), y(y){}
};
struct rect_t{
int top;
int bot;
int left;
int right;
rect_t(point_t a, point_t b)
{
top = max(a.y, b.y);
bot = min(a.y, b.y);
left = min(a.x, b.x);
right = max(a.x, b.x);
}
};
/**
@description
두 사각형을 이루는 네 점을 파라미터로 받아 교차하는 영역의 넓이를 반환하는 함수
@param p 첫 번째 사각형의 한 점, q와 대각선상에 존재한다.
@param q 첫 번째 사각형의 한 점, p와 대각선상에 존재한다.
@param r 두 번째 사각형의 한 점, s와 대각선상에 존재한다.
@param s 두 번째 사각형의 한 점, r과 대각선상에 존재한다.
@return 두 직사각형이 교차하는 영역의 넓이
**/
int get_duplicated_area(point_t p, point_t q, point_t r, point_t s)
{
int area = 0; //두 사각형이 교차하는 영역의 넓이
rect_t ra(p, q);
rect_t rb(r, s);
int c_left = max(ra.left, rb.left);
int c_right = min(ra.right, rb.right);
int c_top = min(ra.top, rb.top);
int c_bot = max(ra.bot, rb.bot);
int width = c_right - c_left;
int height= c_top - c_bot;
if(width >= 0 && height >= 0)
{ //겹치는 영역이 x축과 y축 모두에 존재한다면 넓이를 계산
area = width * height;
}
return area;
}
/*
** 메인 함수에는 테스트케이스와 입출력에 대한 기본적인 뼈대 코드가 작성되어 있습니다.
** 상단의 함수만 완성하여도 문제를 해결할 수 있으며,
** 메인 함수를 제거한 후 스스로 코드를 모두 작성하여도 무방합니다.
** 단, 스스로 작성한 코드로 인해 발생한 에러 등은 모두 참가자에게 책임이 있습니다.
*/
int main() {
//네 점을 저장할 구조체 변수를 선언한다
point_t p, q, r, s;
//네 점의 좌표를 형식에 맞게 입력받는다
cin >> p.x >> p.y;
cin >> q.x >> q.y;
cin >> r.x >> r.y;
cin >> s.x >> s.y;
//주어진 함수를 통해 교차하는 영역의 넓이를 계산한다
int answer= get_duplicated_area(p, q, r, s);
//정답을 형식에 맞게 출력한다.
cout << answer << "\n";
return 0;
}
실행하여 결과를 확인하세요!
Java 답안 코드
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.io.*;
import java.util.*;
public class Main {
public static final Scanner scanner = new Scanner(System.in);
/**
* @description 두 사각형을 이루는 네 점을 파라미터로 받아 교차하는 영역의 넓이를 반환하는 함수
*
* @param p
* 첫 번째 사각형의 한 점, q와 대각선상에 존재한다.
* @param q
* 첫 번째 사각형의 한 점, p와 대각선상에 존재한다.
* @param r
* 두 번째 사각형의 한 점, s와 대각선상에 존재한다.
* @param s
* 두 번째 사각형의 한 점, r과 대각선상에 존재한다.
* @return 두 직사각형이 교차하는 영역의 넓이
**/
public static int getDuplicatedArea(Point p, Point q, Point r, Point s) {
int area = 0; // 두 사각형이 교차하는 영역의 넓이
Rect ra = new Rect(p, q);
Rect rb = new Rect(r, s);
int c_left = Math.max(ra.left, rb.left);
int c_right = Math.min(ra.right, rb.right);
int c_top = Math.min(ra.top, rb.top);
int c_bot = Math.max(ra.bot, rb.bot);
int width = c_right - c_left;
int height = c_top - c_bot;
if (width >= 0 && height >= 0) { // 겹치는 영역이 x축과 y축 모두에 존재한다면 넓이를 계산
area = width * height;
}
return area;
}
/*
** 메인 함수에는 테스트케이스와 입출력에 대한 기본적인 뼈대 코드가 작성되어 있습니다. 상단의 함수만 완성하여도 문제를 해결할 수
* 있으며, 메인 함수를 제거한 후 스스로 코드를 모두 작성하여도 무방합니다. 단, 스스로 작성한 코드로 인해 발생한 에러 등은 모두
* 참가자에게 책임이 있습니다.
*/
public static void main(String[] args) {
// 네 점 p, q, r, s를 차례로 입력받는다.
Point p = new Point(scanner.nextInt(), scanner.nextInt());
Point q = new Point(scanner.nextInt(), scanner.nextInt());
Point r = new Point(scanner.nextInt(), scanner.nextInt());
Point s = new Point(scanner.nextInt(), scanner.nextInt());
// 주어진 함수를 통해 교차하는 영역의 넓이를 계산한다
int answer = getDuplicatedArea(p, q, r, s);
// 정답을 형식에 맞게 출력한다
System.out.println(answer);
}
}
/**
* @description 하나의 점(좌표)를 나타내는 클래스
**/
class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
public void setX(int x) {
this.x = x;
}
public void setY(int y) {
this.y = y;
}
}
class Rect{
int top;
int bot;
int left;
int right;
Rect(Point a, Point b)
{
top = Math.max(a.y, b.y);
bot = Math.min(a.y, b.y);
left = Math.min(a.x, b.x);
right = Math.max(a.x, b.x);
}
}실행하여 결과를 확인하세요!
Python3 답안 코드
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
"""
@description
하나의 점(좌표)를 나타내는 클래스
"""
class point:
def __init__(self, x, y):
self.x = x
self.y = y
class rect_t:
def __init__(self, p1, p2):
self.top = max(p1.y, p2.y)
self.bot = min(p1.y, p2.y)
self.left = min(p1.x, p2.x)
self.right = max(p1.x, p2.x)
"""
@description
두 사각형을 이루는 네 점을 파라미터로 받아 교차하는 영역의 넓이를 반환하는 함수
각 점은 point class의 객체로 주어진다
@param p 첫 번째 사각형의 한 점, q와 대각선상에 존재한다.
@param q 첫 번째 사각형의 한 점, p와 대각선상에 존재한다.
@param r 두 번째 사각형의 한 점, s와 대각선상에 존재한다.
@param s 두 번째 사각형의 한 점, r과 대각선상에 존재한다.
@return 두 직사각형이 교차하는 영역의 넓이
"""
def get_duplicated_area(p, q, r, s):
area = 0
ra = rect_t(p, q);
rb = rect_t(r, s);
c_left = max(ra.left, rb.left);
c_right = min(ra.right, rb.right);
c_top = min(ra.top, rb.top);
c_bot = max(ra.bot, rb.bot);
width = c_right - c_left;
height= c_top - c_bot;
if width >= 0 and height >= 0:
#겹치는 영역이 x축과 y축 모두에 존재한다면 넓이를 계산
area = width * height;
return area
"""
메인 함수에는 테스트케이스와 입출력에 대한 기본적인 뼈대 코드가 작성되어 있습니다.
상단의 함수만 완성하여도 문제를 해결할 수 있으며,
메인 함수를 제거한 후 스스로 코드를 모두 작성하여도 무방합니다.
단, 스스로 작성한 코드로 인해 발생한 에러 등은 모두 참가자에게 책임이 있습니다.
"""
if __name__ == "__main__":
#네 점의 좌표를 입력받는다
px, py =[ int(word) for word in input().split() ]
qx, qy =[ int(word) for word in input().split() ]
rx, ry =[ int(word) for word in input().split() ]
sx, sy =[ int(word) for word in input().split() ]
#각 점의 정보를 객체화한다
p = point(px, py)
q = point(qx, qy)
r = point(rx, ry)
s = point(sx, sy)
#주어진 함수를 통해 교차하는 영역의 넓이를 계산한다
answer = get_duplicated_area(p, q, r, s)
#정답을 형식에 맞게 출력한다
print(answer)실행하여 결과를 확인하세요!
