문제:
시도 횟수: 1번
처음 생각한 방법: 오름차순 벡터, 내림차순 벡터 정렬해서 만들어두고 원본 벡터와 비교해서 출력
그런데 처음에는
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a;
vector<int> vec;
for(int i = 0; i < 8; i++) {
cin >> a;
vec.push_back(a);
}
if(vec == sort(vec.begin(), vec.end()))
cout << "ascending";
else if(vec == sort(vec.begin(), vec.end(), greater<int>()))
cout << "descending";
else
cout << "mixed";
return 0;
}
이런 식으로 접근했었다. sort와 vec를 바로 비교했다가 오류가 났었는데, sort는 리턴값이 없는 void를 반환하는 함수라고 한다.
그래서 직접적인 비교가 불가능해서 벡터 변수를 두개 더 만들어서 해결했다.
내 코드:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a;
vector<int> vec;
for(int i = 0; i < 8; i++) {
cin >> a;
vec.push_back(a);
}
vector<int> ascending = vec;
vector<int> descending = vec;
sort(ascending.begin(), ascending.end());
sort(descending.begin(), descending.end(), greater<int>());
if(vec == ascending)
cout << "ascending";
else if(vec == descending)
cout << "descending";
else
cout << "mixed";
return 0;
}
모범답안:
#include <iostream>
using namespace std;
int main(){
int num;
int asc = 0;
int desc = 0;
for(int i=0; i<8; i++){
cin >> num;
if(num == i+1) asc++;
else if(num == 8-i) desc++;
}
if(asc == 8) cout << "ascending";
else if(desc == 8) cout << "descending";
else cout << "mixed";
return 0;
}
대부분 이 방식으로 풀었다.
내 코드의 개선할 점: sort 함수를 사용하는 게 연산 코스트가 얼마나 높은지는 모르겠지만 남용하면 안될 것 같은 느낌이 든다.
모범답안은 시간복잡도가 O(1)이고, 내 코드는 시간복잡도가 O(n log n)이다. 시간복잡도를 낮추기 위해서 구현방식을 바꿔야겠다.
알고리즘 분류: 구현
난이도: 브론즈 II
복습하면서 참고해본 블로그 목록:
https://carrot-farmer.tistory.com/59
[백준] 2920번: 음계 | C++ 풀이
# 문제 연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오. # 풀이1 코드가 간단한 문제에 비해 길고 복잡한 것 같다. 아이디어가 떠
carrot-farmer.tistory.com
'백준' 카테고리의 다른 글
[백준] 1157번 - 단어 공부 (1) | 2024.03.26 |
---|---|
[백준] 10250번 - ACM 호텔 (0) | 2024.03.22 |
[백준] 2522번 - 별 찍기 - 12 (0) | 2024.03.22 |
[백준] 2445번 - 별 찍기 - 8 (0) | 2024.03.22 |
[백준] 2442번 - 별 찍기 - 5 (0) | 2024.03.22 |