구현

프로그래머스 최댓값과 최솟값 문제 바로가기 python이라면 split을 이용해서 list을 만들고 max, min 함수를 이용해서 쉽게 구할 수 있을듯하다. C++도 vector에 저장해서 algorithm에서 max_element() min_element()으로 최대,최소값을 구할 수 있다. 하지만 vector을 저장하는 메모리가 사용되기 때문에 그보다 효율적인 비교하는 방식을 택했다. #include <string> #include <vector> #include <sstream> using namespace std; string solution(string s) { string answer = ""; int num, _max=-32768, _min=32767; stringstream stream; stream.str(s); while (stream >> num){ if (num > _max){ _max = num; } if (num < _min){ _min = num; } } answer = to_string(_min) + " " + to_string(_max); return answer; }

백준 5525번 문제 바로가기 서브테스크가 있는 String 탐색 문제. substr()을 이용한 해법 문자열 비교는 substr()을 사용하는 편이 가장 깔끔하게 해결할 수 있다. indexing에 비해서 직관적으로 코드를 작성할 수 있어 가독성이 높아진다. 다만 해당 string을 긁어와야하기 때문에 길이가 길어지면 그만큼 시간 소요가 많다는 단점이 있다. #include <iostream> using namespace std; int main() { int N, M; string S; cin >> N >> M >> S; // create Pn string Pn; for (int i=0; i<N; i++){ Pn += "IO"; } Pn += "I"; // check Pn int count=0; for (int i=0; i<M-2*N+1; i++){ if (S.substr(i,2*N+1) == Pn){ count++; } } cout << count; return 0; } 문자열을 그대로 사용하지 않고 count하는 해법 N과 M의 범위가 1,000,000까지 늘어나면 substr로는 시간 내에 해결이 불가해서 다른 방법들을 찾아 헤맸다. String을 한번만 긁고 더 이상 탐색하지 않는 방식을 고민했는데, 솔직히 다른 분들의 풀이를 참고해서 아이디어를 얻었다.ㅎㅎ ...

프로그래머스 둘만의 암호 문제 바로가기 문제에 대한 첫 인상 char을 다루는 문제였기에 ASCII 아스키 코드가 바로 떠올랐다. s의 각 알파벳별로 index만큼 이동하면서 skip할 문자를 고려해주면 된다. 처음엔 되게 간단한 문제라고 생각했지만, ‘z’을 넘어가 다시 ‘a’부터 시작할 때에 (1) 또 다시 skip문자를 고려해줘야하고 (2) 다시 ‘z’을 넘어가버리는 케이스도 고려해줘야한다는 점이 까다로웠다. while문을 통해서 이를 확인하고 ‘z’ 넘어가는 경우 알파벳 숫자만큼(26) 빼주는 방식으로 구현했다. #include <string> #include <vector> #include <algorithm> using namespace std; string solution(string s, string skip, int index) { string answer = s; for (char& c: answer){ for (int i=0; i<index; i++){ c++; if (c > 122){ c -= 26; } while (skip.find(c) != string::npos){ c++; if (c > 122){ c -= 26; } } } } return answer; } 디버깅하는 과정에서 반례가 도움이 많이 되었는데, 유용한 반례를 몇 가지 적어본다. ...

백준 18110번 문제 바로가기 solved.ac 실제 solved.ac에 있는 문제들의 난이도 반영 알고리즘을 따와서 만든 문제. 절사평균이라는 개념은 처음 들었는데 통계학적으로 outlier들을 제거할 수 있는 유용한 방법인 것 같다. 문제는 주어진 조건대로만 구현하면 쉽게 풀렸는데, 다만 index 범위의 설정과, (n=0)같은 예외처리에 신경써야했던 문제다. 내 풀이 #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { int n, rate; vector<int> rates; cin >> n; // 난이도 의견의 수 if (n == 0){ cout << 0; return 0; } for (int i=0; i<n; i++){ cin >> rate; rates.push_back(rate); } sort(rates.begin(), rates.end()); int cut = round(n*0.15); float average = 0; for (int i=cut; i<n-cut; i++){ average += rates[i]; } average /= (n - 2*cut); cout << round(average); return 0; }

프로그래머스 정수를 나선형으로 배치하기 문제 바로가기 아니 이게 Lv.0 문제라고?! DFS에 나올법한 꽤나 난이도 있는 문제였다. 일일히 구현하는것도 쉬운 문제는 아니었다. 예전에 python에서 graph관련 알고리즘 문제를 풀었던 기억이 있어서 C++로도 풀이해보았다. 내 풀이 dx, dy를 vector로 지정해서 다음 움직임의 방향을 지정해주었다. mode에 따라서 dx[mode]처럼 불러와서 다음 위치를 알아낼 수 있다. 다음 위치에 이미 부여한 숫자가 있거나(0이 아니거나), 주어진 범위에 넘어가면 안되기에 예외 처리를 해주었다. 알맞게 구현한 것 같은데 자꾸만 segmentation fault 오류가 발생해서 알아보니 mode가 4를 넘어가면 dx,dy의 index를 초과하기에 발생하는 에러였다. 따라서 mode를 4로 나눈 나머지로 (mod 4) 설정하면 오류에서 벗어날 수 있다. #include <string> #include <vector> #include <iostream> using namespace std; vector<vector<int>> solution(int n) { vector<vector<int>> answer(n, vector<int>(n, 0)); vector<int> dx = {1,0,-1,0}; vector<int> dy = {0,1,0,-1}; int x=0; int y=0; int mode = 0; for (int i=1; i<=n*n; i++){ answer[y][x] = i; int x_next = x+dx[mode]; int y_next = y+dy[mode]; bool a = (x_next<0 || x_next>=n); bool b = (y_next<0 || y_next>=n); bool c = (answer[y_next][x_next] != 0); if (a || b || c){ mode = (mode + 1)%4; }; x += dx[mode]; y += dy[mode]; } return answer; }