https://school.programmers.co.kr/learn/courses/30/lessons/120876
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> lines) {
int answer = 0;
int a[210]={};
for(auto t:lines){
int st=t[0];
int en=t[1]; // st<en 이 보장됨.
for(int i=st; i<=en;i++){
a[i+100]++;
}
}
int tmp=-1;
for(int j=0; j<210; j++){
if(a[j]>=2) tmp++;
else {
if(tmp>=0) answer+=tmp;
tmp=-1;
}
}
sort(lines.begin(),lines.end());
//아래의 경우가 가운데 있는 선분이 길이가 1이고, 그때에 양 끝에서 다른 선분의 양 끝에 겹쳐지는 경우가 예외처리를 해주어야 하는 부분
if((lines[1][1]-lines[1][0]==1)&& (lines[0][1]==lines[1][0]&&lines[1][1]==lines[2][0])) answer--;
return answer;
}
위와 같은 코드를 작성해서 통과하였는데, 스스로 생각하기에 그렇게 만족스럽지 않은 풀이이다. 아무래도 저 예제처리 해주어야 하는 부분에 대해서 제대로 생각하지 못했기 때문에, 처음에 작성한 코드의 경우는 아래에 첨부한 것처럼 그런 예외처리 부분이 없는 형태의 프로그램을 작성하였고, 그랬기 때문에 예를들어, [[1,2],[2,3],[3,4]] 형태처럼 가운데에 있는 선분이 길이가 1이 되는 경우이면서 양 끝에 있는 선분과 딱 끝 점만 연결지어지면, 내가 만든 형태의 프로그램의 경우는 수들이 0 0 0 1 2 2 1 0 0 형태처럼 나와버려서, 이 경우 answer의 값이 +1 을 해버리게 되서 결과가 잘못되기 때문에 해당 경우 같은 케이스가 되면 그 예외를 제거해주기 위해서 저렇게 예외처리 형태를 넣게 되었다.
이런 특별한 예외에 대해서 제대로 고려하지 않고 위와 같은 판별 프로그램을 작성했는데 애초부터 예외가 이렇게 나올 수 있으니 주의하면서 위와 같은 로직으로 작성하자, 라고 생각했다면 오히려 괜찮았겠지만 그게 아니라 아쉬움이 남는다.
/* 한참 잘못된 부분을 찾지 못한 코드 */
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> lines) {
int answer = 0;
int a[210]={0};
// sort(lines.begin(),lines.end());
for(auto t:lines){
int st=t[0];
int en=t[1]; // st<en 이 보장됨.
for(int i=st; i<=en;i++){
a[i+100]++;
}
}
for(int i=0; i<210; i++){
cout<<a[i]<<' ';
}
int tmp=-1;
for(int i=0; i<=210; i++){ //맨 마지막께 체크가 안되나? 혹은 불필요한 마지막이 체크가 되나?
if(a[i]>=2) tmp++;
else {
if(tmp>0) answer+=tmp;
tmp=-1;
}
}
return answer;
}
다른 사람의 풀이를 보니까, 나와 비슷한 방식으로 해결한 사람들의 풀이도 있는데, 이때에 이러한 예제를 발생시키지 않게 하는 형태로 코드를 작성한 것들이 있어서 첨부해보도록 하겠다.
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> lines) {
const int BIAS = 100;
vector<int> arr(BIAS*2 + 1,0);
int answer = 0;
for(auto& v : lines)
{
if(v[0] > v[1])
{
swap(v[0],v[1]);
}
for(int i = v[0]; i < v[1]; ++i)
{
arr[BIAS + i]++;
}
}
for(const auto v : arr)
{
answer += v > 1;
}
return answer;
}
내 코드의 경우는, 시작점과 끝점까지 모두 arr[i+100]++ 형태로 작성해서 양족 끝이 모두 숫자가 증가하는데, 위의 코드의 경우는 시작점만 포함, 끝점은 제외하였기 때문에 배열을 돌면서 answer에 arr[i]>1; 인 경우에 해당하는 경우만 참 거짓 형태로 거짓이면 0, 참이면 1을 더해주는 형태로 작성했는데, 이 경우 내가 작성한 코드같은 경우 걸러내지 못하는 부분에 문제가 발생하지 않는 형태이다.
위와 같은 코드를, 내게 익숙한 형태로 다시 작성해서 첨부해보자면,
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> lines) {
vector<int> arr(201,0);
int answer = 0;
for(auto& v : lines){
for(int i = v[0]; i < v[1]; ++i){
arr[i+100]++;
}
}
for(const auto v : arr){
answer += v > 1;
}
return answer;
}
위와 같은 형태이다. 이게 내가 작성한 코드보다 훨씬 간결하고 이해하기 쉽고, 직관적으로 이해가 되는것 같다. 처음에 생각한데로 선분을 배열에 +1 형태로 작성하는 방법을 떠올렸을때, 맨 끝단의 경우 어떤식으로 처리할지에 대해서 한번 더 고려해서 생각해보았다면 좋았을것같다. 다음에는 한번 더 고려해서 과연 꼭 실제처럼 맨 끝단까지 +1 처리로 표시해야 하는지에 대해서 생각해보도록 하자.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
Lv 0. 특이한 정렬. pair에 대한 first와 second 원소에 대한 개별 sort 적용시키기 위한 커스텀 comp 함수를 이용한 sort. *다시 풀어보기* (0) | 2023.10.10 |
---|---|
Lv 0. 유한소수 판별하기. *다시 풀어보기* (0) | 2023.10.08 |
Lv 0. 평행 (0) | 2023.10.08 |
Lv 0. 저주의 숫자 3 (0) | 2023.10.07 |
Lv 0. 외계어 사전 - string 속에서 string을 찾으려면 find() 함수를, 못찾으면 string::npos를 떠올리자. *다시 풀어보기* (0) | 2023.10.06 |