글 읽기 - 한번만 봐주세요 제발요 제발요

smu04129 1년 전 0

어느 부분을 놓쳤는지 모르겠습니다 75프로에서 틀립니다.

#include <algorithm>
#include <iostream>
#include <map>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define MAX 20000
#define INF 987654321
using namespace std;

int N, Ans, Sidx = INF, Tidx = INF;
map<string, int> Word;
string S, T;


void update(string s, string t, int sidx, int tidx) {
	int cnt = 0, length = min(s.length(), t.length());
	for (int i = 0; i < length; i++) //접두사 개수 세어줌
		if (s[i] == t[i]) { cnt++; }
		else { break; }
	if (cnt == Ans && sidx < Sidx) { //Word에는 중복되는 단어가 없다
		S = s;           //먼저 저장된 S와 현재 s가 같을일이 없다
		Sidx = sidx;
		T = t;
		Tidx = tidx;
	}
	else if (cnt > Ans) {
		Ans = cnt;
		S = s;
		Sidx = sidx;
		T = t;
		Tidx = tidx;
	}
}

int main() {
	fast_io;
	cin >> N;
	for (int i = 0; i < N; i++) {
		string input;
		cin >> input;
		if (Word.find(input) != Word.end()) { continue; }
		Word[input] = i; //같은단어라면 최소 인덱스만을 담음
	}
    //멥특성상 Word는 key인 string을 기준으로 정렬됨
    //정렬후 인접한 단어들끼리 비교해주면 최대 접두사를 알수 있다
	for (auto iter = Word.begin(); iter != prev(Word.end()); iter++) {
		int sidx = iter->second, tidx = next(iter)->second; //t보다 s가 앞에 와야 하기때문에
		string s = iter->first, t = next(iter)->first;
		if (sidx > tidx) { //t가 먼저 있는 경우라면 바꿔준다
			swap(sidx, tidx);
			swap(s, t);
		}
		update(s, t, sidx, tidx);
	}
	cout << S << endl;
	cout << T;
}

dhyang24 1년 전 3

반례 드립니다

입력:

aaa

aac

aab

출력:

aaa

aab

답:

aaa

aac

스트링을 기준으로 정렬되었을때 s와 t의 순서가 반영되지 않습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

한번만 봐주세요 제발요 제발요

smu04129 1년 전 0

dhyang24 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말