Tämä tehtävä on bonustehtävä, koska sen alkuperäinen malliratkaisu osoittautui vääräksi ja toimivan ratkaisun tekeminen on vaikeampaa kuin on tarkoitettua kurssilla. Saat tehtävästä pisteen automaattisesti (sinun ei tarvitse lähettää ratkaisua) mutta voit miettiä tehtävää haastavana bonustehtävänä.

Listalla on kokonaisluvut [1,2,3,...,n] jossakin järjestyksessä. Tehtäväsi on selvittää, onko lista mahdollista järjestää kahden pinon avulla.

Järjestämisessä käyt läpi listan alkiot vasemmalta oikealle. Jokaisen alkion kohdalla lisäät sen jompaankumpaan pinoon. Lisäksi saat milloin tahansa siirtää pinosta alkion tuloslistan loppuun. Tavoitteena on, että lopuksi kaikki alkiot ovat tuloslistalla järjestyksessä.

Voit olettaa, että listalla on enintään 10^5 alkiota.

Python

Toteuta tiedostoon stacksort.py funktio check, joka ilmoittaa, voiko listan järjestää kahden pinon avulla.

def check(t):
    # TODO
    
if __name__ == "__main__":
    print(check([4,5,2,3,1])) # True
    print(check([2,3,4,5,1])) # False
    print(check([1,5,2,4,3])) # True

Java

Toteuta tiedostoon StackSort.java metodi check, joka ilmoittaa, voiko listan järjestää kahden pinon avulla.

public class StackSort {
    public boolean check(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        StackSort s = new StackSort();
        System.out.println(s.check(new int[] {4,5,2,3,1})); // true 
        System.out.println(s.check(new int[] {2,3,4,5,1})); // false 
        System.out.println(s.check(new int[] {1,5,2,4,3})); // true 
    }
}