【TypeScript】AtCoder abc120_c
テストコード
import { main } from './main' describe('tests', () => { test('1', () => { expect(main('0011')).toEqual(4) }) test('2', () => { expect(main('11011010001011')).toEqual(12) }) test('3', () => { expect(main('0')).toEqual(0) }) })
提出コード (TLE)
愚直に問題手順を再現。
当然のようにTLE。
TypeScript
export const main = (S: string): number => { let sList = S.split('') let res = 0 let flg = true while (flg) { let cnt = 0 for (let i = 0; i < sList.length - 1; i++) { if ( (sList[i] === '0' && sList[i + 1] === '1') || (sList[i] === '1' && sList[i + 1] === '0') ) { sList[i] = 'removed' sList[i + 1] = 'removed' cnt += 2 } } sList = sList.filter(s => s !== 'removed') if (cnt === 0) { flg = false } res += cnt } return res } const input: string = require('fs').readFileSync('/dev/stdin', 'UTF-8') const res = main(input) console.log(res)
ES5トランスパイル
"use strict"; Object.defineProperty(exports, "__esModule", { value: true }); exports.main = function (S) { var sList = S.split(''); var res = 0; var flg = true; while (flg) { var cnt = 0; for (var i = 0; i < sList.length - 1; i++) { if ((sList[i] === '0' && sList[i + 1] === '1') || (sList[i] === '1' && sList[i + 1] === '0')) { sList[i] = 'removed'; sList[i + 1] = 'removed'; cnt += 2; } } sList = sList.filter(function (s) { return s !== 'removed'; }); if (cnt === 0) { flg = false; } res += cnt; } return res; }; var input = require('fs').readFileSync('/dev/stdin', 'UTF-8'); var res = exports.main(input); console.log(res);
提出コード (AC)
こちらの解法1を参考にした。
スタックをうまく利用する点が肝のようだ。
JSの配列はそもそもスタックの仕様を満たしているようなのでそのまま使用。
TypeScript
export const main = (S: string): number => { let sList = S.split('') let res = 0 const st: string[] = [] for (let i = 0; i < sList.length; i++) { if (st.length === 0 || st[st.length - 1] === sList[i]) { st.push(sList[i]) } else { res += 2 st.pop() } } return res } const input: string = require('fs').readFileSync('/dev/stdin', 'UTF-8') const lines = input.split('\n') const res = main(lines[0]) console.log(res)
ES5トランスパイル
"use strict"; Object.defineProperty(exports, "__esModule", { value: true }); exports.main = function (S) { var sList = S.split(''); var res = 0; var st = []; for (var i = 0; i < sList.length; i++) { if (st.length === 0 || st[st.length - 1] === sList[i]) { st.push(sList[i]); } else { res += 2; st.pop(); } } return res; }; var input = require('fs').readFileSync('/dev/stdin', 'UTF-8'); var lines = input.split('\n'); var res = exports.main(lines[0]); console.log(res);