#16 2021 / 02 / 27 - 2020 인하대학교 프로그래밍 경진대회(IUPC)

www.acmicpc.net/contest/view/579

2020 인하대학교 프로그래밍 경진대회(IUPC)

A. 연길이의 이상형 - Bronze III

계획

첫 번재 문제다. 문제는 간단하다. 연길이와 정 반대인 MBTI 유형인 사람을 찾아주면 된다. 정답률 76.797%의 문제이기에 바로 코딩으로 들어간다.

코딩

#include<iostream>
#include<string>
int main() {
	std::string type[2] = {"ESTJ", "INFP"};
	std::string input;
	std::cin >> input;
	for (int i = 0; i < input.size(); i++) {
		if (type[0][i] != input[i]) {
			std::cout << type[0][i];
		}
		else {
			std::cout << type[1][i];
		}
	}
}

풀이는 간단하다. 우선 각 MBTI 유형을 차례로 저장해둔다. 그리고 입력을 받아 각 자리와 일치하지 않는 MBTI 유형을 하나씩 출력한다. MBTI 유형에서 각 자리가 두 가지로 정해져있기 때문에 가능한 풀이다.

정답

B. Sort 마스터 배지훈의 후계자 - Silver IV

계획

단순한 정렬 후, 해당 인덱스가 위치하는 자리를 찾는 문제다. stl에 있는 sort 함수를 사용해 풀면 될 듯 하다.

수정

시간초과가 나왔다. cin과 cout의 연산 속도를 가속시켜야겠다.

수정 2

다시 시간초과가 나왔다. 그냥 알고리즘의 구조를 바꿔야 될 듯 하다. 각 자리를 찾는 문제이니 이분탐색을 이용해 원하는 인덱스의 위치를 반환하게 만들어야겠다. 그리고 중복되는 숫자가 들어가는 것이 가능하기 때문에, 각 숫자는 vector에 한 번씩만 넣어준다. 이때 vector는 pair로 만들어서 pair의 second 값에 이전까지의 길이를 저장해둘 것이다. 

수정 3

조졌다. 또 시간초과다. 이분탐색을 통해 검색 O(log n)으로 줄였고, 정렬 후 n 번의 검색을 통해 중복되는 숫자들도 없엤다. 그런데 왜 시간초과가 나는지 도저히 모르겠다. 

찾았다. 이분 탐색을 설계할 때, 실수를 했다. 다음 이분 탐색을 실행 할 때, left와 right의 설정값을 잘못줬던 것이다. 그런데 말이다. 이번엔 메모리 초과가 나타났다;;;

수정 4

메모리 초과는 해결했다. 원인은 이분탐색의 매게변수로 vector를 받아서 그런 듯 하다. 그래서 vector를 전역 변수로 바꿔줬다. 그런데 시간초과가 또 나왔다. 쉽게 본 문제였는데....그게 아닌 모양이다. 이게 왜 이러지... cin을 scanf로 cout을 printf로 바꿔도 3%까지 밖에 가지를 못 한다. 이거 분명 다 풀고나면 성취감보다 빡침이 더 클 거 같다.

수정 5

30%까지 올라가길래 희망찬 소리를 질렀는데, 갑자기 시간초과가 나타났다. 도저히 모르겠다. 이분탐색을 새로 짜서 나온 결과이긴 한디...여기서 뭘 더 해야 될까.

결국 stl에 있는 이분탐색 함수를 사용했다. 그랬더니 바로 맞았다. 직접 구현해서 푸려는 고집 꺾고 그냥 풀어버릴 걸. ㅋㅋ 웃음 밖에 안 나온다.

코딩

#include<iostream>
#include<algorithm>
#include<vector>
int main() {
    std::ios::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);
    
    int n, m;
    std::cin >> n >> m;
    std::vector<int> v;

    while (n--) {
        int a;
        std::cin >> a;
        v.push_back(a);
    }

    std::sort(v.begin(), v.end());

    while (m--) {
        int index;
        std::cin >> index;
        if (std::binary_search(v.begin(), v.end(), index)) {
            std::cout << std::lower_bound(v.begin(), v.end(), index) - v.begin() << '\n';
        }
        else {
            std::cout << -1 << '\n';
        }
    }
}

정답

빡종

B번에서 너무 지친 나머지, 그만 풀기로 결심했다. 이제 밀린 집안일 하러 가야겠다. 인하대랑은 작별이다. 빠이.