[백준] 1283 - 단축키 지정 (C++)

https://www.acmicpc.net/problem/1283

한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명해 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 했다. 단축키를 지정하는 방법은 아래의 순서를 따른다.

1. 먼저, 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정됐는지 살펴본다. 만약 단축키로 아직 지정이 안 돼있다면 그 알파벳을 단축키로 지정한다.
2. 만약 모든 단어의 첫 글자가 이미 지정이 돼있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정되지 않은 것이 있는 경우 그 알파벳을 단축키로 지정한다.
3. 어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문자를 구분치 않는다.
4. 위의 규칙을 첫 번째 옵션부터 N번째 옵션까지 차례대로 적용한다.

 

N개의 옵션마다 단축키로 지정된 알파벳은 좌우에 [] 괄호를 씌워 출력하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 30
• 1 ≤  하나의 옵션에 포함된 단어 수 ≤ 5
• 1 ≤  각 단어의 길이 ≤ 10
• 단어는 공백 한 칸으로 구분된다.

 

아래 링크들을 참고하면서 문제를 풀기 위해 필요한 개념을 정리해 봤다.

[C++] 입출력과 스트림, 버퍼

 

[C++] getline을 이용해 입력받을 때 cin.ignore로 버퍼비우기

 

C++ cin 초기화, 입력 버퍼 비우는 법 : ignore 함수 (BOJ 4458)

[BOJ/C++] cin.tie(NULL)과 ios_base::sync_with_stdio(false) 그리고 endl...

 

문제에 주어진 입력을 받으려면, int n을 먼저 입력받고 이후 n개의 string을 입력받아야 한다.

• int n을 입력받을 땐 cin >> n;으로 간단하게 입력을 받을 수 있다.
• 이때, cin은 빈칸이 나올 때까지 읽기 때문에 공백이 포함된 string을 입력받으려면 개행 문자'\n'가 나올 때까지 입력을 받는 getline(cin, string s);를 사용해야 한다.

int n;
cin >> n; // n = 1

string str;
getline(cin,str); // str = "Hello World"

 

c++ 입출력에서 프로그램은 한 번에 1 byte씩 읽어 들여 처리한다. 블록 단위로 데이터에 접근하는 디스크 같은 장치들에 비해 1 byte씩 읽어 들이는 것은 비효율적이다. 따라서 c++에선 임시로 메모리를 저장하는 메모리 블록인 버퍼(Buffer)를 사용해 한꺼번에 많은 데이터를 읽어 저장해 둔다.

• 버퍼가 꽉 차거나 개행 문자('\n)를 만나는 경우, 버퍼는 자동으로 비워진다.

 

위의 입력을 받는 상황에서, getline(cin, string s);가 실행되기 전 cin >> n;을 실행하면 버퍼엔 개행 문자('\n')가 남아있게 되고 getline(cin, string s);에 개행 문자('\n')가 입력돼 문자열을 받을 수 없게 된다.

• 따라서 사이에 버퍼를 비워주는 cin.ignore();을 반드시 추가해야 한다.

int n;
cin >> n; // n = 1

cin.ignore(); // 버퍼 비우기

string str;
getline(cin,str); // str = "Hello World"

 

입력을 받는 것만 주의하면 나머지는 규칙대로 구현하면 된다.

1. 각 옵션에 대해 공백마다 단어를 잘라 vector에 저장하고, 모든 단어의 첫 글자가 단축키로 지정돼 있는지 확인한다. 안돼있다면 해당 알파벳 좌우를 [] 괄호로 감싼 뒤 옵션 string을 출력한다.
2. 다음 규칙으로 넘어간 경우엔, 옵션에 있는 모든 알파벳 중 단축키로 지정되지 않은 첫 번째 알파벳의 좌우를 [] 괄호로 감싼 뒤 옵션 string을 출력한다.

 

vector<string> v;에 저장된 옵션의 단어들을 타입을 추론해 변수의 자료형을 결정하는 auto 키워드를 사용해 반복문으로 접근할 경우 주의해야 한다.

• 아래 정답 코드를 확인해 보면 key() 함수를 통해 알파벳 좌우에 [] 괄호를 붙여 반환하고, 뒤에 남은 알파벳을 substr() 함수를 통해 붙여 string에 저장한다. 이후 해당 string으로 tmp를 대체한다.
  • 여기서 substr(pos, n);는 pos번째 문자부터 n만큼의 문자열을 반환한다.
• 이때, tmp 앞에 &를 붙이지 않으면 vector의 데이터를 복사해 사용하게 되고, vector에 저장된 원본 데이터엔 아무런 변화가 없게 된다. 따라서 원본 데이터를 바꾸려면 &를 붙여 데이터를 참조하도록 해야 한다.

// 배열 데이터를 복사해서 사용
for (auto tmp:v) {}

// 배열 데이터를 참조해서 사용
for (auto &tmp:v) {}

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N 입력받고 입력 버퍼 비우기
2. getline()으로 옵션을 \n을 기준으로 한 줄씩 입력받기
   1. 옵션을 공백마다 잘라서 단어들을 vector에 저장하기
   2. bool visit[26]: 알파벳이 단축키로 지정됐는지 확인하는 배열
   3. 단어마다 첫 글자가 단축키로 지정됐는지 확인하기
      1. 단축키로 지정해야 한다면
         1. 대문자나 소문자에 맞춰서 단축키 확인 배열 true로 바꾸기
         2. 단축키를 지정했다는 표시하기
         3. 해당 첫 글자의 좌우를 [] 괄호로 감싸고, 첫 글자를 제외한 뒷 알파벳 붙이기
   4. 앞서 단축키를 지정하지 않았다면, 해당 옵션 중 아무 글자나 확인하기
      
      1. 0부터 단어 길이만큼 반복문을 돌면서 공백을 만나면 continue 하기
      2. 단축키로 지정해야 한다면
         1. 대문자나 소문자에 맞춰서 단축키 확인 배열 true로 바꾸기
         2. 단축키를 지정했다는 표시하기
         3. 해당 글자의 좌우를 [] 괄호로 감싸고, 앞뒤에 나머지 알파벳 붙이기
3. 옵션의 모든 단어 뒤에 공백을 붙이고, 정답 string 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int n;
bool visit[26];

// 문자를 []로 감싸서 string으로 반환
string key(char& a) {
    string tmp = "";
    tmp += "[";
    tmp += a;
    tmp += "]";
    return tmp;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    cin.ignore();
    for (int i=0; i<n; i++) {
        // 한 줄 입력받기
        string str;
        getline(cin,str);
        
        // " "마다 단어 잘라서 vector에 넣기
        int str_s = str.size();
        string tmp = "";
        vector<string> v;
        for (int i=0; i<str_s; i++) {
            if (str[i]==' ') {
                v.push_back(tmp);
                tmp = "";
            }
            else
                tmp += str[i];
        }
        v.push_back(tmp);

        // 단어 첫 글자 확인
        bool flag = false;
        for (string& tmp:v) { // & 중요
            if (tmp[0]-'A'>=0 && tmp[0]-'A'<=25) {
                if (!visit[tmp[0]-'A']) {
                    visit[tmp[0]-'A'] = true;
                    flag = true;
                    string keyword = key(tmp[0]);
                    tmp = keyword + tmp.substr(1,tmp.size());
                    break;
                }
            }
            else if (tmp[0]-'a'>=0 && tmp[0]-'a'<=25) {
                if (!visit[tmp[0]-'a']) {
                    visit[tmp[0]-'a'] = true;
                    flag = true;
                    string keyword = key(tmp[0]);
                    tmp = keyword + tmp.substr(1,tmp.size());
                    break;
                }
            }
        }

        // 아무 글자 확인
        if (!flag) {
            for (string& tmp:v) { // & 중요
                int tmp_s = tmp.size();
                bool found = false;
                for (int j=0; j<tmp_s; j++) {
                    if (tmp[j]==' ') continue;
                    if (tmp[j]-'A'>=0 && tmp[j]-'A'<=25) {
                        if (!visit[tmp[j]-'A']) {
                            visit[tmp[j]-'A'] = true;
                            string keyword = key(tmp[j]), pre = tmp.substr(0,j);
                            pre += keyword;
                            pre += tmp.substr(j+1, tmp.size());
                            tmp = pre;
                            found = true;
                            break;
                        }
                    }
                    else if (tmp[j]-'a'>=0 && tmp[j]-'a'<=25) {
                        if (!visit[tmp[j]-'a']) {
                            visit[tmp[j]-'a'] = true;
                            string keyword = key(tmp[j]), pre = tmp.substr(0,j);
                            pre += keyword;
                            pre += tmp.substr(j+1, tmp.size());
                            tmp = pre;
                            found = true;
                            break;
                        }
                    }
                }
                if (found) break;
            }
        }

        // 답 출력하기
        string ans = "";
        for (auto &i:v) { // & 중요
        	ans += i;
        	ans += " ";
        }
        cout << ans << "\n";
    }
}