[백준(Baekjoon)] 2246 콘도 선정

문제

콘도를 선정할 때에는 가급적이면 싸고 바닷가에 가까운 곳으로 하려 한다. 이를 위해 우선 적당한 콘도 몇 곳을 후보로 선정하려 하는데, 다음 두 조건을 만족하는 콘도 X가 후보가 된다.

1. X보다 바닷가에 더 가까운 콘도들은 모두 X보다 숙박비가 더 비싸다.
2. X보다 숙박비가 더 싼 콘도들은 모두 X보다 바닷가에서 더 멀다.

각 콘도의 바닷가에서의 거리와 숙박비에 대한 정보가 주어졌을 때, 후보 콘도의 개수를 구해내는 프로그램을 작성하시오.

 

입력

첫째 줄에 콘도의 개수를 나타내는 자연수 N(1≤N≤10,000)이 주어진다. 다음 N개의 줄에는 각 콘도에 대한 정보를 나타내는 두 정수 D(1≤D≤10,000), C(1≤C≤10,000)가 주어진다. D는 그 콘도의 바닷가로부터의 거리를 나타내고, C는 그 콘도의 숙박비를 나타낸다. D와 C값이 서로 같은 콘도가 주어지지는 않는다.

 

출력

첫째 줄에 후보가 될 수 있는 콘도의 수를 출력한다.

 

예제 입력 1

5

300 100

100 300

400 200

200 400

100 500

 

예제 출력 1

2

 

---

나의 풀이

[Python(파이썬)]

 

풀이1 

from sys import stdin
num = int(stdin.readline())
conlist = [[0] for _ in range(num)]
answer = 0

for i in range(num):
    conlist[i] = list(map(int, stdin.readline().split()))

conlist.sort()
for x in range(num):
    answer += 1
    for check in range(x):
        if conlist[x][1] >= conlist[check][1]:
            answer -= 1
            break
print(answer)

 

풀이2 - 시간을 더 단축시킨 코드

from sys import stdin
num = int(stdin.readline())
conlist, answer = [[0] for _ in range(num)], 1

for i in range(num):
    conlist[i] = list(map(int, stdin.readline().split()))
conlist.sort()
price = conlist[0][1]

for j in range(1, num):
    if conlist[j][1] < price:
        answer += 1
        price = conlist[j][1]
print(answer)

 

[C언어]

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int main() {
    int n;
    int input[10000][2];
    int count = 0;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &input[i][0]);
        scanf("%d", &input[i][1]);
    }

    for (int i = 0; i < n; i++) {
        count += 1;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                if (input[i][0] >= input[j][0] && input[i][1] >= input[j][1]) {
                    count -= 0;
                    break;
                }
            }
        }
    }

    printf("%d", count);
    return 0;
}

---

풀이 과정

파이썬으로 하면 항상 간단하게 코딩할 수 있어서 너무 좋았는데 오늘은 화가 났다ㅠㅠ

C, C++에서는 시간 초과가 나오지 않는 코드가 파이썬에서는 시간초과가 계속 나오는 것이었다. 

 

지금부터 풀어나간 과정을 설명해보겠다. 

 

처음 문제를 풀 때 문제의 조건을 조금 바꿔서 풀었다. 

< 문제에서 주어진 조건 >
1. X보다 바닷가에 더 가까운 콘도들은 모두 X보다 숙박비가 더 비싸다.
2. X보다 숙박비가 더 싼 콘도들은 모두 X보다 바닷가에서 더 멀다.

X보다 바닷가에 더 가깝거나 같은 콘도 中 숙박비가 같거나 작은 콘도가 있으면 후보 X가 될 수 없다로 위의 두 개의 조건을 한 개의 조건으로 바꿔서 풀었다.

 

for x in range(num):
    tfcheck = True
    for check in range(num):
        if x != check:
            if conlist[x][0] >= conlist[check][0] and conlist[x][1] >= conlist[check][1]:
                tfcheck = False
                break
    if tfcheck:
        answer += 1

 

하지만 시간 초과가 나오는 것 그래서 혹시 조건대로 안 풀어서 그런가 해서 다시 조건처럼 풀어보았다. 

조건이 두 개가 있으면 더 시간이 많이 나올 것 같았지만 그래도 문제처럼 풀어보았다. 

 

for x in range(num):
    tfcheck = 0
    for check in range(num):
        if x != check:
            if conlist[x][0] > conlist[check][0] and conlist[x][1] >= conlist[check][1]:
                tfcheck += 1
                break
            if conlist[x][1] > conlist[check][1] and conlist[x][0] >= conlist[check][0]:
                tfcheck += 1
                break
    if tfcheck == 0:
        answer += 1

 

하지만 역시나 시간 초과ㅠㅠ

 

나의 풀이의 풀이 1번 설명

conlist.sort()
for x in range(num):
    answer += 1
    for check in range(x):
        if conlist[x][1] >= conlist[check][1]:
            answer -= 1
            break

 

더 시간을 줄이기 위해 sort(정렬)을 한 다음 0~X까지만 두 번째 for문을 돌리고 conlist[x][0] >= conlist[check][0] 조건은 어차피 sort 했기에 필요 없어서 conlist[x][1] >= conlist[check][1] 조건만 검사를 했다. 

 

그랬더니 드디어 통과!!!

 

 

그래도 시간이 위의 C 코드보다 훨씬 시간이 많이 나왔다ㅠㅠ 

 

그래서 더 시간을 줄이기 위해서 다시 구현했다.  -> 나의 풀이의 풀이 2번

 

conlist.sort()	# 거리를 기준으로 정렬
price = conlist[0][1]

for j in range(1, num):
    if conlist[j][1] < price:
        answer += 1
        price = conlist[j][1]
print(answer)

 

1. 거리를 기준으로 정렬

2. 거리를 기준으로 정렬하면 거리가 가장 짧으면서 가격이 가장 저렴한 콘도가 conlist[0]이 된다 => 첫번째 후보 콘도

3. conlist[0][1](첫번째 후보 콘도의 가격)을 price에 저장한다. 

4. for문을 이용해 인덱스 1~num까지 반복한다. 

5. conlist[j][1]가 price보다 작다면 후보 콘도가 된다. answer += 1

6. price에 conlist[j][1] 저장

7. 4-6 반복한다.  

 

위의 코드를 아래의 예를 들어 그림으로 그리면

 

<예제 1>

7
3 1
2 5
2 2
1 3
4 3
1 4
3 3

출력 = 3 (후보 콘도 3개)

 

 

<예제 2> => (예제 1과 다른 점 2,2가 2,1이 됨)

7
3 1
2 5
2 1
1 3
4 3
1 4
3 3

출력 : 2 (후보 콘도 2개)

 

 이중 for문을 사용하지 않으니까 시간이 확실히 줄었다. 

---

문제 출처

2246번: 콘도 선정