백준 17140번 C++

오랜만에 삼성 기출문제를 풀어봤다.

삼성은 대부분 구현문제로, 문제에서 주어진 조건을 잘 보면 구현할 수 있지만

예외처리로 문제의 정답과 오답이 판가름된다.

 

 

최단 시간을 물어보는 문제여서 혹 할수도 있지만,

최대 조건의 k가 100이기 때문에 정말 구현문제이다.

 

 

이 문제에서 내 코드의 핵심은

1. map을 이용해서 저장한 뒤에, vector로 변환해주기

2. 주어진 조건이 100초까지이므로, 100초도 포함시켜야함

 

두 가지라고 볼 수 있다.

 

배열을 돌면서 map을 이용해서 값을 저장시켜 준 뒤에,

이를 vector의 pair 쌍으로 변환시킨 뒤에 (정렬을 위해),

정렬을 진행시킨다.

 

그리고 100초가 포함될 수 있기 때문에 75%에서 틀렸습니다가 뜨시는 분들은

 100을 포함시키면 된다..! 이런 것 때문에 한 문제를 놓치면 너무 아쉬울 것 같ㅏ..

 

 

코드에서 아쉬운 점은, 행과 열에 대한 코드가 각각 존재하기 때문에 어느정도의 중복이 발생한다는 점인데

다른 분들의 코드를 참고했을 때에도 이와 매우 유사했다.

 

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX(a, b) ((a>=b)?a:b)

using namespace std;

int m[101][101];

int cmp(pair<int, int>& a, pair<int, int>& b) {
    
    if(a.second == b.second)
        return a.first < b.first;
    else
        return a.second < b.second;
}

int main() {
    
    
    int r, c, k;
    
    int rows = 3, cols = 3;
    int time = -1;
    
    cin >> r >> c >> k;
    
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            cin >> m[i][j];
        }
    }
    
    
    while(++time <= 100) {
        
        if(m[r][c] == k) {
            break;
        }
    
        
        if(rows >= cols) {
            
            int maxR = 0;

            for(int i = 1; i <= rows; i++) {
                
                map<int, int> cal;

                for(int j = 1; j <= cols; j++) {
                    if(m[i][j] != 0)
                        cal[m[i][j]]++;
                    m[i][j] = 0;
                }
                
                vector<pair<int, int>> v(cal.begin(), cal.end()); // m[1] = 2, m[2] = 1
                sort(v.begin(), v.end(), cmp);
                
                int index = 1;
                for(auto x : v) {
                    if(index <= 100) m[i][index++] = x.first;
                    if(index <= 100) m[i][index++] = x.second;
                }
                
                maxR = MAX(maxR, cal.size());
            }
            cols = maxR * 2;
            
            
        } else {
            
            int maxC = 0;

            for(int i = 1; i <= cols; i++) {
                
                map<int, int> cal;

                for(int j = 1; j <= rows; j++) {
                    if(m[j][i] != 0)
                        cal[m[j][i]]++;
                    m[j][i] = 0;
                }
                
                vector<pair<int, int>> v(cal.begin(), cal.end());
                sort(v.begin(), v.end(), cmp);
                
                int index = 1;
                for(auto x : v) {
                    if(index <= 100) m[index++][i] = x.first;
                    if(index <= 100) m[index++][i] = x.second;
                }
                
                maxC = MAX(maxC, cal.size());
            }
            
            rows = maxC * 2;
        }
        
    }
    
    if(time > 100)
        cout << -1 << "\n";
    else
        cout << time << "\n";
        
    return 0;
    
}