Pythonで言うSetのようなオブジェクトは、Javascriptにもあるのか
解決したいこと
Paiza問題集に掲載されている問題なのですが、Javascriptでの解き方がわかりません。
「クエリメニュー：アイドルグループ」という問題です。
問題の内容は、配列に文字列を記録し以降の指示に応じて取捨をしながら、時々配列の要素を全出力せよというものです。出力する時は辞書順という条件が付いています。
入力ケースの4番目でタイムオーバーになる
この問題では入力ケースが4つ用意されており、3番目までは通っています。しかし4番目のケースでタイムオーバーとなってしまい、不正解の判定となるのです。
解答例ではPythonのSetを使っていましたが、Javascriptでも似たようなことができるのでしょうか？JavascriptにもSetは存在しますが、ソートする機能を持たないらしいです…。
それとも配列における効率的なソート方法があれば、この問題を突破できるのでしょうか？
提出したコード
Javascriptで2つパターンがあるので、両方載せておきます。
// Javascriptでの提出（得点：75/100）
process.stdin.resume();
process.stdin.setEncoding('utf8');
// 自分の得意な言語で
// Let's チャレンジ！！
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
[ N , K ] = lines[ 0 ].split( " " ).map( Number );
Name = new Array( N );
for ( i = 0 ; i < N ; i ++ ) {
Name[ i ] = lines[ i + 1 ];
}
for ( i = 0 ; i < K ; i ++ ) {
Info = lines[ i + N + 1 ].split( " " );
switch ( Info[ 0 ] ) {
case "leave" :
Name.splice( Name.indexOf( Info[ 1 ] ) , 1 );
break;
case "join" :
Name.push( Info[ 1 ] );
break;
case "handshake" :
Name.sort( function sort ( a , b ) {
return a.localeCompare( b );
} );
for ( j = 0 ; j < Name.length ; j ++ ) {
console.log( Name[ j ] );
}
break;
}
}
});
また常に順番が保存される形の配列でも試してみました。二分探索で挿入する位置を調べて効率化しようとしましたが、これでも速くなりませんでした。
// Javascriptでの提出2（得点：75/100）
// （中略）
for ( i = 0 ; i < N ; i ++ ) {
Name[ i ] = lines[ i + 1 ];
}
Name.sort( function sort ( a , b ) {
return a.localeCompare( b );
} );
for ( i = 0 ; i < K ; i ++ ) {
Info = lines[ i + N + 1 ].split( " " );
switch ( Info[ 0 ] ) {
case "leave" :
Name.splice( Name.indexOf( Info[ 1 ] ) , 1 );
break;
case "join" :
Insert( Name , Info[ 1 ] );
break;
case "handshake" :
for ( j = 0 ; j < Name.length ; j ++ ) {
console.log( Name[ j ] );
}
break;
}
}
function Insert( A , m ) {
l = 0;
r = A.length;
mid = 0;
while ( l < r ) {
mid = Math.floor( ( l + r ) / 2 );
if ( m < A[ mid ] ) {
r = mid;
}
else {
l = mid + 1;
}
}
A.splice( l , 0 , m );
}
});
なおPython3ならば、Setを使うことで簡単に解けます。コードもかなり簡潔です。
0 likes
